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 問題は位数と原始根が前提知識として必要だったとわかる。そしてもちろんそれを知っているというだけで解けるなら問題にならない。