SRM562
Easyで絶望した回。MediumのDPが後少しで気づかなかった。しかももっと簡単な答えがあって絶望した回。
結果報告
確か300-500-1000じゃなかったかな（適当）
| Level | ProblemName | Status | Point |
| Easy | FoxAndHandle | FailedSystemTest | 0.0 |
| Medium | SpellCards | Opened(practiced) | 0.0 |
| Hard | -- | Unopened | 0.0 |
1545->1486->1500->1497->1518->1457とかそんな感じのレート遷移をしてる。
自分の実力がレート1500周囲に収束している感。
Easy FoxAndHandle
問題
ある文字列Hと、Hを適当にパーミュテーションした値H'を用いて、Hの2倍の長さである文字列Sを作った。
例えば、Hが"abc"、H'が"bca"ならば、"abcbca"とか"bcaabc"とか、"abbcca"とかが作れる。
もっと言えば、H="abc"ならば、"abcbca"とか"bcaabc"とか"abbcca"とか"abccba"(H'が"cba")とか"acabcb"（H'が"cab")とかが作れる。
今、文字列Sが与えられるが、元の文字列Hを忘れてしまった。
Hとしてあり得る辞書式で最小な値を求めよ
考えたこと
うーん、貪欲でできる気がしなくもないけどよくわからない。というか、DPを使ったら安全なのではないか？
dp[i][j]を、Sの中のi番目の文字までを生成できる、長さjの文字列の辞書式最小値を格納することにする。
すると、
dp[i][j] = dp[i-1][j]; # Sの中のi-1番目の文字まででできてる長さjの文字の最小値
もしS[i]をHの最終要素として付け足すことが可能なら、
dp[i][j] = max( dp[i][j], dp[i-1][j-1] + "S[i]");
として表せる。
(ここから嘘)
後半の式を実行するかどうかは、予めHに含まれるアルファベットの数を数えておいて、
dp[i-1][j-1]+"S[i]"がそのアルファベット数を超えないか見ればよいだろう。
(ここまで嘘)
書いた。出した。
…落ちたー＼(^o^)／
間違えたコード
string lexSmallestName(string S) {
string result;
int count[30];
memset( count , 0, sizeof(count) );
int size = S.size();
int ssize = size/2;
for( int i = 0 ; i < size; i++ ){
count[S[i]-'a']++;
}
for( int i = 0 ; i < 30; i++ ){
count[i] /= 2;
//cout << count[i] << ", " ;
}
//cout << endl;
string dp[102][52];
for( int i = 0 ; i < 102 ; i++ ) for( int j = 0 ; j < 52; j++ ){
string dammy(ssize, 'z');
dp[i][j] = dammy;
if( j == 0 ) dp[i][j] = "";
}
for( int i = 1 ; i <= size; i++ ){
for( int j = 1 ; j <= ssize; j++ ){
dp[i][j] = dp[i-1][j];
string tmp = dp[i-1][j-1];
tmp += S[i-1];
int tmpcount[30];
bool ok = true;
for( int k = 0 ; k < 30 ; k++ )tmpcount[k] = count[k];
for( int k = 0 ; k < (int)tmp.size(); k++ ){
int ind = tmp[k]-'a';
if( tmpcount[ind] <= 0 ){
ok = false;
break;
}
tmpcount[ind]--;
}
if( ok ) dp[i][j] = min( dp[i][j], tmp );
}
}
return dp[size][ssize];
}
何が悪かったのか
使わなかったアルファベットが妥当かも判定していないと途中で残念な結果が現れることがわかった。
例えば入力が"bbaamfmf"の時、期待される答えは"bafm"だけれど
| 0 | 1 | 2 | 3 | 4 | |
| 0 | "" | ||||
| 1 | "" | "b" | |||
| 2 | "" | "b" | |||
| 3 | "" | "a" | "ba" | ||
| 4 | "" | "a" | "ba" | ||
| 5 | "" | "a" | "am" | "bam" | |
| 6 | "" | "a" | "am" | "amf" | "bamf" |
| 7 | "" | "a" | "am" | "amf" | "bamf" |
| 8 | "" | "a" | "am" | "amf" | "bamf" |
みたいに計算されてしまう。
何が悪いのかといえば、dp[3][1]が"a"になってたりdp[6][3]が"amf"になってたりするのが行けない。
元の数字が"bba"だと、必ずbは使わないといけないのだから、dp[3][1]は"b"、dp[6][3]は"baf"であるべき。
修正したコード(System Test通過済み)
string lexSmallestName(string S) {
string result;
int count[30];
memset( count , 0, sizeof(count) );
int size = S.size();
int ssize = size/2;
for( int i = 0 ; i < size; i++ ){
count[S[i]-'a']++;
}
for( int i = 0 ; i < 30; i++ ){
count[i] /= 2;
//cout << count[i] << ", " ;
}
//cout << endl;
string dp[102][52];
for( int i = 0 ; i < 102 ; i++ ) for( int j = 0 ; j < 52; j++ ){
string dammy(ssize, 'z');
dp[i][j] = dammy;
if( j == 0 ) dp[i][j] = "";
}
for( int i = 1 ; i <= size; i++ ){
for( int j = 1 ; j <= ssize; j++ ){
dp[i][j] = dp[i-1][j];
string tmp = dp[i-1][j-1];
tmp += S[i-1];
int tmpcount[30];
int tmpcount2[30]; // Hに使わなかったアルファベットの個数カウント
memset( tmpcount2, 0 , sizeof(tmpcount2));
bool ok = true;
for( int k = 0 ; k < 30 ; k++ ){
tmpcount[k] = count[k];
}
for( int k = 0 ; k < i ; k++ ){
tmpcount2[S[k]-'a']++;
}
for( int k = 0 ; k < (int)tmp.size(); k++ ){
int ind = tmp[k]-'a';
if( tmpcount[ind] <= 0 ){
ok = false;
break;
}
tmpcount[ind]--;
tmpcount2[ind]--;
}
// check the rest
for( int k = 0 ; k < 30 ; k++) {
if( tmpcount2[k] > count[k] ){
//cout << (char)(k+'a') << ", " << tmpcount2[k] << ">" << count[k] << endl;
ok = false;
break;
}
}
if( ok ) dp[i][j] = min( dp[i][j], tmp );
}
}
return dp[size][ssize];
}
貪欲な解き方
むしろこっちのほうがメジャーな解き方なんですかね。周りがみんなGreedyで凄いぼっち感あった。
S[i]の文字を見ている時
- そのアルファベットを使わないとHが構成できないとき->使う
- そのアルファベットを使うとHが構成できない場合->使わない
- どっちでも良い
の３通りに分けられる。
どっちでも良い場合、
Sの先をみていって
「自分よりもアルファベットの小さい値がどこかで使える」->使わない
「自分よりもアルファベットの大きい（または等しい）値をどこかで使わないといけない」->使う。
というふうな方針にすれば、貪欲解ができる。
これはこれで、「自分よりもアルファベットの小さい値がどこかで使える」の判定でバグったりして何度か書きなおした。
一発で書くのはどっちの方針でもなかなか難しい。
貪欲法のコード(System Test通過済み)
string lexSmallestName(string S) {
string result;
int count[30]={0};
int remain[101][30]={0};
int size = S.size();
//int ssize = size/2;
for( int i = 0 ; i < size; i++ ){
count[S[i]-'a']++;
for( int j = 0 ; j <= i; j++ ){
remain[j][S[i]-'a']++;
}
}
for( int i = 0 ; i < 30; i++ ){
count[i] /= 2;
//cout << count[i] << ", " ;
}
for( int i = 0 ; i < size; i++ ){
int ind = S[i]-'a';
bool ok = true;
if( count[ind] == 0 ) continue;
if( count[ind] == remain[i][ind] ){
result += S[i];
//cout << "must use"<< count[ind] << ", remains"<<remain[i][ind] << ", so use " << S[i] << endl;
count[ind]--;
continue;
}
for(int j = i+1 ; j < size; j++ ){
if( S[j] >= S[i] && remain[j][S[j]-'a'] <= count[S[j]-'a'] ){
// must use S[j], and S[j] is worse than S[i]
//cout << S[j] << " must be used, so prefer "<< S[i] << endl;
break;
}
if( S[j] < S[i]&& count[S[j]-'a'] >=1 ){
//cout << "fouund "<< S[j] << ", so skipped " << S[i] << endl;
ok = false;
break;
}
}
if( ok ){
result += S[i];
count[ind]--;
}
}
return result;
}
Medium SpellCards
問題
カードの羅列がある。カードはそれぞれレベル・ダメージという２つの値を持っている。
プレイヤーはこのカードの羅列にたいして
- １枚目のカードに書かれた「レベル」の枚数のカードを先頭から捨て、１枚目のカードに書かれた「ダメージ」を敵に与える
- 最後のカードを先頭に持ってくる
という２つの動作ができるとする。
レベル・ダメージが与えられた時、プレイヤーが敵に与えられる最大ダメージ数を求めよ。
考えたこと
カードの枚数最大50なので、使ったカードの場所とかを覚えると2^50になって当然間に合わない。ってことで悩む。
……区間DPですか？ と思って
dp[i][j]...i番目のカードからj番目のカードまでで算出されたダメージ なんて思ってみる。
書いてみる。微妙に時間足らなかった。
チャレンジもできなさそうなので納得するまで書いてみるが。
…この方針じゃ無理ポだった＼(^o^)／
この方針では、3枚のカードa,b,cがあった時、b(レベル1)を使用-> a,cが残る -> a(レベル2を使用) -> 何も残らない
というケースが対応出来ないことがわかった。
復習
dp[i][j][k]...[i,i+j)番目までのカードで、kこ残っている場合の最大ダメージ数
とすると
dp[i][j][k] = dp[i+1][j][k-1]; (i番目のカードを使う場合)
or
dp[i][j][k] = dp[i+1][j-1][k-1+level[i] ] (i番目のカードを使う場合、ただし[i+1,i+j) の枚数がk+level[i]よりも少ない場合はこの処理は不可能）
の、どちらか大きい方を選べば良い。
コード
int dp[52][52][52]; vector<int> level; vector<int> damage; int maxDamage(vector <int> level_, vector <int> damage_) { int result=0; int size = level_.size(); level = level_; damage = damage_; //dp[i][j][k]... maximum damage from area [i,i+j), leaving k cards //i \in [0,size) //j \in [1,size] //k \in [0,j] //dp[i][j][k] = max ( dp[i+1][j-1][k-1], damage[i] + dp[i+1][j-1]][k+level[i]-1] // before i,j,k, // i+1,j-1,k-1 // i+1,j-1,k+level[i]-1 // must be calculated //dp[i][j][j] = 0; memset( dp, 0 , sizeof(dp)); for( int j = 1 ; j <= size; j++ ){ for( int k = j ; k >= 0 ; k-- ){ for( int i = 0 ; i < size; i++ ){ if( k != 0 )dp[i][j][k] = dp[(i+1)%size][j-1][k-1]; if( k+level[i] <= j ) dp[i][j][k]=max( dp[i][j][k] , damage[i] + dp[(i+1)%size][j-1][k+level[i]-1]); cout << i << ", "<< j << ", " << k << ": "<< dp[i][j][k]<<"\t"; result = max(result, dp[i][j][k] ); } cout << endl; } } return result; }
効果的な解き方
実はこの問題は、levelの総和がカード枚数以下であるカード集合で、damageの総和が最も大きいもの
を計算するだけで良い。(それはdp[i]=levelの総和がiのカード集合におけるdamage総和最大、とすれば計算可能)
この計算だけで何故問題の要件を満たす値になるか？ を示すためには、以下の補題を示せれば良い。
（補題）
levelのそれぞれ書かれたカードの並び、があるとする。
カードのレベルをそれぞれ
任意のカードの集合について、
そのレベルの総和がN以下であるとき、あるカードが存在して、
はすべてMに属さない
要するに、最低でも一個のカードはMのカードを使わずに利用可能であるってこと。
これが示せれば、後はMのなかから利用可能なカードをじゅんじゅんに使っていけばMのダメージ総和が実現できる。
(補題の証明)
背理法による。
もしこの命題が成立しないのだとすると、
あるカード集合{tex:M=\{C_{a_0},\dots,C_{a_{m-1}}\}]が存在して、
を満たす。
この式をすべて足し合わせるとと言えるが、それは「そのレベルの総和がN以下である」という過程に矛盾する。
よって背理法によりこの命題は成立する。
コード(効果的な方)
int maxDamage(vector <int> level, vector <int> damage) { int result=0; int dp[52]; int size = level.size(); memset( dp, 0 , sizeof(dp)); for( int i = 0 ; i < size; i++){ for( int j = size ; j>= 0; j-- ){ if( j + level[i] <= size ){ dp[j+level[i]]=max(dp[j]+damage[i],dp[j+level[i]]); // cout << j+level[i]<<":" << dp[j+level[i]]<<endl;; result = max(result, dp[j+level[i]]); } } } /* for( int i=0 ; i <= size; i++ ) cout << dp[i] << ", "; cout << endl; */ return result; }
