脳log[20260222]

2026年02月22日 (日) [AtCoder] 昨日の AtCoder × Engineer Guild オンサイトコンテスト ～ACからはじまる27卒キャリア～予選　（ABC446）。最初に言いたい。コンテスト名が長すぎる。なぜこれを言うかというと、コンテストが始まってみるとなんか見た目がいつもと違うのだ。ページトップの黒帯の幅がいつもより大きくて、[トップ][問題][質問][提出][提出結果][順位表][コードテスト]という重要リンクを覆い隠してしまっていた。AB 問題の提出に６分かかってるのはこれへの対処と動揺のせいが半分。ブラウザを横にちょっと広げたら解決した。■A 問題 Handmaid。以前にも書いたけど Ruby で大文字化小文字化に対応するメソッド名がまったく覚えられないうえに当てずっぽうもことごとく外すので今日は最初からリファレンスを見た。String#downcase, String#upcase が正解。JavaScript が toLowerCase, toUpperCase なのは知ってるんだよ(それが原因か？)。■B 問題 Greedy Draft。ジュースがあるかないかのフラグを管理する。■C 問題 Omelette Restaurant。難しい。他の人の提出を見ると、玉子の日にちを個数個分キューに入れて使用をシミュレートするのがわかりやすかった。自分はどうしたか。B 数列(玉子の使用数)の累積和を用意して何日目までに何個必要かを二分探索できるようにした。玉子が補給されると、これまでの玉子で満たされている要求量から何個上積みして要求を満たせるかが、累積和の値(玉子の要求量の累積)と添字(日にち)から二分探索で判断できる。でもややこしいので方針ミス。18 分かかった。■D 問題 Max Straight。これは３分半。Hash で値をキーにしてその値に至るまでの要素数の最大値を記録した。■E 問題 Multiple-Free Sequences。とっかかりもつかめない。飛ばした。■F 問題 Reachable Set 2。最大のミスは無向グラフについて問題を解いていたこと。自己辺も多重辺もあると気づいていたけど有向グラフであることが頭に入っていなかった。そのせいで UnionFind を使う頭から離れられなかった。あとなんか削除する辺の数を答えようとしていた。答えるのが頂点数なら自己辺も多重辺もほぼ無視できて考慮に値しない。終了後もずっと UnionFind をいじくっていたけど、この先に答えはないとやっと頭がリセットできると、k=1..N に沿って寸止めの探索を進めていくだけだった。提出 #73515718 (AC)。訪問済みの頂点(k 以下)と訪問を先送りしている頂点(k より大きい)を２つの Hash に記録すると、それぞれのサイズが判定条件と答えになる。これが 500 点は買いかぶりだと思うけど、解けなかった人間が言うことではない。■■■E 問題。他所で functional graph だと読んだ。それだけではわからない。この問題は M の倍数だとか無限数列だとか言っているけども、ポイントは mod M で考えてもいいということだ(昨日はそれがわからないんだなあ)。そうするとある項は前２項によって規定されるけども、ある項の取り得る値は M 通りで、行き先は M×M 通りの組み合わせによって決められる。行き先が有限だから必ずどこかでループに入る。それが functional graph ということだろう。ここからじゃあどうやって実装しようかなと考えるんだけど、M*M 通りのメモ化再帰でいいでしょう。提出 #73532574 (AC)。時間内に解けてほしいなあ。■■■スペースが足りない。今日の AtCoder Regular Contest 215。■A 問題 Zombie。ちょっと楽しい問題。一見すると全然とっかかりがないように思える。餌を置く位置や順番が影響しそうで途方に暮れそうになる。でも実はゾンビとゾンビのあいだに餌を置いたとき起こることは、２体のゾンビがくっついて空間が消滅し、その他のすべてのゾンビが空間を保ったまま中央のどこかに寄ってきて、左右の端の空間が広がっている、という割とシンプルな状況だった。じゃあ左右端の空間が狭いあいだはゾンビとゾンビのあいだの空間を消費して、左右端の空間が十分に大きくなったら左右端に交互に餌を置くのが良いのではないかと思った。でもサンプルがいくつか合わなかった。整理するとわかるのだけど左右端の空間を L、R とするとき、端に交互に餌を置いて稼げる時間は L、R+L、R+L、R+L、という感じでほぼ一定で推移する。左右端の空間をどこまで育てるのが最善かは単純な大小比較ではわからないのだった。餌の数 K は 10^9 と非常に多いけど、ゾンビのあいだの空間は N-1 までに限られている。全探索をした。提出 #73535514 (AC / 422 Byte / 400 ms)。■B 問題 Stolen Necklace。２つの集合を管理してやるだけですか？ と思ったところで「仕切りの個数 K は N 以下である」という条件に気がついた。これが難しいのだろうか。でも 1 1 2 2 3 3...N N という、一番仕切りが必要になりそうなケースでも仕切りの数は N 以下に収まっているようだったのでとりあえず投げてみて AC だった。提出 #73537550 (AC / 376 Byte / 385 ms)。■終わり。