/ 最近 .rdf 追記 設定 本棚

脳log[2024-06-25~]



2024年06月25日 (火)

最終更新: 2024-07-12T00:35+0900

[AtCoder] JOI Open Contest 2024 過去問A - 試験 2 (Examination 2)

いつもの前置き:提出先は AtCoder だけど問題は AtCoder の作成ではなく JOI で、だけど競プロカテゴリを意図して AtCoder タグを付けています。

しんどかった。BC 問題を読むのは気が向いたときにして、A 問題についてだけ書く。

 どういう問題?

4種類の論理演算(! & ^ |)と、かっこと、ある値を境にして真偽が切り替わる関数から成る式の値について、クエリに答える問題。式の長さが 1M 文字以下で、クエリとして与えられる値の数が 200K 個以下。つまりどちらもとてもでかい。

 アイデア1:クエリの並び替え

クエリを昇順に並び替えたら、入力値との比較で真偽が決まる関数というのは、一度だけ false から true に値が切り替わる関数になる。更新頻度が (関数の数)×(クエリの数) から (関数の数) に減る。

 アイデア2:セグメント木みたいに関数の値の変化の影響範囲が対数レベルにならへんの?(願望)

以上の2つのアイデアというか願望に基づいて最初に書いたのが次の提出

 提出 #54709820 (RE/TLE/AC)

関数を class で置き換えて、そのクラスに演算子を定義して、式全体の評価を eval で行うお手軽な実装。

 RE の原因は Ruby が非ゼロの終了コードを返すこと

eval であるか *.rb ファイルを実行しているかに関係なく、大きな式を評価しようとすると Ruby は黙って異常終了する。式の形によっては終了する前に nesting too deep (SyntaxError) というエラーが出ることもある。p 1^1^1^1^1^...^1 という 1 か 0 を表示するスクリプトをコピペで膨らませて実行すると、Ruby のバージョンと Windows でのスタックサイズに左右されるんだろうけど、手元では 7 KiB を超える前に何も出力されなくなった。

 TLE の原因は、願望が現実ではなかったということ

両極端の例を挙げると、1+2+3+4+5+6+7 という式を [+ [+ [+ [+ [+ [+ 1 2] 3] 4] 5] 6] 7] と解釈するとき、(1+(2+(3+(4+(5+(6+7)))))) という式を [+ 1 [+ 2 [+ 3 [+ 4 [+ 5 [+ 6 7]]]]]] と解釈するとき、階層が直線的に増えていく。

 対策1:逆ポーランド記法

中置記法とかっこの存在が式の扱いを難しくしている。

変換アルゴリズムがうまく書けなかったので、検索してトップに出てきた「逆ポーランド記法入門2|中置記法から逆ポーランド記法への変換」というページを参考にした。

うまく書けなかった部分、求めていた答えがまさに「演算子を全てpopして」と与えられていて喜んだのだけど、あとになって答えが合わない原因が「全て」にあることがわかった。上のページで扱っている四則演算のように、演算子の優先順位が1位と2位の2つだけなら「全て」で正しい。それより多いなら、「これから入れようとする演算子よりも優先順位が高い演算子を pop できる限り全て」が正しい。日本語の説明と Python の実装例に齟齬はなかったので、日本語だけの問題ではないみたい。その一部分を除けば文章だけでアルゴリズムの全体像がイメージできるわかりやすい説明ではあった。

これで RE は解消するけど TLE はなくならない。むしろ eval を呼び出してインタープリタに丸投げすることができないぶん遅くなる。

 対策2(失敗):更新の伝播を下の階層から、更新を階層ごとにまとめて

例えば [1]^[2]^[3]^[4]^[5] という1つの式があって、クエリが 10 だったとする。最初は全ての関数が false で、クエリの昇順に true に切り替えていく。10 が最小のクエリなら、1 から 10 までの関数を順番に true に切り替えていくのだけど、その過程でこの式は false>true>false>true>false>true と値をチカチカ切り替えていく。もしこの式の全体が別の式の一部分であるなら、それら外側の式も同時に連鎖的に値を切り替えていくことになる。

更新の伝播を階層ごとに一旦ためておいて、深い階層から足並みを揃えて各項につき1度だけ値を更新しようとした。その過程で更新と更新が重なって更新が消えることも期待できる。ただまあ、これは根本的な解決策ではなく、効果がある入力もあるかもね、というレベルの対策にすぎなかった。TLE はなくならなかった。

 対策3(失敗):式を真ん中で半分に

演算子の優先順位を考慮して、| ^ & の順番で、もっとも真ん中にある演算子で分割する。

たとえば [1]&[2]&[3]&[4]&[5]&[6] という式なら [& ([1]&[2]&[3]) ([4]&[5]&[6])] と分割する。

たとえば [1]&[2]&[3]&[4]|[5]|[6] という式なら [| ([1]&[2]&[3]&[4]) ([5]|[6])] と分割する。

ところでこの分割は同一階層内でしかできないので、[1]&([2]&[3]&[4]&[5]&[6]) の分割結果は [& ([1]) ([2]&[3]&[4]&[5]&[6])] になる。かっこを無視して分割してしまうとあとでどうくっつけていいかわからないので。

かっこに制約されるということで、更新が影響する範囲を対数レベルに抑えて TLE を解消する助けにはならなかった。

 対策4(失敗):逆ポーランド記法の式を操作して同一演算をマージする

なぜか抵抗があって考えないようにしていたのだけど、TLE 続きでなりふりかまっていられなくなったので、結合法則を使う。実は対策3でももう使っている。

「なぜか」っていうか、左結合だと問題に明記されていたから、それを無視するのはずるであると、理性ではなく感情が訴えるのだ。答えが合いさえすれば何をしてもいいという教育は受けていない。たぶんそういう理由。問題の解釈が曖昧にならないように出題者が左結合だと定義するのはわかる。交換して答えが変わらないのを見抜いて利用するのが解答者だというのもわかる。だけど無意識が抵抗している。まあいいや。

中置記法の式はかっこがあってややこしいので逆ポーランド記法の式を操作する。

たとえば 1+2+3+4+5+6 を逆ポーランド記法に書き換えると、1 2 + 3 + 4 + 5 + 6 + になるのだけど、演算順序をいじって 1 2 3 4 5 6 + + + + + に書き換えたい。

そうすると何が嬉しいか。演算子に由来する階層を取り去って [+ ([1]) ([2]) ([3]) ([4]) ([5]) ([6])] と解釈することが容易になる。次にこれを6項演算として扱うこともできるし、2項演算のまま引数列を半分半分にしていくこともできる、半分半分にするということは、セグメント木のようにきれいで効率的な階層が作れるということ。

正しい方向に向かっていることを予感させるけど、1パスでやろうとして十分にマージできなかった。

