TopCoder SRM 701
— つたじろう@秋M3F-19a (@_TTJR_) October 26, 2016
930 -> 961 (+31)
いい加減4桁になりたい・・・ #tsutajmemo
TopCoder SRM 701に参加。誤読の恐ろしさとチャレンジの重要性を知った回でした。
SquareFreeString (Easy)
問題 → TopCoder Statistics - Problem Statement
SquareFreeStringとは、文字列Sの中で、長さが1以上の部分文字列Tが連続して(つまり、TT と書ける)登場しない文字列のことです。
例えば、"apple"は、長さ1の部分文字列"p"が連続している箇所が存在するので、SquareFreeStringではありません。また、"people"は同じく長さ1の部分文字列"p"が2つ存在しますが、連続していないのでSquareFreeStringであると言えます。
これを解くためには、
- 長さが 2 〜 (文字列Sの長さ)の偶数である部分文字列を列挙
- その部分文字列を半分に割ったものをs1, s2とおいたとき、s1 == s2となるものが存在するならば"not square-free"
- そのような要素が存在しなければ "square-free"
という方針を取ればよいです。文字列の長さは最大50なので計算量的にも余裕です。
どうやら部分文字列の意味を取り違った人が多かったようで(私も最初間違えました)、同じアルファベットがあるかどうか調べている人がけっこういましたね。今回は「部分列」ではなく「部分文字列」を扱っており、連続したものを見なければいけないのでそれだと方針が違います。ちなみにその間違いが多いだろうなと睨んでいた私はチャレンジで2人落としました(チャレンジしたの初めてだったので成功して嬉しかった)
class SquareFreeString { public: string isSquareFree(string s) { int len = s.length(); bool ok = false; repq(i,2,len) { if(i % 2 == 1) continue; repq(j,0,len-i) { string temp, s1, s2; temp = s.substr(j,i); s1 = temp.substr(0,i/2); s2 = temp.substr(i/2); if(s1 == s2) ok = true; } } if(ok) return "not square-free"; else return "square-free"; } };
SortingSubsets (Med)
問題 → TopCoder Statistics - Problem Statement
これ、本当にMedか？？？と思うくらい簡単だった。個人的にはEasyより全然簡単だった。
与えられる配列をソートしたものと元の配列でdiffとる。以上！
class SortingSubsets { public: int getMinimalSize(vector<int> a) { vector<int> t = a; sort(t.begin(), t.end()); int ans = 0; rep(i,0,a.size()) if(a[i] != t[i]) ans++; return ans; } };
ThueMorseGame (Hard)
問題 → TopCoder Statistics - Problem Statement
提出したけどSystem testで落とされた。通したの1人しかいなかったみたい。
コンテスト中に考察したこととか (嘘解法)
嘘解法なので参考にしないでください、自戒を込めて書いてます。
- 最善な行動を取るので、even in binaryにしにいくような選択をとるに決まっている
- ある人が負けるときのパターンは、odd in binaryにしてしまう選択肢しか残されていないときか、前の手番で石を全て取られた時しかない
- → 前の手番で石を全て取られたら負けなのだから、なるべく多く取るのが最善なのか？ (最善ではなかった)
- → 現在残っている山から石を取る個数のパターンを、大きい方から全通り試せばodd in binaryを選ばざるを得ないかどうか分かる？
- → サンプル通ったからこれでええやろ(適当)
- → Failed System test
という感じでした。つらいですね。というわけで真面目に解法書きます。
正しい考察
- mが1であるとき ... 1減らすしか選択肢がないため、nを1ずつ減らしてodd in binaryになった時のステップ数から勝敗を判定。
- それ以外のとき ... 前の手番で、相手に石を全て取られないように動きたい
- → どちらにとっても、今の自分の手の2つ前(直前に行った自分の手)を行ったあとに、山に(m+1)個の石が置いてあれば必ずこれを達成できる。なぜなら、相手のターンで1〜m個の石を取っており、その結果山に残るのは1〜m個になり、全て取ることができるからである。
- → 実際にはodd in binaryにしてはいけない制約もあるため、「山に(m+1)以上でeven in binaryを満たす最小個数の石」が置かれていれば達成できる。
- → 逆再生のように、山が0の状態から上記の条件を満たす数ずつ増えていくものとして考え、山にある個数, m, nの大小関係で勝敗を判定すればよい。
ちなみにodd in binaryの判定についてですが、gccビルトイン関数で"__builtin_popcount(unsigned int)"というものがあって、これはunsigned intを2進数表記した時に1が立っているビット数を返してくれる関数のようです。知らんかった・・・。まあ普通に自前で関数作っても問題ないですけどね。
ビット関係のビルトイン関数についてはこちらが参考になると思います。
class ThueMorseGame { public: string get(int n, int m) { // 1度に1個しか取れない時 if(m == 1) { if(n == 1) return "Alice"; int flag = 0; while(1) { n--; if(__builtin_popcount(n) & 1) { if(flag) return "Alice"; else return "Bob"; } flag = 1 - flag; } } // pile := 山の数 (逆再生だと思えば良い) // pileには常に、消費に2ターン必要な数が足されるため、 // pileは常に後攻(Bob)サイドにとって有利な数になる。 // → 足す数を s と置く。 // → pile + s > n であればアウト (山の数オーバー) // → つまり、pile + s <= n が成り立たなければならない int pile = 0; // 条件を満たす数ずつ山を増やす操作を考える // 山はnを超えない (pile + (m+1) <= n → pile + m < n) while(pile + m < n) { pile += m + 1; // even in binaryにするための操作 while(__builtin_popcount(pile) & 1) pile++; } // 最終結果でpileに余裕がある、つまり pile < n である場合、 // Aliceの最初の操作でnからpileになるように // 適当に取ることができるためAliceの勝ち // そうでなければBobの勝利になる。 if(pile < n) return "Alice"; else return "Bob"; } };
結果
解答状況
| 問題 | 時間 | 得点 | (満点) |
|---|---|---|---|
| Easy | 1:12:23.087 (Resubmit) | 75.00 | 250.00 |
| Medium | 0:01:52.010 | 497.84 | 500.00 |
| Hard | 0:31:49.838 | 900.00 | |
| (Challenge) | Success +2 | 100.00 | - |
| (Sum) | - | 672.84 | 1600.00 |
順位 / レーティング
Ranking: 115th / 376
Rating: 930 -> 961 (+31)
反省
Easy誤読はいただけない。というか絶対やっちゃダメ。早く解くのも大事だけど正確にやらないとダメ。Medが早く解けたのはよかった。取れる問題は確実に取らないとね。Hardは自分の実力は出した感じがあるので、まあ致し方なし。復習はちゃんとする。
あとチャレンジ超大事。チャレンジしていなければ順位が90くらい落ちてたので本当に危なかった。特に今回のように落とし穴が想定できる問題に関しては必ず目を通す。他のRoomの人にもチャレンジできる知見を得たので次回以降は活用していきたい。
大学のWi-Fiだとなぜかアプレット開かないけどWebArenaは使えることが判明し、大学でもTopCoderできるようになったしぼちぼち過去問を解き始めたい。どっかのサイトで読んだとおり、全探索やDPの出題がかなり多い気がするので対策したい。
