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 から精進でした。いつまで水色かわからんで。k = (b/p+1)/2)がまったく一筋縄ではいかなかった。他にもね、14 行目と 15 行目にある２つの式 k*k*p と (k+k+1)*p が似てるでしょ。自分の目には同じに見える。取り違えてもしかたないよね。それから、後半７行でやっているボーダーライン上のアイテムを買えるだけ買う処理だけど、これ単純に割り算で計算できるらしい。二分探索で求めたボーダーラインの意味を考えればその通りなんだけど、半信半疑になってしまうところがあると思う。■F 問題まで解ける問題が並んでいて、だけど時間内に解けたのは C 問題までってどういうことですか。最近の問題傾向のせいにしてもいいですか。自分は数字とか式を精密に扱うのはまったく苦手なので、たこ焼きに関する問題が解きたいです。文章で発想のヒントとなる過剰なディテールが与えられてるといいなあ。そして発想だけで解けるといいなあ。式変形とかまじ無理なんで、D と E が解けなかったのもそれが原因なので。■D 問題の早い人の提出を見てると、ループで１つの式の合計を求めて、４倍して１を足して答えにしていた (#61802287)。どういう見かたをすればそんなシンプルな理解に至れるのだろう。■F 問題に関連してセグメント木の max_right メソッドへの言及をいくつか見た。どうやらそれは前回の ABC388-F に関して自分が「セグメント木で解こうとすると、何をリクエストして何を得るかという検索インタフェイスがどうあるべきかがよくわからない」「懸案だった検索インタフェイスは左側の境界を与えて判定関数が true を返す区間の右端を探るメソッドということにした」(20250111) と書いていたメソッドそのものではないかという気がする。お名前いただきました。■E 問題。「制約を見たら M の上限が 10 の 18 乗だった。キューから M 回取り出そうとしたら TLE になるのは当たり前」とさっき書いた。AC までいった今だからわかるけど、キューから取り出す回数の上限は M 回ではない。(k+1)^2-k^2 = 2k+1 であることから、+1 個のコストは個数に比例して上がっていき、その和は２乗のオーダーになるから(Σk = n(n+1)/2)、取り出す回数は M の平方根である 10 の９乗に比例する。ていうかコストの定義が kkPi なのだからそれはそう。それでもやっぱり TLE になるように M の上限が 10 の 18 乗程度に定められている。■E 問題。ボーダーラインを求めてさらにボーダー上の境界に注目する問題としては PAST8-I「/2 and *3」を思い出す (#26574800)。知ってる問題だったんだよ。解法の枠組みが自明で、でも式変形が難しすぎた。$<.read か gets かの違いか？ ローカルでも遅いから再現性があるんだけど、何が悪いのかさっぱり。提出 #61608160 (AC / 256 ms)。配列の shift をやめて添字アクセスにしたら数十秒が数百ミリ秒になって AC になった。S という配列に対して shift したり []= で代入したりするのがどういうわけか遅くなるみたい。それが [] と []= の組み合わせだと大丈夫だと。これが S という配列に対してイテレータでループを回している最中の話だと因果が見えやすいけど、そうではない。この時間の差は Ruby 3.1、2.7、1.9、1.8 までさかのぼっても変わらなかったので、Ruby で最初の提出のような書き方をしてはいけないということを自分が知らなかっただけということになるのだけど、何度見てもまずさがわからないのがやばいと思う。一応書いておくと、Ruby の Array#shift は要素を前に詰める線形時間の操作ではないし、shift 操作が(配列の実データ共有を無効化する) copy on write を引き起こすこともない。……と書いて気がついたけど、[]= による代入が配列のコピー書き換えを引き起こしているのだな。自分には S という配列が１つあるだけにしか見えないから、書き換え前にコピーしなければいけない理由がわからないけど。shift には注意しよう。あ、問題について書いていない。各人が配る石がどのタイミングで尽きるかをメモしておいて、あとは決まった流れを再生する。■E 問題 Simultaneous Kagamimochi。上に乗せるおもちは小さい方から順番に選んでいくしかない。最初に間違えたのは、一度下にしたおもちを上に乗せるおもちに再利用してしまったこと。それで乗せ替えをしたりややこしいことをしてなんとか答えを合わせたけど、おもちを前半と後半に分けるともっとすっきり解けたのだろうか。■F 問題 Dangerous Sugoroku。黒マスブロックの前後に集中する BFS なのかなと思ったけど、いい具合に集中する手順が出て来なかった。■G 問題 Simultaneous Kagamimochi 2。セグメント木で連結を工夫して二分探索でできないかな。■E まで解いてまさかの緑パフォ。あまりにも厳しい。■■■精進。G 問題。セグメント木でどのセグメントをどのように連結して答えに近づいていくかを考えていたら、それってダブリングぽいなと思った。提出 #61669596 (AC / 503 Byte / 1728 ms)。セグメント木ではなくダブリング。たぶんメモリ使用量の点で、ざっくり要素数の２倍を使うセグメント木に対して、ダブリングのために要素数×log2(要素数)のサイズのデータを準備したのが不利だと思う。しかし 2 対 18 は定数倍の範囲。できあがったものは実装途中よりもシンプルになったけどすんごくややこしくて、バグはなかったけど寝る時間がなくなった。実はやってることは E 問題への提出 #61589354 とあまり変わらなくて、高速に乗せ替えをするためにセグメントごとに前計算をしたみたいな感じ。セグメントの連結というのが上のおもちと下のおもちがオーバーラップしないように乗せ替える操作にあたる。乗せ替えると何が起こるかというと、前計算で得ていた下に敷くおもちのインデックスが右にずれる。どれだけずれるかは添字との差だけから計算できる。E 問題を解くのにそんな回りくどいやり方をして時間を無駄にしていたのだった。ダブリングでなくセグメント木で解こうとすると、何をリクエストして何を得るかという検索インタフェイスがどうあるべきかがよくわからない(だから都合良くダブリングを採用した)。二分探索をセグメント木の外部に担わせると木の操作の log と合わせて log が２乗になってしまうけど、log は１つで済ませられるはずなので(実際そうだった)、セグメント木に探索を丸投げするために何をリクエストすればいいのか。汎用性(普遍性)のある問いとは何か。■セグメント木に乗せるのは下に敷くおもちのインデックスそのものではなくて、いくつ右かというオフセットにするのがいいらしい？ そうすると l+k+max(l...l+k)≦r で判定できる？ k を二分探索すると log が２乗になるので Ruby が許されるかどうか。提出 #61683769 (TLE×13/AC×33)。許されなかった。残念。もう AC があるので定数倍改善の意欲はありません。しかし、インデックスの代わりにオフセットを扱うだけでびっくりするほど簡単にセグメント木が利用できるようになるのだね。そういううまいやり方があるのは ABC371-F「Takahashi in Narrow Road」(20240914) のおかげで知っていたはずだけど。「FはまずXi←Xi-iとすることで条件を狭義単調増加から広義単調増加に書き換えておく。すると用事を完了するためには邪魔になる人もろとも目的の座標までずらせばよく、」(週記（2024/09/09-2024/09/15） - kotatsugameの日記)。他には ABC353-G「Merchant Takahashi」(20240511) も同じようなセグメント木の使い方をする。セグメント木ではないけど ARC120-C「Swaps 2」(20211022p01) も同じ発想で解く。以前はポテンシャルという勝手用語で説明していたけど、改めて共通点を探してみると、絶対相対変換という見かたができると思った。位置相対的な値をセグメント木に乗せても共通の土俵で比較することができなくて困るときは絶対的な値を乗せる。そしてややこしいことに逆のニーズもあって、今回の F がそうなんだけど、絶対座標が扱いにくくて相対値を乗せたいこともある。そういうテクニック。■ついに許された！ 提出 #61689758 (AC / 1030 Byte / 1837 ms)。セグメント木。定数倍ではなくオーダーを改善して log を１つにした。懸案だった検索インタフェイスは左側の境界を与えて判定関数が true を返す区間の右端を探るメソッドということにした。しかし 118 ms オーバーで惜しくも TLE (#61689533)。しかたがないので判定関数ではなく判定の閾値を引数にして判定処理を埋め込む苦肉の策でやっとの AC。苦しい。
@ を通過したあと . に書き換えた。■C 問題 Illuminate Buildings。難しかった。実装で２つ間違えてペナルティは４回出した。AC が出たのは終了５分前。２乗が通る制約だからと愚直に書いて、念のために最大ケースでテストしたら TLE になりそうだった。愚直というのは始点を固定して全ての間隔を試すというもの。よく考えると右側にある同じ要素を何度も参照するから２乗では済んでいない。そこで間隔を中心に考えることにした。１つおき、２つおき……の各数列について、同じ要素が最長でどれだけ続くかを数える。間隔が S なら長さが N/S 程度になる S 本の数列を考える。間隔の選び方がおよそ N 通りだからこれで O(N^2) になる。ここでも罠があって Array#values_at と Enumerable#chunk と Integer#step を組み合わせた解答が予想よりも時間を食っていた。Enumerable#each_cons には大きい数を引数にしたとき尺取りの計算量 O(N) では済まないらしい罠があると思ってるんだけど、ここにもあったのだろうか。手続き的に書き直して最初に提出するまでに 15 分かけた。そこからペナルティを重ねるんだけど、最後まで見つけられなかったバグは N=1 のケース。間隔に注目したせいで単一要素のケースが漏れて nil を出力していた。■D 問題 Santa Claus 2。どうやって計算量に対処するか悩む。たとえば BIT を使えば各行、各列のどこに家を置いて、どこから家を取り除くかは自在に(対数時間で)できる。あるいは行ごと列ごとに移動区間と家の並びのソート列があれば並行してスキャンしていくことができる。どちらも行データと列データに重複して登録される家を二重にカウントしないために同期が必要。これは行に基づいて得た訪問家リストと列に基づいて得た訪問家リストを最後に線形時間でマージして出力すれば良い。ということを考えてから必要なデータ(行ごと列ごとの移動区間)を集めて整理していった。そうすると家を中心にして考えたとき、行データと列データを参照して二分探索をするとその家が訪問されるかどうかがすぐに判断できるなと気がついて、後半の実装がちょっとだけ楽になった。BIT はいらないし、ソート列の並行スキャンもいらないし、答えのマージもいらない。ランタイムエラーでペナルティを１回出したのは N×N のグリッドを想定していたせい。D の提出をするときに C が WA になっているのに気がついて、C のデバッグをしているときに D が RE になって、C のデバッグを優先したけど結果的にデバッグしやすかったのは D だった。いっときは C をあきらめて E 問題を読んだほど。■E 問題 Snowflake Tree。木 DP かなと思って実装を始めたら親方向の情報が欲しくなって全方位木 DP だと気がついて、残り 10 分での実装をあきらめて C のデバッグに戻った。C は終了５分前に、E は終了 10 分後に AC。最も簡単なタイプの全方位木 DP だと思ったけど、もっと簡単に中心を全探索して間に合う計算量だったらしい。頂点数が N でそこから辿る辺の数が両方向で 2×(N-1) だから間に合う。しかし気付けない。だって解けるんだから。それで時間が足りてればね。■C のミスと D の重さにやられて E を通す時間がなかったのが悔やまれる。F はどれだけ時間があっても無理なので期待も諦めもない。