たとえば次の式の書き換えを考える。1 2 + 3 + 4 5 6 + + +。参照範囲が限定できるので予め連続する演算子を結合しておくと便利。1 2 + 3 + 4 5 6 +++ になった。左から読んでいって最初の + 演算子に出合うとき、右の要素が被演算子(3)でその次の要素が + 演算子なら、順番を入れ替えて 1 2 3 ++ 4 5 6 +++ にできる。しかしこれ以上の結合ができない。被演算子もまとめておくとひとつ飛ばすだけで +++ にアクセスできる? だけど 4 という項は 2 2 * という演算子を含む3項として存在していることもありますね。

 対策5:逆ポーランド記法の式を解釈するときに同一演算をマージする

対策4とやりたいことは同じなんだけど、今度はうまくできた。演算子に行き当たったとき、スタックから取り出した2つの値(a, b)を即座に [op a b] としてスタックに戻すのではなく、ab が単独の値か何らかの演算の結果なのかを調べて可能ならマージして、できるだけ階層を増やさないようにした。そしてそれが最後でもなく、スタックから取り出されてまたマージされることもある。

 提出 #54933176 (AC / 2299 Byte / 1088 ms)

これの 92 行目から 107 行目のあたり。

2K オーバーの長大なスクリプトになってしまった。絶対もっと短く賢く書けるはずでしょ。

 ざっと読んだ


2024年06月24日 (月) セルフレジであたふたしてる年配者を見るにあの手の人々は「文字を読まない」ので文字情報は彼らには無力 - Togetter [トゥギャッター]」■何度も利用しているスーパーのセルフレジに言いたいことがあります。セルフレジに2種類あるのね。それぞれに、「こういうキャッシュレス決済が使えます」「キャッシュレス専用です。現金使えません」とか書いてある。一度間違えたからその次の機会に、どこに注意していれば間違えずに済んだかという観点で注意を払って観察してみたことがある。全然わからなかった。2種類のセルフレジは大きく左右のゾーンに分かれていて、待機場所も左右に隣り合った位置が別々に指定されている。レジと列に違いがあると知っていて、どちらに立つべきか注意して観察して、それで全然わからなかった。足下を見ても、左右に視線をやってレジまわりのポップを眺めても、判別できなかった。あとになって判明した理由は2つ。1つは、どこにも「現金が使えます」とは書かれていなかった。「現金が使えない」ことを知りたいんじゃないんだよ、しかもそれをレジ前で知っても遅いんだよ(これが2つ目の理由)。そして現金が使えないレジを見つけることは、現金が使えるレジを見つけることを助けはしない。現金が使えるかどうかわからないレジが存在しているだけなんだ。現金が使えないレジが現に存在しているのだから、これは自然に生じる疑いだと思いますがどうですか。あたふたする原因が導線の悪さにある例でした。スキャンを全部終わらせたあとで支払い方法の選択肢に現金がなかったんだよね(サポート店員さんがレシートを発行して現金可のレジに読み取らせることになった)。レジを区別するという注意コストを不特定の客に要求しているのだからこれはもうどうしようもない。ハードルがあるから越えられない人が出る。なくせないならせめて低くする仕組み作りを続けるしかない。


