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 分で読むだけ読んだ。手つかずの山の数の偶奇と、お手つきの山の値の和の偶奇と、手つかずの山の値の偶奇を見て考えるのかなと思った。自分では考えられません。私の観測範囲の C の初学者、構造体で詰まる人が結構いる。でもってポインタは案外詰まらない。」■構造体で詰まるという詰まり方に興味がある。ポインタでは詰まらないという点に関連付けて想像してみる。C の前に他の Python みたいな言語になじみがあると、数値など不変型とオブジェクトなどの参照型はすでに知っているものと思う。ポインタは参照になぞらえて理解できる。構造体はオブジェクトになぞらえて理解できそう？ C にしかなくて戸惑うのは、不変ではなく参照でもないもの、malloc せずに存在している構造体ではないだろうか。これは自分の実感に基づいた想像で、Ruby に散々なじんだあとで C++ を触ると、変数のごつさにびびってしまう。スライシングみたいな罠にもなるやつ。詰まり方に興味があるというのは要するに、構造体を malloc して使うのは普通にできるんじゃないかと疑っている。
s[-1]=tt if !s.include?(tt) と帳尻を合わせている。自分はすごーく苦労して間違いながら回りくどい処理をした。提出 #62132900 (AC)。最後の文字を最初に取り分けてメインの上書き処理を通さなかったのがうまくなかった。あとから最後の文字だけ上書き処理をして、それによって余ったすでに上書きに使われていた T の文字が無駄にならないように玉突きで再利用を繰り返した。玉突きの適切なインデックスを求める 19 から 21 行目と 28 行目の find メソッドの条件がまあ間違いやすくて WA を２つ出した。N=M=5 程度の小さなランダムケースを作成して、スクリプトの解答と自分の解答(私はバイオコンピュータを内蔵しています)を突き合わせて NG ケースを探して見つけた。でもこの苦労は避けられたはずの無用な苦労だったと。■B 問題 XOR = MOD。A とほぼ同じ人数が通しているみたいだけど自分はこちらの方が解きやすかった(A 問題通されすぎ)。N を増やしながら愚直解を列挙してみれば、N=X が必ず最小の解として存在している。また、解の上限は 2N-1 らしい。N が２の冪乗のときにもっとも解が多く、区間内のすべてが解になる。そこを手がかりに前後の N の２進表現を考えてみると、０の数が答えの数(2.pow(０の数))を決めている。つまり、N の０だった桁が０か１に変化したものが X (決めつけ)。提出 #62134372 (AC)。K-1 のビットパターンを N の０のビットに埋め込む。■C 問題 A^n - 1。N+1 が素数だと解きやすい気がするんだけど、それだけ。こういう問題にアプローチする術(すべ)を持っていない。■D 問題 Moving Pieces on Graph。一応読んだだけ。基本的には最短経路+１本の辺があればコスト２を払って一方が待避することですれ違いができる。最短経路が部分的にでも２本に分岐していれば追加コストはいらない。もちろん全く共有辺を持たない最短経路が２本あるのでもいい。最短経路でなくても、+1 コストの経路には価値があるし、待避できる余分な辺がないならどんなコストであっても２番目の経路に価値がある(全体が輪っかのグラフを想像する)。どうやってコードにするかはわからない。コーディングだけが問題かもわからない。■D 問題。すごいケースがある。S と T が直線で通じていてそれ以外の迂回路がないとき、S または T から外部へ双方が待避して位置を入れ替えることができる。それはもう最短経路とか全く関係がない。■A、B がどちらも緑 diff だったらしい。ARC は怖いところだよ。緑落ち寸前の自分が解いているという事実に納得しかないけども。■■■D 問題に訪れた AtCoder 最高の瞬間。提出 #62153446 (WA×1/AC×63)。circle_like というケース名をヒントにランダムケースに傾向を与えてダメケースを探した。提出 #62154569 (AC)。補助なし時間制限ありでこんな問題解けるわけないよ(自分には)。正解を出力する他の人の AC プログラムを助けにしてデバッグに次ぐデバッグで数え切れないバグを潰してやっとこれ。■正解を知るのにこちらの提出 #62136607 をコンパイル(＆リンク)したものを使わせてもらっていたのだけど、ソースを読むと、変数 L と R を使ってささっと２つ目の最短経路を見つけている。どういうことか。それぞれ f(G,S) と f(G,T) に対応していることから S と T から BFS した結果かと思うのだけど(f 関数を読まない)、最短経路上にある各頂点について、一方(とりあえず S)からの距離をメモして、その距離に重複があれば迂回路があると判定できる？ 迂回路があるということは、S(または T) から等距離に異なる２つ以上の(最短経路を構成する)頂点が存在すること？ そうっぽいけどこれ当たり前にわかること？■自分がやったこと。S から BFS をしたあと T から後戻りすることで最短経路を１つ特定する。最短経路上の S を除く各頂点について、隣接頂点のうち最短経路にないものの S からの距離を調べる。自身の距離を d として、d-2 以下であることはありえない。d-1 である場合は、異なる最短経路が合流してきたことがわかる。d である場合は +1 コストの経路が合流してきている。d+1 の場合は、ここから分岐したのかもしれないし、+2 コストの経路が合流してきているのかもしれないけど、どちらの場合でも扱いは同じ。引き返してはいけないというルールがないので、分岐してすぐ戻ってくることで +2 コストの経路になる。S と T には特別な扱いが必要。S には合流してくる経路がなく分岐していく経路しかないので調べない(今は分岐路の合流点を調べている)。T に隣接する頂点で d+1 の距離を持つ頂点に注意が必要。さっき引き返してはいけないルールがないと書いたけど、T に限っては引き返す経路がすれ違いのための迂回路にならない。しかし +2 コストの本当の迂回路が合流してきている場合も考えられる。最初にやった S からの BFS を T で止めることでこの２つを区別できるようにした。これには +3 コスト以上の迂回路の合流を妨げない意味もある。あとは「すごいケース」への対応を追加でやる。WA×1 はこのケースへの対応がバグっていたせい。最初の１回の BFS 結果を流用するのをやめて、２回目３回目の BFS をすることで間違いがなくなった。たいへんすぎるよ。まずやるべきことがわからないし、やるべきことをやる方法がわからないし、正しくやるのも難しい。■■■『はじめての数論 原著第３版』を開いている。第21章は「法 p でのべき乗と原始根」というタイトル。C 問題は位数と原始根が前提知識として必要だったとわかる。そしてもちろんそれを知っているというだけで解けるなら問題にならない。(i-l)*(r-i) の簡単な式で数えられる。■自分のすべての提出。宿題が多すぎるんよ。D から精進でした。いつまで水色かわからんで。