しばらく ARC は出るとしても Unrated で出ようと決めていたので、それで。 とか言いつつ、ひょっとしたら 3 問解けちゃったりするかも？とか期待していたりしたけど、 全然でした。０完。Unrated でよかったよ。
解説読んだらそのまんまなんだけど、コンテスト中にちゃんと辿り着けなかったことへの反省も込めて、自分でも解き方を整理しておく。
文字列が B から始まる３文字 以上の文字列だった場合には、2-3 文字目から順に左から右へ操作を適用して行くことで、BAA ... AB という回文にできる。
また、文字列が A で終わる３文字以上の文字列だった場合にも、逆向きに右から左へ操作していけば、ABB .. BA を得ることができる。
それ以外の場合、つまり、最初が 'A' で最後が 'B' だった場合には、これらふた文字を変更する手段がないため不可である。
ただし、B から始まり A で終わる文字列のうち、二文字のもの、つまり "BA" だけは回文にできない。
投稿例： 33639502
これ、明らかにTLEになるのがわかっていながら、Grundy 数を求めるコードを提出して TLE。
ちゃんと解くのは後日にするとして、Alice は自分のターンでは取れるだけ石をとるべきであるという部分だけ確認しておく。（解説中の「証明」のところ）
Alice のターンにおいて、取れるだけ多くの石を取るべきであることを以下に証明する。
N < A のときには、明らかに Alice の負けである。そこで、以降では \(N \ge A\) とする。
\(A \le B\) の場合、Alice は取れるだけ石をとることで、残りの個数を \(N \mod A\) 個、つまり A 未満、したがって B 未満にできるので勝つことができる。 よって、この場合には Alice は取れるだけ石を取るべきである。
また、\(A > B\) の場合、もし Alice が取れるだけ石を取らなかった場合、 残りの石の個数が B より多い状況で、Bob の番となり、\(A > B\) から先ほどと同様の議論により、Bob は取れるだけ石を取ることで勝つことが出来てしまう。よって、この場合にも、 Alice は取れるだけ石を取るべきである。
初め単純に貪欲法っぽく書いて TLE。
これ、数字が３種類あるけど、３進数ではないんですよね。 でも、先頭に a, b のみがある部分に着目すると２進数ではある。 なので、2進数部分は２進数として処理して、最初に出現した文字が 'c' の時は素朴に処理するように書き換えたら、ACだった。
提出例： 33256230
…なんだけど、最初は 32-bit 整数溢れで WA になっていた。 桁数が 60 までなんだから、64-bit 整数使わなきゃってきづこうよ。 （解説見て書いたのも同じ間違いをしていて、それで気づいたという）
自分の解法は、解説のものに比べるとやや鈍臭いけど、普通に思いつけるものだと思う。
自分では、ここまでしか思いつかないかなと思って、解説を見てしまった。 ここでTLEになるのは、スター型の中心にいるようなノードばかりが呼ばれてしまうケースと考えられるので、一番次数の大きいノードだけ特別扱いしてやればよかった。
提出例： 33272979
実は、解説見てからなかなか AC にならなかったんだけど、引っ掛かってたのはここ：
// 次数が最大のノードだけ特別扱いする。
int maxsiz = -1;
int maxi = -1;
for (int i = 0; i < n; i++){
if (maxsiz < edges[i].size()){
maxsiz = edges[i].size();
maxi = i;
}
}
maxsiz < edges[i].size() のところで、符号ありなしを比較している旨の警告が出るのを無視していたんだけど、ここで -1 が size_t の最大値にキャストされてしまって、決して true にならないバグになっていた。
いかんね。
コンテスト本番では、最初 TLE x7 となってしまい、焦って不完全な高速化をやったけど TLE x2 残ってしまいダメだったやつ。
まず、高々長さ N の数列の繰り返しとなることは、見てすぐわかったのだけど （誰でも分かりそうだけど）、繰り返しの検出が雑すぎて入力例２すら通せず悩むのに時間を幾らか消費してしまったことが１つ目の反省点。
次に、X が大きい数になり得るので、尺取り法などを使わないと TLE になるだろうということに気づいていなくて、提出してから焦ってしまったのが２つ目の反省点。
提出例は、おととい TLE だったものをもとに修正したものなので、 はじめから見通していたら、もうちょっとスッキリ書けたのかなという気はする： 32986532
これは、以前似た問題が解けなかった経験があったのを覚えていたので、解けた： 32818990
えるでしゅしゅうだなと思いながら、普通に dijkstra 書いたら TLE。 それで★６なわけがないか。
解説にあるように、仮想的なノードを追加することで、全結合による辺の数を大幅に抑えることができる： 32819779
貪欲ではうまくいかなさそうだし…と飛ばしてしまったのだけど、もう少し良く考えればよかった。
なるべく大きな数字を得るためには、まず、桁数をより大きくしたい。 結果として得られる最大の桁数は、N を \(C_{min}\) で割れば得られる。
今度は、より上位により大きな数字（より大きなコストがかかる）を割り当ててやれば良いので、 残りの桁のために残しておかなければいけない費用を確保しつつ貪欲に割り当てていけば良い。
投稿例： 32798195
いっしゅん、部分列なら DP かしらと思ったりしたけど、実例を紙に書いて考えてみたらわかった。[l, r) 区間における最小の文字を探すのに、はじめ segtree を使って、それで AC だったんだけど、解説にあるような LUT を使うやり方も典型っぽいので、そちらでも投稿。
わかんなくて解説みた。解説見ても、いまいちピンとこなくて、書いてみてわかった感。
まず、最大や最小の問題はニブタンが使える場合が多いよ、という話。 この問題は、これにきづいてからも少々難しかった。 x 座標でソートして尺取り法ということなんだが、慣れていないと、さっとは書けないかも。
投稿例： 32162635
こちらは自力で解けた。一度 TLE 出してしまってから、そうかーと思って書き直し： 32164544
「部分列DP」を知らないとすごく難しく感じるのだけど、知っていると簡単かも。 知らなかったので諦めて解説をちょっとみた。 部分列DPの考え方はとてもシンプル。
異なる選び方でも結果的に同じ文字列になる場合は、それらを重複して数えないようにしないといけないわけだが、それがかなり簡単に実現できる。 つまり、同じ文字列になる選び方のうち、選ぶ位置の列の辞書順が最も若くなるものだけを選ぶようにすればいい。
実際にどうするかというと、dpで次の文字を選ぶ際に、同じ文字（例えば 'a'）が後ろに複数ある場合には、必ずいちばん前にあるものを選ぶようにすればいい。
今回の問題は、単純な「部分列DP」ではないが、その処理は次の文字を探し始める位置を変えるだけなので対処は簡単だった。
投稿例： 32112003
解き方が思いつかなくて焦った。順位表を見ると、かなり多くの人が解いているので、 ますます焦る。
あまりいい解き方ではないかもしれないけど、
を順に求めていく方法で解いた： 31870777
だけど、解説にあるように、こういう３つの数字の組み合わせ (i, j, k) を扱う時に、 j を全探索するのは典型的なパターンだったような気がする。気づかなかった： 31879128
※そういえば、「半分全列挙」というテクニックもあったな。本質的には、それと似ているかも。
※列を前から見ていくのと、後ろから見ていくのと、どっちがいいか両方考えてみようというのに加えて、３要素の時には真ん中に着目してみるという選択肢も持っておけということね。
参考：ここの「固定して考える」
もう一つの解説には、DP で解く方法も載っている。 本質的には、自分がやったのと似ているんじゃないかなぁと思うんだけど、 自分が悩みながら書いたものよりスマートそうなので、そちらも見ておこう。
この問題は、(i, j, k) を動かす解き方の方がスマートだなと思うけど、 DP の方は、選ぶ個数が一個増えて (i, j, k, l) の選び方の個数を求めよってされても解けると思うので、そういう意味では悪くはないかなぁ。
解けなかった。くやしい。
で、書いてみたのだが、何回か TLE を出してしまった。 ちゃんと正しい dijkstra をかけていなかったようだ。que に経路をプッシュする前に、 距離が緩和し、かつ、緩和される時のみプッシュしないといけなかったようだ： 31881525
以前、dijkstra で解けると思って書いたのに TLE だったのこれか。見直してみよう。 ⇨ ABC246E なんだけど、ちゃんとやってた*1。この問題は diijkstra では解けないやつだったのかな
今日も典型問題をやろうと思って、LIS (Longest Increasing Sequence) を。 これは蟻本の p.63 にある。すげー見事だ。
で、AtCoder の過去問で LIS をシンプルに扱っているのが ABC006D だったので、 これを解いた： 31769166
Euler Tour の典型問題。昨日蟻本や Web ページをいくつか見て Euler Tour と RMC (Range Minimum Query) で LCA を求める方法について学んだばっかりだったので、 すぐに書き方はわかったのだけど、ちょこちょこバグって書くのに時間かかってしまった。
これは、さらさらっと書けるようにしておきたい： 31751845
昨日は D 解けたのに惜しかったなぁという反省はあったものの、 レートを少し戻して、もうちょっとで水色復帰かなというところだったのですが…。
連日で挑戦した ARC140 は大惨敗でした！ はは。
いくつものミスがあって、120分かかっても通せなかった。 以下それぞれ反省点などを。大きく３つの反省ポイントがあった。
まず、今回も誤読して問題を難しく考えてしまっていた。
「T の先頭の文字を削除し末尾に追加する操作を任意の回数行うことによって作ることのできる文字列の種類数を求めてください。」
を、なぜか、
「T の先頭の『任意の数文字』を削除し末尾に追加する操作を任意の回数行うことによって作ることのできる文字列の種類数を求めてください。」
と誤読してた。こう誤読していても、結局のところ得られる文字列の種類は変化しないので、結局同じ問題を解くことになるのだけど、それに気づくための余分な時間を使ってしまった。
問題よく読もうよ、おれ。
次に、あるシフト幅に対して何文字変える必要があるのかを求めるときに、これは、 根本的な間違いをしてしまっていた。
例えば、abcabcabd のような文字列 3 シフトしても変わらないようにすることを考える。 これは、最後の一文字を c に変えて abcabcabc にしてやればいいわけだけど、 これを計算するのに、３文字ごとに abc, abc, abd ときった時のどれに揃えてやれば必要な変更回数を最小にできるかと求めてやればいいのかな、と。
これで、問題文にある例は全て解けるのだが、 これでは 8WA になってしまう 。
これは解説にある通り、M シフトの場合には M 箇所それぞれについて、最も出現回数の多いものをターゲットにすればいい。
最後の３つ目は、これもなぁ、我ながらへぼくていやんなるんですが、 頻度をカウントするための配列の初期化もれ。
最初の初期化もれバージョンはこれで、 手元では通っていた sample ですら WA していたので、これにはすぐ気づいた。 ローカルの配列は 0 初期化されるとは限らないよね、という。
で、何も考えずに（思考停止よくない！）初期化したバージョンが これ。
ちゃんとよく考えるべきですよね。M 箇所それぞれ正しくカウントするには、 M 回ループの先頭で初期化しなければならない。当たり前ですが！！（自分向けに強めに）
で、やっと通したコードがこれでした： 31747334
やれやれ
これ、100進3桁ともうちょっとだよね、という、解説にある通りの方針には比較的すぐ気づいたのだけど、 「や、そんなに簡単なはずないか」という思い込みも手伝って、問題を誤読してしまった。
この問題では、W 以下の全ての正整数が「良い整数」であればいいのだけど、 これを誤読して、これに加えて「W を超えるものは良い整数にはならない」という条件を勝手に自分で追加してしまって、悩みまくってしまっていた。
問題はよく読もう。
投稿コード： 31694717
昨日のコンテスト中も「なんかハッシュでも解けそうだな」と思ったものの、思っただけだったのと、ハッシュで解くほうが楽そうだったので、まずはそちらで書いてみた。
ここで使えるのは Zobrist Hash というやつ。 各要素に対応する乱数値（要素の値から、その値に対応する乱数値へのマップ）を用意しておいて、 部分集合に含まれる要素に対応する乱数値の XOR をとるというもの。 なんか聞いたことあるのは、将棋やチェスで使われるからかな。
XOR の性質より、計算結果が演算の順序に順序に依存しないので、今回のようなケースに使いやすい。
投稿コード： 31572105
上のコードは無駄なことしてたので書き直し： 31589302
当初思いついた通りのやり方で解けたのだけど、X == Y のケースでバグっていて手間取ってしまった。if 文の羅列を、つい、
if (a[i] > x) {
igtx = i;
} else if (a[i] == x){
ieqx = i;
} if (a[i] < y) {
ilty = i;
} if (a[i] == y){
ieqy = i;
}
と書いてしまったためだった。こう書くとバカみたいだけど。
なお、これは、解説、ユーザ解説いずれとも違う（ユーザ解説の方に近いかもしれないけど、解説の方がずっとうまい）。
まー、計算量からも解けるはずと思って、その通り解けたのだからいいのかもしれないけど、解説のやり方も確認しておこう。
方針はすぐに立って、その方針であっていたのだけど、WA 連発してしまった。
64-bit 整数でも溢れてしまう場合があるケースへの対処がうまくできなかったのが原因だったのだけど、対処したつもりでいたりしたので、的が絞れずに時間と手数を浪費してしまった。
対処法については、解説コードを確認しておこう。
まず、64-bit だと足りないなと気づいた時点で、さっと 128-bit 変数を使うという手があった。 中途半端な対策で WA 重ねて混乱するのでなく、最初からこうしておけばよかった的な： 31569819
また、解説にあるように、double で概算しておいて、概算値が long long に収まることを確認してから long long 値を使うなども可能： 31569965
コンテストで解けなかったもの。
最初に思いついたのが、指数の小さな \(B_0\) から順に求めていくやり方で、 途中で \(A_0 = 0\) になるケースが許されているのでマズいなと気づいたものの、 方針転換できずにドツボにハマった。
\(C_{M+N}\), \(A_N\) がいずれもゼロでないという制約があるので、指数の大きなものから求めていけばよかった。 気づきたかった： 30510010
普通に解けたけど、書くのに時間かかりすぎたかな。
ひさびさの AtCoder 練習。 少しだけ考えて解説を見てしまった。なるほど。 \(K_i\) の制約が小さいので、 これでいけるのね、と、dfs で実装。
・・・なのだけど、dfs でミスってデバッグに手間取ってしまった。 dfs ルーチンの中で、すでに到達済ノードだった場合に何もしない分岐は最初から入れてあったのだけど、呼び出しがわでもチェックして、先のノードが巡回済だったときには配列の追加をしないようにすべきだった。
dfs の書き方が自分の中で定まってなかったんだけど、読み出しもとの方で一つ先が巡回済みかどうかチェックするようにした方が安全なのかもしれないな。
ところで、ユーザ解説を見ると「オイラーツアー」なる用語が見える。
オイラーツアーでは、部分木クエリ、パスクエリ、LCA などができるらしい。あとで勉強しよう。
提出コード： 29774213