2024年06月22日 (土) [AtCoder] 今日はユニークビジョンプログラミングコンテスト2024 夏(AtCoder Beginner Contest 359)があった。F 問題まで解けたけどなぜか D 問題が解けない謎の回。ではふりかえり。■A 問題「Count Takahashi」。普通に Takahashi を探したけど、制約を読めば T を数えるだけでも良かったらしい。他の人の提出で知った。そうか、手の抜き方を見習わないといけないな。無駄にコンピューティングパワーを使ってしまった。■B 問題「Couples」。正規表現の先読みでやったけど、結構複雑で罠もあるパターンになったので(/\b(\d+)(?= \d+ \1\b)/)、普通に Array.each_cons(3).count{...} でやるのが良かった。■C 問題「Tile Distance 2」。数え方が ABC353-F Tile Distance と同じ。斜めを数えてから縦と横を数える。横移動のコスト計算が難しかった。目的地がタイルの右側か左側か判別してから、右と左のどちらから移動してくるのか場合分けをした。■D 問題「Avoid K Palindrome」。ABCDEF で一番難しかった。えっとね、まず否定で良い文字列を定義するのをやめてほしい(わがまま)。かなり長いあいだ勘違いしていた。何を数えたらいいのかまだわかっていない。長さ K の枠の中について回文があるとかないとかを数えるとするじゃない、でも枠の外を数えることができない。重複を省いてどうやって数えられるのか。■E 問題「Water Tank」。特別なデータ構造はいらない。スタックが1つと数を1つ覚えておくだけで答えが出せる。こういう単純な道具をこねこねする問題は好きだけど、前回の D 問題が灰 diff だったことを考えると、緑 diff どころか茶 diff があるかどうかもわからないと思う。高めに出てもそれは D 問題の壁があったからだよ。■F 問題「Tree Degree Optimization」。Ruby での他の人の提出を見ると、自分のよりずいぶんとシンプルで、自分には見えていない何かがあるのかなと思わされる。自分が考えたこと。各頂点が単独でばらばらに存在していて、(相手のいない)辺を1本伸ばしている。コストはその頂点の値(A)と現在の次数による。木を作るのだから、N-1 回、2本の辺を選んで繋ぐことを繰り返す。繋いだときにコストが発生して、それぞれの頂点からはまた新しい辺を生やす。辺を選ぶのにプライオリティキューを使ったけど、同じ連結成分から生える2本の辺を繋ぐことはできないので、単純にキューから2つ取り出して繋ぐというわけにはいかない。自分はキューを2本使った。1本目のキューにすべての辺を入れて、2本目のキューには最小コストの辺と、それと同じ連結成分の辺を入れた。そうすると2本のキューの最小同士を連結することでうまく処理が進む。だけど他の人の提出を見ると、キューは1本で足りるみたいなんだよね。どう考えるとそうできるのかわからない。■F 問題。次数の和が 2(N-1) になることを利用するのかな。キューには常に N 個の数を入れておいて、2つ取り出してコストを計算して、2つ戻す。自分の提出が無駄に複雑になったのは、個々の頂点の繋ぎ方を区別していたからだ。次数だけをカウントして繋ぎ方は考えないでおくと、シンプルになる。たぶんね。ほらね。提出 #54856675 (AC / 753 Byte / 562 ms)。ほらねじゃない。2つ取り出すのは嘘だった。1つずつ N-2 回取り出す。次数の和が 2(N-1) になるというだけでは条件が足りない気がした。各頂点の次数が最低でも1あるというのも条件なのかな。だから次数 N は予約済みとして、残りの N-2 をキューから引いた。■F 問題。tinsep19 さんのこの提出 #54855773 は個々の辺の繋ぎ方を考えつつもシンプル。木の問題の制約で自分が好きな形式があって、こういう形で親を定めるもの p2,p3,p4,...,pN (1≦pi<i)。これでどんな形の木も作れるんだよ。これと同じ考え方で処理を進めていてシンプルになっている。自分の考えが1つも2つも足りないのが明らかになっていくなあ。■F 問題。自分の最初の AC 提出には嘘があると思う。辺を繋いで、新しい辺をキューに追加するときに、2つ目のキューが空かどうかを確かめて適切なキューに追加するようにしないと、取り出し済みのコスト最小の辺と、2本目のキューに入っている同じ連結成分の2番目以降の辺の、コストの大小が入れ替わってしまうおそれがある。これは自分がキューのトップを参照するのではなく、とりあえず取り出してみた最小値を変数に保存して利用しているせいで生じているバグ。あぶないところだったなあ。■■■G 問題「Sum of Tree Distance」。全方位木 DP だと思ったら普通の木 DP だった。木 DP は DP の中でもやりやすい印象を持っている。積み上げの基礎となる葉の部分が最も単純でとっかかりとして好都合だからだと思う。その代わり子のマージに神経と時間を使う。提出 #54881518 (TLE×2 / AC×50)。2ケースダメでした。何が弱点だろう。メモリ消費と時間がだいたい比例している。メモリ消費は Hash かなと思うけど、どういう形の木だと無駄が増えるんだろう。単純に頂点数じゃあないんだよな。■精進。D 問題。X で ABC305-G Banned Substrings の簡易版だと読んだので、自分の提出 #42262239 をなんとか解読してそれっぽいものを書いた。提出 #54884526 (AC / 496 Byte / 147 ms)。おもしろいのは、っていうかやられたなって思うのは、入力文字列中の ? の出番がごく控えめなこと。力技で長さ N の良い文字列を構築していくにあたって、入力文字列中の AB はふるいとしての役割を果たしているのだけど、? というのは A でも B でもいいという意味だから、ふるいとして働かないことが機能なのだ。注目する部分が間違っていたし、プログラムの構成も全く予想していないものだった。■■■G 問題。朝のトイレでひらめいてしまった。マージテクのためにサイズでソートしてるんだけど、そのサイズって5とか3の固定だったりしませんか。帰ってからデバッグする。提出 #54896069 (AC / 839 Byte / 3169 ms)。通りました。まさかのマージテク失敗が TLE の原因だった。あれこれ考えることが多いと手癖にまかせて .sort_by(&:size) とか書いちゃうんだな。ところで、今確認したところ tinsep19 さんが G 問題を 528 ms で通している。同じ Ruby なのに桁が違うんだけど、何をどうやっているのか、知りたいが読んで知りたくはないんだな。■F 問題。「自分の最初の AC 提出 #54840376 には嘘があると思う」と書いた。実際に確認したところ、新しい辺を無条件に2番目のキューに入れていたので、懸念していたコストの逆転は起こらないはずだけど、代わりに「2つ目のキューが空かどうかを確かめて適切なキューに追加する」ことができていなかったことが明らかになった。これの何がまずいか。新しい辺を空っぽの2番目のキューに追加すると、そのキューから選ばれた辺が次に繋ぐ辺の一方として必ず使われるんだけど、これがコスト最小であるとは保証されない。1番目のキューから取り出されたものを2番目のキューに入れるからコスト最小が保証される。一方でこれが WA の原因にならない理由もわかってきた。どれか1つ任意の連結成分を選んで、これに属する辺を2番目のキューに入れると決めることでも N-1 回の操作で木を構成することができる。自分は UnionFind を使っていながら、ミスによって UnionFind による連結成分の管理を必要としない木の構成法を実行していた。なんだかなあ。考えが2つ足りず(次数への着目、インクリメンタルな木の構成法)、実装ミスをし(追加するキューの選定)、ミスしたと勘違いをしていた(IMKK)。素直に F 問題の AC を喜ばせてはくれないのか。


2024年06月21日 (金) X で見かけた。「階段を1段もしくは2段ずつ上るときに、ある段に至る上り方はフィボナッチ数になる」らしい。えっそうなんだって新鮮な驚きだったよね。DP の遷移から漸化式を見ようとしたことがなかった。2次元以上になるとまた何も見えなくなるんだけども。


