○○ を探す。■B 問題 Citation。１回間違えて愚直二乗解法で書き直した。与えられた値の中に答えがあると思い込んだわけではないのだ。それも想定して、でも反例が出てこなくて間違えた。とても難しい問題。以前から書いてるけど、否定で定義される MEX みたいな問題が苦手。問題名は引用かなと思ったけど意味がわからない。調べたら召喚状、出頭(罰金)命令書、賞状といった意味が出てきた。意味があまりにとっちらかっている。形式に対する名称なの？ なんにせよどれもしっくりこないような。■C 問題 Equilateral Triangle。円周 L を３等分して L/3 個の三つ組の掛け合わせの和。■D 問題 String Rotation。まず先頭に近い方から前後ペアを見つける。どのような。前後が大小の順番で並んでいるペア。次は見つけたペアの大きい文字をどれだけ後ろへ送るかを決める。より大きな文字の前か最後尾。■E 問題 Pair Annihilation。焼きなまし？(問題名←それは annealing こちらは対消滅) F 問題より考えた。最小全域木的な操作や重み付き UnionFind を考えたけど、うまくない。葉からの DP (with マージソート)を考えたけど、うまくない。実は葉から貪欲にペアを作っていくのが最善だった。それがわかればあとはがんばって書く。■F 問題 Connecting Points。２乗が通るのでやるだけですか？ TLE×3 だった(#66577100)。もうええやないですか。通してください。できることはもうやってるんです。プライオリティキューに無駄要素が詰まりがちだから、値が重複しないように気をつけました(プライオリティキューにはユニークな距離の値だけを入れ、距離に対応した頂点対リストは Hash に入れた)。新頂点を追加するときに点間距離ではなく連結成分対新頂点の最短距離をソートによらず選び出すことでさらにキューに入れる要素を減らそうとしたら、これは遅くなりました(TLE×7)。お手上げ。1+1+1+1 = 4 ではないんです。３までは線形に増えていってもその次はスタックオーバーフローで実行が完了しないんです。こういう限界の低さをふまえて出題してもらいたい。D 問題に解けない問題を置かないでほしい。■■■A 問題。嫌いな嫌いな +0.5 秒問題。自分について理解した。たとえば問題文が「最後に肩を叩かれてから S 秒後まで長老は起きています。(最後に肩を叩かれてから) S+1 秒後には寝ています」だったらすんなり頭に入ってくる。次からこう読めばいいと理解した。S と S+1 という２つのパラメータを S というひとつの値で表すために +0.5 秒というやっかいものを導入して、「あとはわかるな」で済ませるから話がややこしくなるのだ。きっちり文章にしてくれないとわかりません。0110 と 0[1]2[1]0 しか作れないとわかる。２の両隣の１はオプション。0 はいくつ連続で並べてもいいので、11 と [1]2[1] を 0 で区切るイメージ。まずは消費の仕方が限られている２を消費したい。２を消費するのに十分な０の数は２と同数。これは数列が環状に循環しているから。次に１を消費したい。２の両隣の１はオプションだから、２の倍の数までは何も考えずに消費できる。余りは 11 として２の島と同様に同数の０で区切る必要がある。余りの１が奇数個の場合が面倒。２の隣の１をひとつ持って来られるなら良し。持って来られない(２がゼロ個)なら即座に No。実装ミス(A = A-B-B を A -= B-B とした)と勘違い(ひとつのことを実装しているあいだにもうひとつのことが曖昧になっていくせい)で２ペナ。■本日の ARC は終了です。時間をオーバーして C 問題の実装を終わらせたけど、シャッフルした順列をソート済みに並べ替えようとすると最後の２要素が一致しない。操作対象が２要素だけだと自由度がなくていけない。１要素を加えた３要素を手で操作してなんとかできないかやってみたけどどうにも完成させられなかった。えっ？ 全体の和が一致していても不可能なケースがある？(ないよね) N=2 だけでなく N=3 も場合分けが必要？masked_max_m = max>>digit_from_bottom<<digit_from_bottom って書くかなあ。特に罠もないと思う。符号は罠にならないし(非負だよね？)、シフト数の罠(明らかなシフトしすぎは未定義)は書き方によらないし (Rust の罠は知らないよ)。あと、20250517 に書き足したことだけど、以下と未満の差を埋めるのは n に予め１を足しておくだけでいいみたい？円安が追い風」 円安はネガティブ材料なのだから、向かい風や逆風がふさわしい。関係あるようなないような話。真逆と書かれていればそれが作家の当て字でも早い者勝ちルールでマサカと読むことにしている。■■■「大学院の講義が英語化された結果、日本人学生はリスニングができないので話を聞かずレジュメを眺め、一部積極的な留学生がたまに質問するようなスタイルになった - Togetter [トゥギャッター]」■相変わらず趣旨には触れないんだけど、～が原因となってみたいな意味の「ひいては」を漢字にすると「延いては」になるみたい。意味を考えるとまあそうかなという感じ。延長線上に何があるかを示すという意味で。「引く」という動詞があまりにもたくさんの意味を持っていて、「引いては」と変換候補にも出てくるから、うっかり選ぶこともあるかな。(それがなんか違う気がしたので ATOK で辞書を引いた)
Array#- で残ったものをどれでも出力する。■B 問題 Grid Rotation。回転操作は transpose と reverse をテキトーに組み合わせて実現できることを知っている。テキトーに試してみてどんな具合か出力してみてそれが何回右回転したものかを目視で確認する。あとはそれが T とどれだけ一致しているかしていないか数える。■C 問題 Cycle Graph?。スマートにやろうとかテキトーにやろうとすると WA が出るのを知っています。スマートにっていうのは頂点数と辺の数が一致していることを確かめるだとか、頂点の出現回数がどれもちょうど２回であることを確かめるだとか。入力が単純無向グラフであることで多重辺や自己辺といった罠はあらかじめ取り除かれているけど、グラフが複数のサイクルに分かれている場合が罠になる。再帰関数できっちり全頂点を辿れるかを確かめる。きっちりできるかどうかはがんばりしだい。■D 問題 Goin' to the Zoo。100 ms オーバーで TLE だった。こうなるとましな新しい解法を考えることはできなくて、小手先の試行錯誤でなんとかする頭しかない。E 問題のあとでやろうとして帰って来られなかった。■E 問題 Bowls and Beans。2000 ビットのビットフラグで状態を管理することは TLE になるのでできない。できないけど他に思いつかなかった。どうすれば良かったか。茶碗には２種類しかない。最初から豆が入っていた茶碗と、入っていなかった茶碗。あとから豆を入れられた茶碗というものをとりわけて考えない。茶碗１から順番に考えていく。左側にある C 個の茶碗を参照して、現在の茶碗に豆があるとすると最少何回の操作を追加することになるかを記録していく。そのとき、参照した茶碗が元から豆が入っていた茶碗なら、その茶碗に記録されている操作回数は無視して１回が記録対象になる。もともと豆が入っていなかった茶碗なら、その茶碗に記録されている操作回数＋１が記録対象になる。コンテスト中に引っかかっていて解決できなかったポイントがここにある。元は豆が入っていなかった茶碗が右側にある豆を茶碗０に移動する際の中継点になるとき、もちろん複数の茶碗から豆を集めてからまとめて操作をして操作回数を節約したいと考える。さっきのやり方では操作回数を重複して数えてしまうのではないか。そうはならない。現在の茶碗と参照する豆なし茶碗のあいだに豆入り茶碗が存在しているとき、豆入り茶碗が常に優れた参照先になる。ここまではいい。あいだに豆なし茶碗が存在するとき、それが中継点への中継点として役に立つか無視されるかはわからないけど、重複を心配する必要はない。だってどちらの豆なし茶碗もまだ実際には操作回数が答えにカウントされていないのだから。豆なし茶碗の操作回数は豆あり茶碗から参照された時点で初めて答えに寄与し、そのときから参照した豆あり茶碗が参照された豆なし茶碗より優れた参照先になるので、操作回数の重複カウントが起こらない。そういう関係が見えなかったのでコンテスト中はビットフラグで全パターンを網羅しようとして TLE 解しか書けなかったのだった。提出 #65480897 (AC)。■F 問題 Lost and Pound。残りの試行回数と現在の当たり回数しだいでは１つのボタンに全ベットするしかない状況もあるよね。後ろ向きに全パターンを網羅して埋めていくんだろうか。TKKM≦810000 が微妙に小さくて何か見落としてないか不安。ボタンの選び方が簡単に決まらないのかな。30 の選択肢を 1 から 30 個のボタンにどう分配するか。ボタン当たりの賭け数の比率にしか意味がない。30、29+1、28+2、28+1+1、……。これは何通り？ 状態数が TK で遷移が KM かと思ったけど、遷移の M が M の関数だった。■F 問題。提出 #65484558 (WA×18/TLE×1/AC×35)。サンプル３を合わせるために T 回の試行の各回で k=0 から勝ち抜ける場合を特別扱いしているけど、３分の１ほど WA がある。その他の k も特別扱いすればいいのだろうか。頭の中の整理が追いつかなくてどうやるのかわからないけど。……経路の復元をしますか？ すでに TLE が１個出てるのにまだ手をかけますか。■■■F 問題。提出 #65513292 (AC / 1925 ms)。えっとね、サンプル３の合わせ方が間違っていた。後ろ向きの遷移経路の復元ということで順方向の遷移をたどっていて気がついたんだけど、答えが合わない原因は、当たりの数が１増える遷移、２増える遷移、３増える……ばかり考えていて、当たりの数が増えない遷移を考え忘れていたこと。それを忘れたまま変なこと(最初の提出の 34-37 行目)をしてよくも３分の２ほど答えが合ったものだと逆に驚く。そこをちゃんとやれば最初に考えた構成で素直に答えが出た。後ろ向きの遷移を T 回繰り返したあとで k=0 の位置に答えがある。何種類のボタンに何回ずつ賭けるかという配分のしかたは前半部分でプログラム的に求めている。再帰関数で愚直に。TLE×1 の対策は Hash#to_a をしただけ。t/N を事前に計算して t の値に含めておく案もあったけど必要なかった。あとは分配のしかたを埋め込むとか？■■■E 問題。線形時間で解けると読んだので考えた。提出 #65552947 (AC / 124 ms / 49 ms)。124 ms が最初のテストケースに固有の特異な値だとして無視するとその次に遅いのが 49 ms。いいんじゃないでしょうか。C の値に基づいて次の最善手を範囲取得すると log が付いたり２乗になったりする。後ろから見ていくとうまくいく。そのためには ref1, ref2 という２つの変数を蓄えておくだけでよかった。少しだけがっかりするお知らせは、次の一手を範囲取得するのでも、適時(Ai=1 のとき)参照する配列を空にするようにすると 56 ms までにおさまるということ (#65551430)。考えて字数を費やして複雑にした甲斐がない。