脳log[20260111]

2026年01月11日 (日) [AtCoder] 昨日は ABC440 (Promotion of Engineer Guild Fes) があった。苦しい。配点を見れば E までを確実に解きたい回。フタを開けてみれば C も D も E も苦しい。(結果とは別のところで)とても満足している。■A 問題 Octave。X の Y 乗ではありませんでした。■B 問題 Trifecta。T の小さい順に３つ。■C 問題 Striped Horse。問題文が難しいです。幅 2W で区切った前半 W を黒で塗る。変数は x。これを操作することで 2W の区切りをずらすことができる。N マスが 2W の倍数でないと面倒なので 0 を補って 2W 境界にアラインする。あとは尺取り。2W 幅の繰り返しは予め重ね合わせて同時に扱える。頭の中を整理しながら丁寧に丁寧に丁寧に時間をかけて尺取り。黒と白の幅がそれぞれ W しかないから勘違いしたけど、総当たりするには 2W 通りを考える。23 分かかった。■D 問題 Forbidden List 2。ある値 x が与えられたとき、X 以上 x 以下の整数の個数と、A 数列に含まれる X 以上 x 以下の要素の個数から、含まれない数の個数がわかる。ある値 x が A 数列に含まれる場合と含まれない場合を慎重に区別すれば答えを二分探索できると思ったけど、これは log が２乗になるというのに時間制限が標準の２秒しかない。これはいけない。A 数列をなぞる処理を考えよう。ソートした A 数列のうち X 以上の要素のみを並べた A′ について考える。求める Y 番目の値が A′[i] の左にあるか右にあるかは計算で求められる。答えが右にある A′[i] のうち最大のものはなんだろうか。なぜか Q×N の処理に満足して TLE を出したけど、A 数列をなぞる処理を二分探索で書き換えるのは簡単。６分で修正して全体で 35 分＋ペナルティ５分。■E 問題 Cookies。まずですね、問題文でさらっと流されている全ての選び方が N+K-1 個から K 個を選ぶ方法の数だということがわからない。そこをわかったつもりでプライオリティキューを使って１個１個下位の要素に置き換えていく操作を X-1 回行う処理を書いたら、サンプルの３が合わない。どうやったらサンプル３の答えが出てくるのか、プログラムを離れても理解できなかった。最大の値 97 を２番目の値 93 に置き換えることで４ずつ小さくなっていくものだと思っていたら、途中から減り幅が２になって１になっている。ようやくわかったのは、たくさんの 97 を 93 に置き換えるよりも、１つだけの 97 を 59 に置き換える方が優れている、そういう閾値が K 以下で存在している場合があるということ。残り 10 分以下でそれがわかっても、なんならどれだけ時間があっても、重複なく整然と次の候補をキューに入れていくことができない。■自分のすべての提出。■動画を見ていて知ったけど、馬の問題が多かったらしい。今年は午年らしい。どうしてどちらも「らしい」なのか。シマウマがいきなり長さ N のマス目になるんだなという、前置きと本題の切り替えの唐突さは感じていたが、そういう理由だったのね。■■■E 問題。N+K-1 個から N-1 個を選ぶだと理解できた。K 個ではなく K 個以外である N-1 個の方が仕切り。H で表される組み合わせは知っているしそれで理解しようと考えていたんだけど、どちらに注目するかでさっぱりわからなくなるんだなあ。むしろ問題文に書かれていたことでわからなくなった。■E 問題。重複のない遷移を考える必要はない。最大 50 要素になる配列を Hash につっこんで重複を調べるので十分に早い。提出 #72433875 (TLE×18/AC×16)。ダメです。■提出 #72434929 (AC / 934 ms)。遷移先をより限定することで AC になった。A 数列は予め降順にソートしておく。各クッキーを何枚選んだかという C 数列を状態としてダイクストラ法をする。１枚以上選ばれたクッキー i のひとつひとつについて、遷移先は (C[i]-1; C[i+1]+1) したあとの C に限って良い。遷移できなければ遷移しないだけ。それで網羅できる。■E 問題。逆の遷移を考えることで重複のない一意の遷移を選ぶことができるとかなんとか解説に書いてあるらしい。読んだけどよくわからないので「らしい」です。■F 問題。動画で考察を聞いてなお実装が１時間で終わらない。提出 #72444957 (AC)。すべてが 66 行目に詰まっている。