2024年06月15日 (土) [AtCoder] 今日は CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358) があった。良くないできではあるがしかたがないというあきらめもある。F 問題はどうにもならない。ではふりかえりを。■A 問題「Welcome to AtCoder Land」。比較します。「空白」を 0x20、改行を 0x0A だと決め打ってもいいよね。しなくていい split はしない。■B 問題「Ticket Counter」。前の人から順番にシミュレートすれば答えになる。■C 問題「Popcorn」。制約が小さいので組み合わせる数を決め打ってから全組み合わせを試した。考えなくていいので隙あらば全探索。またの名を総当たり、ブルートフォース。■D 問題「Souvenirs」。スーヴェニール? ou をウと読ませるのはおフランスっぽい。ジュルナリステン、カムフラージュ、ウイノン…………以上! つい最近までこれがお土産だとは知らなかったので、なのにお土産っぽい雰囲気がしたので、こういう名前の問題があったのだとわかる。思わず問題名に2って付いてないか確かめた。日記を書いている今調べたら、該当する過去問は ABC286-E Souvenir であり、あちらは単数形、こちらは複数形という違いがあったのだった。まあいいや。値段と個数を1つのパラメータで決めてしまうってなかなかおかしいね。二度見した。要求を下回らない限り最も安いものを選べばよい。B の昇順に処理を進めるなら A も昇順にスキャンするだけで済む。B の降順だとそうはいかないし、正当性にも不安が生じる(実際には問題ない気がする)。■E 問題「Alphabet Tiles」。問題を勘違いしていて解法が間違った枝に入り込んでしまって余計な時間を使った。どこに分岐路があったか。作る文字列は長さ K に限らず、1以上 K 以下であれば良いのだった。最初の間違った解法は、K 文字のうち k 文字が確定している場合の数を文字種ごとに数え上げていく DP だった。長さ K の答えは合っていたけどその他の長さは合わない。長さ K の答えは合っていたので、同じ方法を K 回繰り返すだけで答えが出るのはわかる。しかしこれはまともな時間で完了しなかった。1から K までの一連のプロセスを通じてそれぞれの答えを見つけなければいけない。インクリメンタルに答えを出していかなければ間に合わない。そうすると必然的に DP で持つべき状態が決まる。あとは状態と状態をつなぐ遷移がどうなるか。しばらく悩んで見つけた次の解法は、k 文字が確定しているときにある文字を1から c 文字まで挿入して k+1 から k+c の文字列を作る DP。答えは合ったけどローカルで 30 秒以上かかる。自分の PC で 16 秒だったら2秒制限でも AC になるのは ARC179-B の精進でわかっている(20240602)。システムを HDD から SSD に移し替えたときにジャッジサーバーとの速度差が2倍程度に追いついたのだけど、最後の言語アップデート以来、えっと、8倍に広がったの? 30 分以上高速化に費やして結局 AC までに1時間ちかくかけた。厳しい。何をやったか。コンビネーションの前計算をして、それだけでなく共通項をループの外に括りだして掛け算の回数を減らしたり、DP 配列の複製を抑制して in-place で値の更新ができるように処理順を入れ替えたりした。それでもコードテストで 3.5 秒だったり 2.5 秒はかかる。AC 提出は #54600449 なのだけど、最後の決め手は 20 行目の %P の位置だった。3項の掛け算のあとに %P をくっつけていたのを前にずらして2項の掛け算にするだけで2秒オーバーが1秒未満になった。Ruby にはオーバーフローがないからついテキトーに %P を付けたり省いたりしてしまうんだけど(%P が多すぎても少なすぎても TLE の原因になるのだ)、同じ1回の %P でも位置によって効果がだいぶ違うんだなあ。■F 問題「Easiest Maze」。出力形式難しすぎ。そして問題文が間違っていた。「壁があるときに辺で結ばれていて、長さ K の唯一のパスを構築する(大きさ K の連結成分では十分ではなく、塊やループや3つ以上の端点があってはいけない)」というのでは壁の既成概念が崩壊する。質問と訂正があるのを待つことにして A 問題からの実装を始めることにした。終了の 25 分前に戻ってきたら問題文の修正は終わっていたが、差分を調べるのが面倒で読まなかった。すること自体は難しくなさそうに見えてやりきるのはすごく難しいかも。自分の頭で考えて答えを構築するなら、縦と横の偶奇の扱いがやっかい。だったら機械に長さ K のパスを探索させれば何も考えなくていい。100×100 というのが素朴な DFS にとってどれだけの規模感なのかよくわからない。やばいとは思う。マスの埋まり具合と現在位置でメモ化してもどうか。2、3日前に読んでいた『競技プログラマー ハンドブック』(PDF) で紹介されていた枝刈り手法が使えそう。壁にぶつかって左右に進路が分かれるとき、ゴールがない方の進路に答えはない。なんにせよ時間がなかった。■精進。G 問題「AtCoder Tour」。F より低い青 diff なのを見たので問題を読んだ。現在のマスが終着点だと仮定したときの想定楽しさを元にした BFS でできそう。提出 #54618901 (AC / 413 Byte / 480 ms)。できた。こんな腑抜けた G 問題を置かれると、目の前の問題を解く以外のことを考えさせられてめんどうくさいんだよなあ。■■■精進。F 問題。やっぱりね、「すること自体は難しくなさそうに見えてやりきるのはすごく難しい」。何をするかって、ぐねぐね左右に線を引いて、ラスト2行の帰り道では縦にぐねぐね線を引いて、それをフォーマットして出力する。がんばってやる! 提出 #54644107 (AC / 1676 Byte / 51 ms)。右へ線を引く、下に移動する、左へ線を引く、ぐねぐねしながら左へ線を引く、と関数を分けることで、同時に1つのことだけを考えればいいようにした。文字列化するのも、行を出力する関数と行間を出力する関数に分けて、同時に1つのことだけを考えるようにした。もーたいへん。縦横の偶奇と K の偶奇は調べなかった。予め達成可否を判定することはせずに(できませんから!)、やるべきことをやった結果ゴールにたどり着いているかどうかで判断をした。これは ABC347-D の反省から(「RE/WA を出した方では、不可能なケースを最初に判定するようにしていた。一方の AC 提出の方では、操作をしたあとで、結果が満足しているかどうかで出力を切り替えた。要するに、不可能なケースの判定に漏れがあったのだ」)。■■■F 問題のジャッジがザルだったらしい。まあ、あの大作の出力形式を整えて提出しただけで評価されてもいいよ。■G 問題。「現在のマスが終着点だと仮定したときの想定楽しさを元にした BFS でできそう」について書く。まず、待機するマスは必ずパスの末尾になる。最適を目指すとそうなる。パスがあって長さが決まっていて、残りのターンを費やすのは報酬が最大のマスに決まっている。それがパスの途中にあるとするなら、そのマス以降のパスが蛇足だったということになる。移動を省いてそのターンも待機に費やした方が良い。だから待機マスは必ずパスの末尾になる。▐あるマスに到着したときのことを考える。関心事はそのマスを最終地点とした場合のスコアだから、到着時点での残りターンを報酬に変換してスコアを比較する。スコアがすでに記録されているスコアと同じか下回っている場合は探索を打ち切って良い。なぜか。パスを伸ばす目的というのはより良い待機報酬を求めることにあるのだから、あとから訪れていて残りターン数が少ない探索の枝はそれだけでビハインドを背負っている。それなのにパスに依存したスコアが余分に費やしたターン数に見劣りしているというのだから、これ以上の探索で先達より良いスコアを得る可能性はない。▐もう全部書いた? 提出したあとになって問題があると不安になって、でも実は問題がなかったことがある。BFS で t ターン目の処理をしているときに、隣接マスを t+1 ターン目のキューに入れると同時に t+1 ターン目の状態をその隣接マスに書き込んでいる。このあとさらに t ターン目の処理を進めているときに、さっき t+1 ターン目のキューに追加したマスが出てきてしまったら、t+1 ターン目の状態に基づいて t ターン目の処理をすることになるのではないかと考えた。でもチェス盤を考えるとわかるんだけど、t ターン目のキューと t+1 ターン目のキューに同時に入るマスは存在しないのだった。うまくできてるんだなあ。今までそれを知らずにグリッド BFS を書いてたんだぜ。■■■D 問題。B の降順だと A をスキャンするだけでは済まないみたいなことを書いたけど、具体的には二分探索と中間位置からの効率的な削除が必要だと、平衡二分探索木みたいなものが必要だと思っていたけど、そんなことはなかった。昇順でも降順でも線形時間でソート部分の O(NlogN) で解ける。B の降順に処理を進める場合にはスタックを新しく1本用意する必要があるが、それだけでよかった。提出 #54693460 (AC / 降順)。だけどあえて降順ソートをするより素直に昇順に処理をする方が簡単。提出 #54576260 (AC / 昇順)。■G 問題。ダイクストラ法とのツイート(?)を読んだのでプライオリティキューを使う方法を考えた。グリッドが小さいから BFS でも大丈夫だと思ったし実際大丈夫だったけど、BFS だと後追い更新が続くとターンが進んでもキューが短くならないんだよね。提出 #54698671 (AC / 1132 Byte / 124 ms / 58 ms)。プライオリティキュー由来の log が付いても 480 ms より速くなった。ちょっと意外。しかも 124 ms というのはテストケース1つ目に特異的なタイムに見えるので、実質的には2番目に遅い 58 ms が最悪タイムだと見ていいと思う。爆速。キューにはグリッドのマスと同じ数だけ K ターン待機した場合のスコアを入れた。ゴールからスタート地点を目指す。移動するごとに決まったスコア(ゴール地点の待機報酬)を引き現在位置の報酬を足していく。最初にスタート地点に到達したときのスコアが答え。負の辺とかは知らない。ダイクストラ法を1回だけやっている。


