今週の参加記担当の山田です！ABC476の参加記を書いていきます。
ABC476
コンテスト前の山田のレートは 2001 でした。本当に久しぶりの黄色安定期に入ってきました。なので今回は unrated での参加記になります。
この高めの配点と writer 陣を見て嫌な予感がしました。unrated でよかったかも。
苦手 writer を３人挙げろと言われたらこの３人を挙げます。特に先頭のひらきちという人物は難実装・非典型要素の大きい問題を出してくることが多いです（でも最近は落ち着いてきたと思います）。競プロ界隈では「コワスギ銀行頭取」「Σexの人」などの通り名で恐れられています。
A問題
（C++ では）S.back()で最後の要素を取得できます。知らなくてもS[S.size() - 1]でできます。
0:30 AC。
B問題
拡張forで楽に書きたくなります。ただS, Tの「同じ添字で両方取得」というのは難易度が高いです。Python だとfor c, d in zip(S, T)でできるのを山田は知っています。
残念ながら C++ しかまともに書けないので普通のforで添字iを回して書きました。
1:14 AC。
コンテスト後に GPT に聞いたら、C++23 以降ならviews::zip(S, T)で Python のzip(S, T)と同じことができるらしいです。rangesとviewsは体系的な教材が見つからなくて習熟できてません……。
C問題
Wavelet Matrix で殴ります。
2:30 AC。
C のユーザ解説に「殴る」って書いてあったから WM かと思ったら違った
— えびちゃん🚑🐿️☄️ (@rsk0315_h4x) 2026年9月19日
↑これになりました。
D問題
ドル紙幣しか受け付けないというありえん問題設定は sheyasutaka イズムを感じます。
の自販機では自由に買えて、変な制限があるのは
の自販機です。
自販機ごとに買う優先順位は安い順でいいと思います。なので「 での購入個数」「
での購入個数」の二つさえ分かれば「購入可能か」は累積和でもなんでも自動的に求まります。両方固定しようとすると当然
以上になって駄目です。
の方が単純な構造をしているので、
での個数を決め打ち全探索すれば高速化可能だと思います。
まだ詳細があやふやですが、手癖ですぐ解ける自信があったので実装開始しました。
はソートされてあるものとします。
となる数列
を作っておきます。これは各商品で消費される
ドル紙幣の枚数を表します。
での購入個数を固定したのち、
でどれだけ買えるかの計算を
ぐらいでやろうと思います。まず
の累積和で「
ドル紙幣が足りるかの判定」と「残金」を
で計算します。これで
で何ドル使えるか分かったので、
の累積和上の二分探索でどこまで買えるかを
で求めます。ちなみに累積和上の二分探索は直接やるより、区間和セグ木に乗せてセグ木上の二分探索でやった方が、山田的に楽なのでそうします。
9:25 AC。
E問題
まあ……やるだけ。
セグ木で区間最大値（最小値）を取得するのはよくありますが、今回は （＝最大値の添字）も取得したいです。それは素直にセグ木に（最大値、最大値の添字）を両方持たせておけばできます。セグ木に乗せられがちランキングで「最大値／最小値」「和」の次ぐらいに来るモノイドです。
16:21 AC。
添字を乗せなくともセグ木上の二分探索で を取得できることが、コンテスト終了後の Twitter に書かれていました。確かに。そっちのほうが山田にとっては楽です。
F問題
本日のメインディッシュ問題。最終的に別解での AC となりました。
「住人の数が で与えられる」「出力するのはハッシュ的なもの」という変な設定は入出力の削減のためだと思います。入出力は定数倍が重く、この巨大なグリッドを入出力させると言語やテンプレートによって有利不利が出まくってしまうので、それを解決するための設定だと思いました。
よってこの設定を利用することはなさそうです。各マスの住人の数がランダムに与えられても解ける解法で、普通にマスごとに答えを計算してから出力すべき値にするんだと思いました。
二通りの方針があると思いました。１つ目は、カフェの場所を固定して、かかるコストを累積和か何かで直接取得する素直な解法。２つ目は、人の場所を固定して、各場所のカフェへの寄与を imos か何かで加算する主客転倒解法です。
後者の方が求まる感が強かったので、一旦後者で考えていました（想定解法もこっちです）。
チェビシェフ距離はその等距離線が四角形の渦巻き型となります。考える対象を以下のように４方向に均等に分解し、別々に求めることを考えると単純になると思いました。
山田のテンプレートにはグリッドを回転させる関数があります。
template <typename T> vector<T> Rotate(const vector<T> &v, int clockwise = true) { using U = typename T::value_type; int H = v.size(), W = v[0].size(); vector res(W, T(H, U{})); for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) { if (clockwise) res[W - 1 - j][i] = v[i][j]; else res[j][H - 1 - i] = v[i][j]; } return res; }
これで以下のようにすれば実装量を四分の一にできます。
// C は各マスの人数 for (int _ = 4; _--; ) { ans = Rotate(ans); C = Rotate(C); auto bns = calc(C); // １方向のみの寄与を求める関数 for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { ans[i][j] += bns[i][j]; } }
肝心の寄与を求める方法ですが分かりません。imos を変な方角に作用させる問題だと思います（実際そうです）が適当な方向に作用させても全然所望の形にならなくて絶望していました。
破滅の予感がしたので人固定方針を忘れて、カフェ固定方針を考えます。一個一個のカフェに関して独立に求めようとして難しいと判断してさっき棄却しました。独立に求めるのではなく差分更新を利用するのはどうでしょうか。
カフェを右に動かした場合にその差分を で求めたいです。
このように斜め方向の区間和的なものを で求める問題になりました。ただしただの区間和ではなく邪魔な重みが付いています。数列
の添字の一次関数で重みが付いた数列の区間和は、
の区間和と
の区間和を組み合わせる、という典型があるので一応求まることが分かりました。累積和を駆使します。
解けたと思います。でも実装がしんどそうです。 固定、
固定系（つまり斜め方向ごとの抽出）の添字はただでさえ頭を壊しやすいですし、それを組み合わせて色々やるのは大変です。
考察開始から 20 分ぐらいで実装開始。
固定のところを抽出する際に、
std::vectorの負の添字を有効にするテクニックが便利です。
vector<int> A_base(101); auto A = A_base.begin() + 50; // これで A の添字は [-50, 50] が有効 A[-10] = 10; // RE にならない
これで 固定の扱いが楽になります。座標変換後の
C[i][j]は従来ならS[i - j + N - 1][j]みたいにオフセットを足す必要がありますが、負の添字を有効化することでS[i - j][j]のようにそのままアクセスできます。が、毎回忘れて非負添字のみで実装してしまっています。次こそは使います。
55:01 AC。
実装開始から 20 分ぐらいでの AC です。sheyasutaka 問の重実装系の中では楽な方だと感じました。強烈な回だと今回の「四回 Rotate」みたいな小手先の典型など通用しません。
imos を適当にガチャガチャ考えていた時間が無駄でした。
山田は「変な imos」に分類される問題をあまり思い出せませんし、実際かなり希少だと思います。しかもだいたい別解の方が素直だと感じていたため、あまり重要視していませんでした。
今回 imos でのやり方を思い付けなかったのは「方角の組み合わせを前から決め打って所望の形になるか試す」というスタイルで考察していたからだと思います。これでは山田のような天啓難民にはきついです。
より確実な方法がないか考えます。所望の形から逆に考えれば imos 構築方法が見えてくると思いました。答えの形から考察することは imos に限らず競プロ全体で頻出な解法特定方法です。何故考えなかった……？
今回の問題を例に挙げます。
この「完成形」から「一段階前の状態」を想像します。なるべく「単純な形」になるようにします。今回は横方向が良さそうです。
一旦緑色部分のことだけを考えます（水色と別々に求めて足し合わせればいい）。これは斜め方向に差分を取ると「単純」になります。
既に普通の imos です。もう一回同じ方向に差分を取れば、「加算すべき場所」は一個だけになります。これで全 imos の逆手順が求まりました。
G問題 (間に合わず)
とした数列
の範囲
から、「狭義単調増加な部分列を何本取れるか」という問題です。それは「広義単調減少な部分列の最大長さ」（つまり LDS）と一致するという有名な話があります。ちなみにこの事実は競プロerが Dilworth の定理を履修する際に最初に見せられがちな具体例です。
「 の LDS を求めよ」っていう問題の方が元のよりやりやすいと思うのでこの言い換えで考えるのは確実そうです。LIS-DP をどうにかこうにかしてこのクソデカ制約でやるっぽいです。
ここから何も考察が進みません。 の増減にしかない性質を利用するのが必須だと思いますが見当がつきません。
時間が多く余っている上にやることがないので大胆予想をします。最初に採用する要素の を決め打つと、あとは
の大きいものを貪欲に採用していけばいい、という解法です。
半分ぐらい証明したつもりになっていましたが普通に嘘です。しかも思ったより実装が大変で、桁 DP をバグらせている間にコンテスト終了。
１５分後ぐらいに、想像した通りに完璧にコードが動いていそうという状況まで来ましたが、サンプルが合いません。しかも小さいケースでは全部合っているのでデバッグできません。
必殺ランダムテストを書いて、落ちる小さいケースを発見しました。
LDS で選ぶべき添字は ですが、この解は先述のアルゴリズムで拾われません。
嘘だったので考え直します。
まず区間内の は、「動くビットのうち半分ぐらいが立っているもの」に非常に偏っていると思います（二項係数
は
が
に近いほど大きくなるため）。序盤の時点で考えていたことです。これを利用できませんか。
「動くビット」というのが曖昧なので、一旦考察対象を がセグ木的区間である（つまり非負整数
を用いて
、
で表せる）もののみに限定します。これで「動くビット」が均等に下位
個となります。
先述の通り「ほとんど同じ から選ぶことになる」と考えていましたが、セグ木的区間なら「全部同じ
から選ぶことになる」なんてことはありませんか。それ以外の
から取ってくる必要を感じません。
証明ができないので、さっきのランダムテストで書いた愚直解を再利用し、実験してみました。……どうやら全部同じ を選ぶのは正当らしいです。
よって与えられる をセグ木的区間に分割すると、LIS-DP が
の多項式時間で可能です。
実装やり直し。一旦 で書いて最大ケースで試すとめっちゃ遅かったので、DP を累積 max で高速化して
に落として提出。
150:36 AC。50分オーバーで未証明 AC。
公式解説を開いたら、山田ができなかった証明に知らない知識が出てきました。後で履修します……。
コンテスト結果
G 問題以外の六完 (55:01 ノーペナ)、パフォーマンスは 2189 相当でした。正直とりあえず黄パフォあれば OK ということで。
E 問題まで癒やしセットだったのに F 問題がコワスギ問題すぎてやられました。
↓画面録画
