精進記録: ABC46 - ABC48 D問題
ABC-Cが旧基準まで含めて終わったので、ABC-Dに移行。
ABC-Dの42-45は以前解いたので、それ以降を進めていく。
今日はD問題とりあえず3問。D問題も難易度はピンキリなようだ。ABC-D46は300点だったし。
今日の3問で手こずったのはABC-D 48 (500点)。
正解にはたどり着いたが、時間がかかりすぎてしまった。
ゲーム問題は終状態の性質をよくよく考えることが大事なようだ。
やはりD問題になると勉強になることが多い。
あと、最近行われていたらしいキーエンスコンテストの問題を見てみた。
考察をしてみただけだが、120分あればD問題までは解けそうな印象だった。
以下、解答メモ(正確に言えば思考の記録)D
ABC46
パーを使うのは後回しにしても点数変わらん。
よって思考停止でグー半分まで連打→ 残りパーでok
一発AC
復習も兼ねて、C問題も考察だけはやることにする。
ABC47
Aj - Ai (i < j)の最大値をmaxとしたとき、同じ最大値maxを有する組がいくつ存在するかが効く(入力例2)。
制約がN <=10^5なので、全ての組を調べることは不可能。
(自身より右側で最大のもの), (自身より左側で最小のもの)の2つをO(log N)で取得するには？
前者については、後ろから見ていきながら要素をmax heapに入れていけばいい。
後者は逆に、前から見ていきながらmin heapに入れる。
一つのAiが最大、最小両方に絡むことはありえないのでどちらかだけで十分。
->min heapの宣言の仕方忘れてたが調べて一発AC。Tの必要のなさ。
というか、普通に前から見て最小値更新していけばいいだけだ。O(N)でいい。
無駄に変なことをやってしまった。一度もpop()していないのだから気づけ。
ABC48
抜き取り方はどのように影響するか。
入力例3: abcab
abcab->abcb -> acb -> ab
abcab->abab
abcab->acab -> acb->ab
この例では影響しないが一般にそうか？
負けが決まる瞬間の文字列のパターンは、
-
残り文字数が2
2. cbcbcbcb or cbcbcbc
のように、一つおきに同じ文字が並んだ状態。
a1 a2 a3という並びに対して、a1 != a3ならa2を消せる。
そして、a2を消すことはa1, a3の外側の文字列には影響しない。
任意の3つ組についてこれが正しい。
自分がどう行動しようが、上記の2つのパターン以外なら相手は生き残るので、最長の場合どちらのターンでこれらのパターンになるかを考えれば良い? 上の例で順番がゲームの長さに影響しているのがちょっと不気味。
|s| <= 10^5なので実際にシミュレーションしてみる。前から、a1 != a3を見つけ次第a2を消すことを繰り返す。
stringで書いていたらTLEした。それはそう。リストでやり直す。
-> WA。
abababcという状況でbを消すとababacとなり、左のaが消せるようになる。
すると、ababc -> abac -> abc->acという削除が可能。
abab..が続いていたとしても、あらたにcが右から入ってくるとacになる。
abac -> abc->ac
ababc -> abac-> abc->ac
acに持っていくまでに必要なステップ数は(abab..の文字数)-1
abcabという場合
-> acab->acb->ab
->abab
->abcb->acb->ab
の3パターン
左から見てab(…)aだったとする。ここで、(…)はaを含まない文字列。この時、右から消していく事により、常にabaに帰着できる。それに必要な操作回数は(…).size()
つまり、一番左端をaとしたとき常に、abaca….という形にまずできる。
それに必要なステップ数を記録しておく。
一般に、abac…という形の場合、b, c, にひとつでも違うものが混じっていれば一番右の x!=aに圧縮できる。
ababacacabacac
-> ababcacabacac
-> ababacabacac
-> ababcabacac
-> abacabacac
-> abcabacac
-> acabacac
->acabcac
->acabac
->acbac
->abac
->abc
-> ac
以上から考えると、文字列が最初からababa …だった場合を除いて、必ず3文字までは落とせそう。
3文字になった段階でabaなのかabcなのかで勝敗が決まる。
3文字に落とし込むまでに必要な操作数の偶奇と、両端の文字が同じか否か。
最初からabab…だった場合は問答無用でfirstが死ぬ。
3文字に落とし込むまでの操作数はs.size()-3
abab..の場合、s.size()-3は文字数奇数で偶、偶数で奇
操作数が偶数でabaだとsecond、奇数だとfirst
操作数偶数でabaだと逆
操作数が奇数でabだとsecond, 奇数だとfirst
操作数奇数でabだと逆
結局、
s.size()が奇数かつ aba -> second
s.size()が偶数かつ ab -> second
それ以外firstでok。
-> AC。
ゲーム展開に勝敗が依存しなさそうというところを詰めて考えればもっと早く到達できたはず。
解説を読んだ。ゲーム展開が常に3文字になるように進むわけではないというところを詰めきれていなかったが、可能なあらゆる終状態について文字数の偶奇が共通しているということに気づけば、ゲーム展開について仮定する必要がなかったようだ。
教訓: ゲーム問題は終状態の性質を捉える。