2024年06月14日 (金) PS5 のシステムソフトウェアアップデートについて。QR コードをスキャンするとアップデートの詳細がわかります、じゃねーんだよ。まじで、アップデートする気が起こらない。今日もそのまま電源を切った。詳細が知られると不都合があるのかと勘ぐりたくなるほど、愚かなやり方だと思う。テキストで詳細な内容を提示するのが一番(従来はこうだった)。内蔵ブラウザで表示できるようにリンクと URL を提示するのが二番。エンコードされた記号をその他のデバイスで読み取らせるのは論外。


2024年06月13日 (木) UTF-8 の BOM について - 将棋プログラミング」■ブコメに「WindowsはなぜBOMをつけたがるのか」とあった。自分も同じように感じていて、UTF-8 の BOM を目障りに思っていたけど、Excel で未だに「ANSI」エンコーディングが意味を持っていることを知ると、「すべての」コードページと共存しつつ互換性を破壊しないための、もっともリーズナブルな手段なのかなと、考えないではない。CP932 以外のことはさっぱり知りませんけども。たぶん、コードページを UTF-8 (65001) に切り替えるのがユーザーの望みというわけではないのだと思う。二者択一では満足できないもの。


2024年06月08日 (土) [AtCoder] 今日はサントリープログラミングコンテスト2024(AtCoder Beginner Contest 357)があった。F 問題が解けず、問題の理解があやふやで早解きも失敗し、冴えない結果だった(確認はしていない)。以下ふりかえりを。■A 問題「Sanitize Hands」。シミュレートして使用後の残量が負でない人数。境界を探そうとすると1差で間違えそうで怖い。手のない宇宙人が紛れていると話がややこしくなるんだけど、そういう面倒がない 1≦H という制約だった。■B 問題「Uppercase and Lowercase」。やります。ASCII の6ビット目を数えるという猪口才な判定法。■C 問題「Sierpinski carpet」。今日のつまずきはここから。再帰関数でやろうかクラスでやろうか文字列操作でやろうかいつまでも迷っていた。結局文字列配列を敷き詰めて拡張していく操作が簡単で短かったが、15 分かけた。■D 問題「88888888」。まず勘違い。与えられる N が整数型に収まらないサイズだと勘違いしていた。文字列として各桁を扱わなければいけないのだと思って解いていた。求めるものは初項、公比、項数が明らかな等比級数なのだけど、項数が mod 998244353 だとサンプル3の答えが合わない。Integer Sequence Fair を解いたこと(20230327)が糧になっていない。mod をそのまま指数にはできない。で、繰り返し二乗法を自分で実装しなければいけないのかと思って N が何ビットになるのか確かめたら、60 ビットで足りるようだった。なんだよー。公式に3数を当てはめるだけのことに 20 分かけた。■E 問題「Reachability in Functional Graph」。これも勘違いがひどかった。N 頂点 N 辺だというから、輪っかが1つのなもりグラフなのだと思って解き始めたのだけど、このグラフは連結でも単純でもなかった。サンプル1に言及があったのだけど、自己辺がある。それではと複数のループとループに繋がる毛が生えているグラフを想像してサイクルと直線を検出する関数を書き始めたのだけど、サンプルの3が合わない。枝毛の可能性を考慮していなかったせい。問題文の最後にわざわざ「特に、u=v の時は常に到達可能です」と書いてあるのも読み飛ばしていてカウント漏れがあったし、もう散々だった。およそ 40 分かけて変な関数を書いた>提出 #54372312 (AC / 316 Byte / 227 ms)。順方向と逆方向の DFS を2回やるらしい強連結成分分解をそらで書くことがまだできないので、変な関数を発明しがち。出次数がすべて1だという条件があるから、強連結成分分解はオーバーキルなのだと思う(だから変な関数で解ける)。■自分のすべての提出。■■■C 問題。再帰バージョン。提出 #54407583 (AC / 276 Byte / 138 ms)。結局のところ実装の方針に迷っていたというのは、どの方針にしろ実装を最後まで見通せなかったために二の足を踏んでいたということなのだろう。実装力が足りない。■■■級数という言葉について。ちょっと検索したら、級数というと普通は無限項の和を表すみたい。特定の範囲を除いて0と定義することで有限個の和を表すこともできて、そうでないことを示すために無限級数という言葉も使われるけど、基本的に無限個の和なんだって。「級数」(ja.wikipedia.org)。そうかー。等比数列の和って言わないとだめなんか。長ったらしいなあ。てっきり、並べたものが数列で、並べて足すものが級数なんだと思ってた。


2024年06月07日 (金) [AtCoder] 「生成AIの台頭に伴うABCにおけるルール変更について - AtCoder」■なんの補完も整形も行わないテキストエディタしか使わない自分には関係ないかなと思っていたら「AtCoderの開催中のコンテストの問題として発信されている情報の全部または一部を、ソフトウェアに入力として与える行為を禁止します。問題文をコピーした文章・スクリーンショットなどが該当します。提出するソースコードを書くためのエディタも、この制限に該当します。」と書いてあって、完全には無関係ではなかった。エディタも例外ではなかった(想定は VSCode みたいな Copilot 付き高機能エディタらしいけど)。とはいえ、自然言語の問題文をコピペする機会はこれまでなかった。定数や出力用文字列は「問題文で与えられる固有の整数や固有名詞などの文字列は、任意の場合においてコピーが許されます。998244353などの問題文で与えられる数値、「Takahashi」、「Aoki」などの文字列等。「Monday」などの曜日や、問題文で与えられる数列などは許可されます。」と例外として許可されていた。自分は自分の注意力や指や目を全く信じていないので、Aoki と4文字タイプするのも避けてコピペしたいタイプなのであって、許可されていて良かった。最近はもう積み重なった慣例を疑う理由もないので、グリッド問題で ox をコピペするのはやめてしまったけど、字形と文字コードの繋がりって不確かだよね。GitHub やブログに貼り付けられたソースコード片において、円マークに見えるものが 0x5C ではなく 0xA5 だったせいで壊れていたケースを複数回見かけている。タイポを避けるためにコピペしたいし、見た目ではなく文字コードに基づいて入力するためにもコピペしたい。話がそれた。他に注意が必要な点はなかった。


