10^7)に制限されている意味はわかっていたつもりだけど、区間の上限が (10^7)^2 だということとその意味に気がついていなかった。十分な大きさの素数までを列挙すれば、１つの素数のべき乗(2,4,8,16……など)とすべての合成数(4,6,8,10,……など)が列挙できて、消去法で区間内に高々１度しか現れない大きな素数も見つけられるんだけど、「十分な大きさ」を決めるのは区間の幅ではなかったのだった。提出 #67224096 (AC)。■F 問題 Socks 4。N すくみ的な状況。手持ちの靴下を C→D(→E)→C と入れ替えて戻すのは必ずどこかで判断ミスをしているので堂堂巡に陥る心配はしないけど、問題設定がすこしでも複雑になると自己ループの除去とかできなくなる。■火曜日……２晩……。６月30日は ABC412 の代わりに消えた？÷6^N をループの外に出してこれなので、もし２秒制限で TLE だったら、2,3,(4),5,(6) の N 乗までを前計算したりしたかな。あと、前後のループの後半と前半で確率の値が使い回しできそう。……ということは、ループ全体で足し引きを通算して再構成するともっと演算が減りそう。考察が足りなくて最適解が見えていない可能性。■F 問題 Contraction。制限時間が４秒。やや高の 525 点。辺をマージするだけなのかなと素朴すぎる方針を立てて実装したところ、およそ１秒で時間は間に合ったけど WA が多数 (#66981976)。必要な処理を抜かして時間を稼いでいる疑い。■■■F 問題。終了 12 分後に提出したものは WA×31 だった (さっきの提出)。翌朝目覚めたらデバッグが完了していた (#66988575)。頂点 a と b をマージして a が代表として残るとき、b とのみ辺で繋がっている頂点 c を a に付け替える。そのときに辺を a と c 双方に登録しなければいけないところ、a から生やす辺を忘れていた (30 行目)。やっぱり時間内(E 問題に 40 分かけたがまだ 30 分と少し残っていた)に解けてほしい難易度の問題だったけど、実際にはひと晩(≠ひと晩中)かかったなあ。解答に使った知識は UnionFind とマージテク。■今日ある第六回日本最強プログラマー学生選手権-予選-（ARC201）には参加しません。最初の２問が 500 点だけど、どう考えてもはりきった出題者が一筋縄ではいかないひねった問題骨太な問題を出してくるに決まってるんです。先週の ARC200 (div.2) の A 問題 (500 点) が解けなくてゼロ完だったことで私はいたく傷ついています。■■■D 問題。Array でやってもだめだった (TLE×13)。ちなみに String だと TLE×12 だったから、Array よりマシ。そして、クエリ逆読みをやってみたら WA×18 だった。「一瞬で断念した」だけのことはある。デバッグ完了 (AC)。それから最初の解法だけど、リンクリストのノードは Q 個ではなくクエリ２の数だけで十分みたいだった。クエリ１と３でコピーしなければいけない気がして自分は空文字列を追加した体で新しいノードを作ったんだけど、一度作ったノードは不変なのだから、参照をコピーしてノードを共有するやり方で問題なかった。当該車両の運転士が車両のパーキングブレーキシステムをオンにし、待機場停車時にフットブレーキ操作を行ったにもかかわらず、パーキングブレーキが有効に作動しなかった」ときにどんなフィードバックがあったのかなかったのか。これはブレーキをかけることとブレーキがかかることが一致しなかった例。自分は古い人間なのでこの２つがワイヤーで直結している(力学的)システムが好きです(大型車両で補助動力がうんぬんはおいといて、自分が乗る車は)。ちなみに自動運転のエラーではなく手動操作中の事故。しかし原因は(車内の？)通信ネットワークにある。
○○ を探す。■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 に予め１を足しておくだけでいいみたい？