/(\d+)\s+\1\s+\1\s+/ というパターンを書いた。入力末尾の改行を保存しているので３番目が入力の末尾でもマッチするのでそこは罠ではない。罠というのは入力が "11 1 1" というケース。11 の末尾１桁だけを切り出してマッチしてはいけない。提出直前に気がついてテストしてパターンの先頭に \b を足した。\b は単語境界(\w と \s、\w と \W、\s と \S の間)にマッチするパターン。■B 問題 Card Pile。スタックが使えますかという問題。■C 問題 Buy Balls。かなり難しい。貪欲法でやろうとしたけど、どうやるべきか、本当に貪欲法でいいのか、すっきり答えが見通せなかった。黒より白の数が多くなってはいけない。だから基本的に黒を取ることにし、黒を取るときに同時に白を取るかどうかというオプションを考えることにした。それでいい？ 白が先になくなる場合、黒が先になくなる場合、黒が負でも白と併せて正なら取るべきか、そのとき併せるべき白は何か、処理順によって判断が変わってくることはないか、考えるだに貪欲法で大丈夫か不安が募る。よーく考えて提出して AC。10 分弱かけた。■D 問題 Minimum XOR Path。制約で難しさを出すのが定番の D 問題で愚直 DFS でもない順列総当たり O(N!) が通るのは甘々です。といって前にも１回「甘々です」と書いているので、前例がないわけではない。■F 問題 Rotated Inversions。E よりとっつきが良かったので F 問題から考えた。k=0...M につれて転倒数の変化を数えれば良い。変化はある要素が 0 に落ちるタイミングで起こる。自分は最初左にあって大きい要素の数と、右にあって小さい要素の数を使って変化量を数えようとした。答えが合わないから、左にあって小さい要素と右にあって小さい要素を使って数えてみたり、左にあって大きい要素と小さい要素と右にあって小さい要素を使って数えてみたりして、最終的に左右にあって大きい要素と小さい要素の数を使って数えて答えが合った。途中で何度か考え直していたんだけど、なかなか全体像が見えなくて答えを出すのに４つの変数が必要だとわからなかった。４変数のどれも答えを出すのに必要なんだけど、どこまで考慮すれば十分かはそれほど明らかでなく、目についた不十分な変数の組み合わせで答えを出そうとしていた。■E 問題 Min of Restricted Sum。数学問題に見えて実はグラフ問題であり、やれば答えが出る。つながっている要素間ではある要素のあるビットの 0/1 が決まれば他のすべての要素の 0/1 が決まる。0 の数と 1 の数を見て 0 にするか 1 にするかを決めればいい。どうやるか。UnionFind と BFS でやったけど、制限時間いっぱいの 2995 ms かかっていてこれは遅いらしい。時間内に Ruby で通している人たちはそれぞれ 660 ms、970 ms、1303 ms しかかけていない。提出が早いほど早いのには残酷な格差を見て取ってしまう。■コンテスト成績証。６問解けてないしあまり早くもなかったけど水パフォ上位で +12。前回から AtCoder がデレてきている。cs.sort_by!(&:size) cs というのは数値配列で、数値を size プロパティに基づいてソートするというのは、ほぼ何もソートしていないのに等しい。だって Bignum でなければ 32 ビット整数なら４、64 ビット整数なら８に決まっているのが数値の size だから。この間違いは過去にもやったことがある。単純に .sort と書くべきところで .sort_by と書いてしまったときに、つい選んでしまって疑問を持ちにくいのが .sort_by(&:size) なのだと思う。しょーもない間違いで貴重な得点を失ったものだ。■解法について書く。テキトーに根を選んで DFS をした。再帰関数の戻り値はアルカンの構成要素になり得る C または H の数。たとえば子がないなら自分自身を H と数えて１を返す。アルカンを構成しうる子が４つ(以上)あるなら、自分自身を C として中心に据えてアルカンを完成させて答えを更新する。アルカンを構成しうる子が１つでもあってそれが単純な H でないなら、自分自身を H として加えてアルカンを完成させて答えを更新する。アルカンを構成しうる子が３つ(以上)あるなら、自分自身を C として中心に据えてアルカンを構成しうる子であるとして親に返す。子が７つも８つもあっても選べるのは最大で４つまでなのだから、できるだけ数が大きい子を選ばないといけない。そのためのソートだったのだけど、ソートできていなかったので WA が出ていた。「アルカンを構成しうる子」というワードについて。実はすべての子がアルカンを構成する(その子を H とみなす)。最初に実装を始めたときには明らかでなかったので思わず条件があるみたいに書いてしまっただけ。
180000 = 50*60*60 だから……50 時間！ どうりで何日も終わらないはずだ。しかも GUI でやってたときは失敗するたび最初からやり直すしかなかったし。ARC=11_、ARCRA=1111_、ARCRARC=111111_、と並べていって、長さ 2n+1 の右端(+1)を除いて１にできると思ったらサンプルの１が理解できなかった。右端に０があるのに Yes なんだって。「SN+1=S1,SN+2=S2,AN+1=A1 とします」というループ条件を読んでいなかった。精確には読もうとしたけど理解できなくてそのまま忘れていた。だったら
ARCR=1111 を単位として長さ 4n はすべて１にできる。4n+1 と 4n+2 と 4n+3 がどうか。いろいろな挿入パターンを考えてみたけど、１が１個あれば ARCR=1111 の１つを AARCR=_1111 か ARCCR=11_11 に置き換えて、０に変えられないダブりの A(C) を元からの１に合わせて 4n+1 を Yes にできる。4n+3 はどうか。+3 を ARC=11_ とすれば２つまでは１に変えられるので、元からの１が１つでもあれば Yes にできる。4n+2 のケースがやっかい。さっき A か C をダブらせると書いたのには意味があって、R をダブらせると基本単位が壊れて ARRCR=___11 になってしまい２文字しか１に変えられなくなる。+2 は AAARCR=__1111 か ARCCCR=11__11 か AARCCR=_11_11 型にしたい。これら３つは R をダブらせて壊れた ARRCR=___11 にさらに +1 文字したものの上位互換になってるんじゃないかな。確かめてないけど。だからこの３つの型だけ考える(ローテーションできることを考えれば実質的に２つ)。型とはどういう意味か。ダブらせる A または C は同じ基本単位に属している必要がないということを意味している。元からの１の位置を４の剰余で分類して、A または C の位置関係にある２つの１が存在していれば長さ 4n+2 のどんな数列も１に変えられる。N=4n+2 に対する答えに全く自信がなかったのでまずはそれ以外のケースを実装して提出した。提出 #62607384 (RE×24/WA×1/AC×48)。結果を見ると、N=4n+2 型のケースが 24 ケースあり RE になっている。その他のケースは１つを除いて AC。３行目の N=3 のケースの条件が誤っている。N=3 は２つまで１に変えられる。それに N=3 は N=4n+3 に含まれるので意味のない場合分けだよ。答えやすいからとわざわざ N=3 だけ括りだしてそれで間違えてりゃ世話ないよ。続いての提出 #62608228 で無事 AC。問題の所在の切り分けができたおかげでスムーズにデバッグできたと思う。ペナルティ５分は安い。■C 問題 Range Sums 2。配点が同じ BCD を開いてみて C がインタラクティブだと見えたので C 問題しか読まなかった。インタラクティブ問題は総じて考える要素が控えめだとの偏見を持っている。つまり解きやすい。実装さえできれば AC できる。実際、この提出 #62614705 の冒頭にある３行のコメントが一番最初に書かれた部分なのであって、やることを明らかにしたあとで実装に取りかかったのだった。その実装に 50 分かかったんですけどね。s と Ps の関係とか頭がこんがらかってしかたがない。ABC ではないのでわからなくなるたびに立ち止まって慎重に整理してから実装を進めていった。■B 問題 Fennec VS. Snuke 2。残りの 15 分で読むだけ読んだ。手つかずの山の数の偶奇と、お手つきの山の値の和の偶奇と、手つかずの山の値の偶奇を見て考えるのかなと思った。自分では考えられません。