2024年06月06日 (木) 【悲報】日本人の民度、ガチで悪くなっていた… : 暇人\(^o^)/速報 - ライブドアブログ■これのコメント欄に「ハザードたいて路肩に一時停車するだけ」とあって、実際そういう対応を見かけることは多いのだけど、自分はそういう対応を教習所で習った覚えがない。ハザードをつけるのは害がないと思う。だけどつけろと習った覚えはない。交差点には進入できない。だから交差点に進入しないために停車することはあると思う。だけど、直線で路肩に寄って停止するのは、あまり良くない対応だと思っている。なぜか。車というのは横に寄せるためにも前進しなければいけないのであって、たとえば救急車が後方から接近しているときに、前の方にある車がそそくさと停止してしまうと、後ろにいけばいくほど前進余地が少なくなって横に寄せることができなくなる。ウチの県は1号線であっても片側1車線なので、救急車もその周辺もにっちもさっちもいかなくなる。■「緊急車両(緊急自動車)が近づいてきたときの道の譲り方や進行妨害した場合の罰則 | クルマ情報サイトーGAZOO.com」 「緊急車両 対応」で検索して出てきたこのページの「3.緊急車両に対する道路交通法での義務」に条文の抜粋がある。前段が交差点付近の対応で、左側に(場合によっては右側に)寄せて一時停止せよと書いてある。後段がそれ以外の場所での対応で、左に(もしくは前段同様右に)寄せて譲れと書いてある。次節(4項目目)記事本文には停車せよと書いてあるから、あえて条文部分を参考にした。「譲る」を日常語として理解してはいけない可能性? でも前段との比較によっても一時停止までは求められていないと判断できる。もちろんしてはいけないとも書かれていないのだけど、あまりいい考えじゃないんじゃないかなあというのが自分の意見。前が止まれば止まるしかないけど、寄せて減速はしても率先して止まりはしないというのが自分の対応。■左に寄せるときはまずミラーを見て二輪を挟まないように注意します。


