一問もACできず終了。残り30分ほどでBの解法が分かり、実装、提出してみたがTLE。その後、TLE解消方法に気付くも実装でミスってWAのまま終了。レートは落ちたけど、noSubしなかったのは良かったかなぁ……。
A - ABC Identity
解法ツイートなどは見たけど、概ね自力でAC。
文字列を三つに分ける、という解法はコンテスト中から考えていた。最初の1/3のうち、文字数が一番多いものを取ったらどうだろう……いや、それはできないか、などと考えていた。
大体の気持ちはそれで良いのだが、「一ヶ所の文字数を0にしよう」と考えるのがポイント。
三か所に分けていて、一ヶ所にAとBとCが含まれるので、計９個消さなくてはいけないが、ある箇所の文字数が0個になったとき、他の二か所も同じ文字数ずつ減ることを考えると、一ヶ所が一文字のみになったとき、他の二か所はその文字以外の二文字以下になっており、あとは二回で全て消せる。
そこまでは高々四回（＊）で消せるので、これで六回以下になる。
……ところで、実験するとこれで五回になっているみたい。
確かにそうなりそうだけれど、証明できない。
B - ABC Supremacy
ABCを0, 1, 2で置き換え、(S[i] - i) mod 3で考えれば分かりやすい！ と思いついたのは、コンテスト二時間以上経過してから。それも、この問題（類題かと思って見にいったがあまり似ていなかった）の解説の一行目に、「まず入力から1を引きます」と書いてあったため思いつけた模様。
その後、同じ数字三つ（つまり、元の問題の"ABC", "BCA", "CAB"）は自由に移動できると気付き、残ったものが一致するかどうかで判定すれば良いと気付いたのが30分前あたり。
そこからコードを書き、ランダムテストし、提出した……が、TLE。
ちゃんと計算量を見積もっていなかったのですね。焦っていたせいか、なぜか計算量は大丈夫という気持ちになっていました。
定数倍効率化するコードをいくつか投げ、その後ようやくどういうとき二乗になるかに気付く。これはdequeを使えば計算量改善できる、と気付いたのは終了五分ちょっと前。
時間が足りないか、と思いつつ書き直して提出したがWA。直せず終了。
同じ処理を二回やっていたのだけど、二回目のところで初期化忘れをしていたためWAが出ていた……と気付いたのはコンテスト終了後に冷静になってからでした。
0 件のコメント:
コメントを投稿