2024年06月02日 (日) [AtCoder] 今日は AtCoder Regular Contest 179 があった。結果が見たいような見たくないような気がするけど、どちらにしろまだ出ていないだろうからまずはふりかえり。■A 問題「Partition」。サンプル1の出力例が壊れていましたね。解説文と食い違っていた。サンプルの2がなんで No になるのか考え込んでしまった。Yes だよね、「(Yi​<K かつ Yj​≥K) ならば i<j が成り立つ」という型の命題は、前提が成り立たないときは常に真だよね、誰か質問しないかなと考えていた。そのうちに問題文を何回目かに読み返していたときに気がついたんだけど、累積和の初項が必ず0だから、その時点で K 以上の値が出現してしまっている場合があるのだね。K が0以下の場合とそれ以外で場合分け。ここではあっさり書いたけど、境界値が 0 なのか -1 なのか 1 なのかでもじっくり考え込んでしまった。基本的には Yes でソート列が答えになる。判断が分かれるときは正の和と負の和の絶対値の差と K を比較する。ここでも不等号にイコールが付くかどうかをじっくり考えてしまった。なんなら最初に戻って場合分けの条件から考え直している。これが自分の脳みそに収まるぎりぎりのサイズの問題です。■B 問題「Between B and B」。ある文字が要求されているいないの状態が 1<<M あって、これを N 文字分繰り返す DP をするのだと思った。実は最後の文字が何であったかを区別しようとしていて、そうすると1億ステップの処理になって TLE なのではないかと思ったけど、区別しないなら 1000 万なので間に合いそう。どちらにしろ数字合わせができなくて TLE かどうか以前の問題だった。■C 問題「Beware of Overflow」。個別の値の絶対値が R 以下ですよ、値の合計の絶対値も R 以下ですよ、二項間の比較と加算を駆使してどの瞬間どの値も絶対値が R を超えないようにうまい順番で全体を1つの値にまとめましょうね、という問題。最初はソートしてから先頭と末尾の加算を繰り返せばいいかと思った。ソート列を真ん中で折り返して加算するので、1回のイテレーションで全長がおよそ半分になる。だいたい答えは合っていたけど、3ケースだけ WA だった(#54171399)。どういうケースで良くないかというと、-R,-R,-R,2,2,R-1,R-1,R-1 みたいな場合? R=3 だとすると 2+2 をしてはいけない。改良版では、加算した結果を二分探索で適切な位置に挿入することで常にソート済みの状態を保ちながら、最大値と最小値の加算を繰り返すことにした。提出 #54175146 (AC / 442 Byte / 177 ms)。■水パフォで喜べないって悲しいね。わざわざ確かめないけどね。自分の想像では ARC、ABC、ABC、ARC と下げが続いている。■■■D 問題「Portable Gate」。Ruby で挑戦している人がいたのでまずは問題を読んでみた。全方位木 DP? ゲートを置く場合と置かない場合のコストを積み上げていくのかと思って実装を始めたけど、どうもそれではいけない。始点に帰ってくる必要がないのだ。最後に選んだ辺へは行きっぱなしでいい。そうすると、ゲートを置かずに帰還する場合のコスト、ゲートを置いて帰還する場合のコスト、帰還しない場合のコスト(※ゲートを置く置かないは呼び出し元に影響しないので置けばよい)の3つを考える必要があるのかなと考えたところでギブアップ。知力を振り絞るためには頭の良さだけではダメで外国で冬の海に飛び込めるくらいの体力が必要らしいですよ(もちろんそんな体力もエネルギーもないのでさっさと投げ出しちゃいます)。■通った!!! 提出 #54283484 (AC / 1521 Byte / 1758 ms)。びっくりマークを3つ付けてもいいでしょう。たいへんだった。寝る前に数時間がかりで慎重にコーディングをしたら、ちょっとしたシンタックスエラーを2つ直しただけでサンプルが通って、あとのミスは親方向の深さを計算するときに +1 するのを忘れていたことだけだった(37 行目と 50 行目。子供から見て兄弟は最も近くに見えて2親等だという話)。結局考えるべきは先に挙げた3つに加えて、(ゲートを使わないで)帰還する場合と帰還しない場合の差分として最も遠い子孫との距離を記録した。この問題ならではのフックがありました。全方位木 DP の手順として、全体から子を引いてそれを親方向のパラメータとして子に与える必要があるんだけど、パラメータの計算に最大値(最小値)を使っている部分がある。つまり、複数の子があるときに、1つの子については帰還する必要がないけど、他の子についてはすべてを黒に塗ったあとで戻ってくる必要があって、その選択に最大値(最小値)を使っているんだけど、子の影響を全体から差し引くときに最大値(最小値)が利用できなくなる場合がある(その子がまさしく最大値(最小値)だった場合)。こういうときのトップ2戦略は過去2回の経験がある(20240302)。どうですかね、もっとシンプルに解ける考え方があるんですかね。選び方次第でパラメータが減らせる可能性はあるかな。全方位木 DP というだけでたいへんなのに、それに輪をかけてたいへんだった。パラメータが4つあってそのうち2つでトップ2戦略を使った。最後に補足。ゲートを使う使わないを辺ごとに独立に選んでいい理由は、ゲートを使わずに網羅して帰還する辺を、ゲートを使って網羅して帰還する辺より先に選んだことにすればいいから(そして最後が帰還しない辺)。■■■B 問題。提出 #54413597 (AC / 433 Byte / 1544 ms)。すでに散々悩んだあとで頭の中が整理されていたからか、フツーに普通の DP だった。日記に「ある文字が要求されているいないの状態が 1<<M あって、これを N 文字分繰り返す DP をするのだと思った」と書いたことは忘れていて、ブロックされている文字にビットを立てる DP をした。それで良かったけれど時間が厳しい。3重ループになるのだけど、N のループの中で 1<<M のループの中で M のループを回すとコードテストで 10 秒弱かかった。制限は特に長めでもない2秒。ここで ABC356-D Masked Popcount の解法のひとつ、ビットごとに 0 と 1 の出現サイクルを利用するものを思い出した。ビットごとに 0 または 1 だとわかっている数についてだけループを回すなら、3重ループの最奧でビットが立っているかどうかの判定をしなくて済むし、ループの回数も半分になる。そのためにはループの順番を変えて、N のループの中で M のループの中で 1<<M のループを回す。遷移はビット演算が2つ。ある文字を置いた結果その文字自身をブロックし、そののちいくつかの文字のブロックを解除する。■同じく B 問題。提出 #54414039 (AC / 796 Byte / 1628 ms)。Ruby による B 問題へのすべての提出を見ると Akiyah さんが 2047 ms で AC まで一番近づいていた>#54319004。お楽しみを奪ってしまったとしたら申し訳ないのだけど、速くなりそうな部分があったのでそこを修正したものが冒頭の提出。具体的には ns.sum{|n| dp[n] }dp.values_at(*ns).sum に変更したら 20 % くらい速くなって AC になった。インタープリタ型の言語は、できるだけ短い指示で多くの仕事をコンパイル済みのネイティブコードにやってもらうのが良い。ちなみに TLE を避ける工夫は自分のものとは異なっていて、1<<M 通りの遷移先をビット演算で N×M 回求める代わりに前計算をして、遷移先ごとに遷移元の集合を用意している。それがさっき出てきた ns。そういう準備があったからこそ dp.values_at(*ns).sum という効率的な遷移を書くことができた。遷移を1行で済ませることができていた。■■■D 問題。解説を読むと、読むのもたいへんなので8割読み飛ばしちゃうんだけど、移動コストの上限は 2(N-1) で固定だから、ゲートを使って帰還コストをどれだけ節約できるかだよと書いてある……ような気がする。提出 #54485687 (AC / 989 Byte / 1765 ms)。パラメータが1つ減って3つになった。解説の最後にリストされている3項目に3つのパラメータを対応付けるなら、順番に RG+LG になるのではないかな。最後が一致しているのでヨシ!


2024年06月01日 (土) [AtCoder] 今日は AtCoder Beginner Contest 356 があった。自分のすべての提出。結果は見ないようにしつつふりかえりだけ。■A 問題「Subsegment Reverse」。愚直に配列を操作してもいいし、区間を3つに分けてもいい。■B 問題「Nutrients」。Array#transpose が便利。■C 問題「Keys」。愚直にやります。2**15*100 は数百万なので間に合う。問題文の「与えられるテスト結果が誤っており上記の条件を満たす組み合わせが存在しない場合もあります。その場合は 0 通りと解答してください」の意味がよくわからなかった。信頼できない入力が混じっていて、それを見抜いて何らかの対処が求められているのかと思った。実際は単純に矛盾するテストによって答えが0通りの場合があるよということを言っているだけだった。たしかに、複数のテストを照合した結果矛盾が生じて答えが存在しない場合、じゃあ、個々のテストにおいて「開いた(開くはずがない)」「開かなかった(開かないはずがない)」という結果をどう扱えばいいかという疑問が生じる。それは誤りであるという断り書きだった。■D 問題「Masked Popcount」。かつてよく見られた数え上げ問題。苦手だよ。でも精進によってなんとなくの型みたいなものは持っている。上限が N で与えられてるのがやっかいなんだよね。たとえば N=2**60 ならこれは主客転倒で寄与を簡単に数えられる。じゃあどのようにしてそういう状況を作るかというと、与えられた N のビットのうち、最も左にあって最初に倒されるビットを決め打つことによって N を複数の区間に分割する。N のプリフィックスと自由に {0,1} が選べるサフィックスとで構成される区間について問題を解く。たとえば N=0b10101 ならプリフィックスは1のビットの数と同じ次の3つ(0b10100、0b100xx、0b0xxxx)。 もちろん1つもビットを倒さない場合も忘れない。■E 問題「Max/Min」。よくわからない問題。N の上限は 20 万。これは O(N) もしくは O(NlogN) が解法となるよくある制約で、N の制約としてはほぼ上限。そして A が取り得る値が 100 万以下。これは N と比較すると大きい数字だけど、処理すべき区間が 100 万以下であってそれ以上は考えなくてもいいと思うと、そんなに大きい数字には思えない不思議。結局これは調和級数の上限がどうのという問題だったんだろうか。特別な道具を使わずに配列を操作すると決めたあとでも答えを合わせるのに苦労して、結局1時間近くかけてしまった。やるべきことはひと目でわかるんですよ。すべての組み合わせについて足し合わせるに当たって、予めソートして Ai と Aj の大小関係を固定してしまえば考えるべきは分子が分母の1倍か2倍か3倍か……。時間が厳しいので(そこが問われている問題なので)同じ値はまとめて計算しますよ。そうするとどんな入力が嫌かというと、小さい数字が順番に並んでると、処理をまとめることができず、区間を大きくスキップして処理することもできないのが困るなと。だけどね、100 番目、1000 番目の値はすでに十分大きいわけです。100 万割る 100 は1万だし、100 万割る 1000 は 1000 なので、個々の処理量は無に等しい。もちろん1万が1万集まれば馬鹿にならないんだけど、全体で見ても処理可能な範囲に収まることは知っている。名前は出て来なかったけど高3の演習問題でいつの間にか不等号を証明させられていたような気がする。■F 問題「Distance Component Size Query」。解けなかった。セグメント木とか平方分割とか、うまく区間を分割して効率良く数えられないかと考えたけど、できそうでできなかった。でもできるのかなと思ってる。自分にはできないけど。K=0 と K=1、それと K がすごく大きいときでだいぶ様子が違ってくるなとも思った。でも、じゃあ K=1 の場合に限れば問題が解けるかというと、そうでもなかった。■■■D 問題。桁ごとにサイクルを考えるという解法を仕入れてきた。LSB から見ていくと、サイクルは2、4、8と倍々になっていく。その中身だけど、前半が0で後半が1という単純なもの。だから 0 から N までの N+1 個の数をサイクルと半端に分けて1の数を数えるのも簡単。提出 #54162917 (AC / 165 Byte / 42 ms)。この考え方だとずるいぐらいに実装が簡単だった。自分は自分の考え方で実装したとき式を間違えて1回 WA を出してるからね>提出 #54107427 (WA)。


2024年05月25日 (土) [AtCoder] 今日は東京海上日動プログラミングコンテスト2024(AtCoder Beginner Contest 355)がなかった。いいね、そんなものはなかった。だから残念な結果も存在しない。少なくとも自分は確認していない。だけれども問題はあり、解けた問題もあるので、ふりかえりは行う。■A 問題「Who Ate the Cake?」。Ruby の配列は集合演算も行えて便利。■B 問題「Piano 2」。A 数列と B 数列をマージしてソートして、A 数列由来の要素が連続しているかどうか。愚直に線形探索をしても許される制約。どうとでもやる。■C 問題「Bingo 2」。1列が最大 2000 要素。縦横斜めが最大 4002 行(列)あり、それぞれに対して 2000 要素のスキャンを行ってもおよそ 800 万なので許される。ビンゴカードに何ターン目に呼ばれるかを書き込んで、行(列)ごとに最大値を読み取る。呼ばれない番号もあるので、それはテキトーに T より大きい値にする。Ruby で 800 万の処理はちょーーっと不安だったので、ターン数を知るのに Hash を使う代わりに Array を使うようにした。他所で読んだけども、制約がひと桁以上大きければ、ターンに沿ってビンゴゲームを進行し、ビンゴが成立したかどうかの判定を行列対角ごとに用意したカウンターで行うしかなかった。■D 問題「Intersecting Intervals」。タイムラインに沿って入りと出を管理して、現在を中に含んでいる区間の数を数える。数がわかれば組み合わせが数えられる。サンプルをよく読めば書いてあったけど、閉区間なのである値で隣り合っている2つの区間は共通部分を持つ。同時に起こる入りと出の処理順に注意する。■E 問題「Guess the Sum」。ABC349-D Divide Interval の記憶も新しいので(20240413)、今度はセグメント木をすぐにイメージすることができた。でも解けなかった。クエリ回数を最小化しないといけない。そのためには、与えられた区間を2冪に分割するか、もしくは、与えられた区間を内包する2冪から区間外を除くか、どちらを選ぶ場合も考えられる。それをうまく整理できなかった。散々悩んだ末にまずは DFS 関数を2つ書いた。1つは区間を受け取ってクエリ回数を数える関数で、もうひとつはクエリを実際に実行する関数。積み上げるのがいいか取り除くのがいいかは、2冪の幅を大きめと小さめの2種類特定して、再帰呼び出しでシミュレートして比較選択した。この2パターンでいいということが全然見えなかった。「整理できなかった」とはそういうこと。その結果、ひと通りの実装は済んでもデバッグの時間がとれないまま時間切れになった。穴あきになっていた PAST の問題(魚釣り)の精進をしてから(ふてくされてたんだよ)、コードの整理とデバッグをした。再帰関数はクエリ配列を返すもの1つだけに統合された(#53902777)。最短のクエリ配列を選んで最後にまとめて実際のクエリに変換する。クエリ配列を使うものも使われないものも区別せず生成破棄を繰り返すのは無駄が多いけど、それでも許される制約なのだから AC のためにはこだわっていられない。■F 問題「MST Query」。解けてないよ。MST というのは辺のコストの昇順に UnionFind をするやり方しか知らない。それでクエリに答えられるか考えてみたけどできなかった。辺のコストが 10 通りの値しかとらないところがクサい。つまり、コストの更新機会が限られるのではないか。グラフは最初は木で、クエリのたびに辺が増えて入り組んでいくけど、実は常に木の形を維持していていいのではないか。そして木を維持するのにちょっとばかしコストをかけても、総体としてコストの和は実行可能な範囲におさまるのではないか。新しい辺を追加しても木の形を維持するというのは、2頂点間のコスト最大の辺を特定して切断するということ。そんなの逐次的に効率的にできないよ。UnionFind の経路圧縮的な手抜き手段がないと、部分木のすべての頂点について親子関係を更新することになってやってられないよ。■自分のすべての提出。成績証は確認しません。■■■UnionFind を 10 個使うんだという解法の核心を某所 publish.obsidian.md/naoya/ で読んだので、それでどうやって答えが出せるのかをお風呂で考えてきた。UnionFind ではコスト1のグラフ、コスト1から2のグラフ、コスト1から3のグラフというような 10 種類のグラフを管理する。あとはまあ、やります。提出 #53927502 (AC / 576 Byte / 1512 ms)。当日は、コスト1のグラフ、コスト2のグラフみたいに分けることは考えていた。「それでクエリに答えられるか考えてみたけどできなかった」。あとちょっとが足りないんだよなあ。やるだけも門前払いも退屈なので、これはちょうどいい難易度。■AC を出したことなので安心してネタバレを読みに行ったら、「ABC355 振り返り」、なんか UnionFind の使い方が違う。Ruby の中ではひときわ速い fumta さんの提出 #53927847 が同じ解法だと思うんだけど、えー、わかりません。自分の解法は、最初に N-1 本の辺のコストの合計を記憶しておいて、新しい辺が採用されたらそのコスト w を足し、それまでに採用されていたが不要になった辺のコストを w+1..10 の範囲で探して引くというもの。単純明快でしょ。しかも、コスト1の辺を使うグラフ、コスト1から2の辺を使うグラフ、……という 10 種類のグラフを維持管理する処理と、辺を追加したことで不要になった辺のコストを特定する処理が一体となっているところが美しいと思うんだ。これは解答というより問題の力だとは思うけども。■■■E 問題。kotatsugame さんの動画(【競技プログラミング】ABC355【実況】)でグラフとしての見かたを知ったので、新規に実装して提出した>#53993734 (AC / 1045 Byte / 402 ms)。変数の取り違えで RE を出し、off-by-one エラーで WA を出し、デバッグ版を提出して WA を出したあとでの AC だった。やっぱり難しいね、この問題。ミスのしやすさも問題の難しさのうちだとすればね。やっていることは辺が陽に与えられないだけの BFS。グリッド問題みたいなもんだ。■C 問題。行や列をスキャンする O(N^2) 解が 455 ms (#53855978) だったところ、カウンターを使う O(T) 解が 132 ms (#53993977) だった。制約がちょっと変則的で、1≤T≤min(N^2,200000) かつ 2≤N≤2000 なので、T の上限が 20 万なのに対して N^2 の上限が 400 万。N^2 解を許容するためにあえて制約の桁を減らしていることが窺える。C 問題だしね。まんまと甘えさせてもらいました。