KCPCブログ

京大競プロサークルKCPCのブログです！

【ABC477】惨敗！！

こんにちは、柑橘です。
今回はABC477参戦記となります。記事を出すのが大変遅くなってしまい申し訳ないです......。競プロの勘は一向に戻る気配がありません。
あと手元のAC counterはいまだに謎に壊れっぱなしで、死んだ顔になっています。大昔にgeminiに全部環境構築を任せたのが完全に裏目に出ている気がします。

ABC477

配点：100-200-300-400-450-525-625

A問題

問題リンク：https://atcoder.jp/contests/abc477/tasks/abc477_a
推定diff：17（灰diff）
この日は帰省先からの帰り道でのコンテスト参加でした。もたもたしながらPCをスマホのwifiデザリングに繋ぎつつ、少し考えます。手早い書き方が分かりません。愚直に場合分けすることにしました。2:16、AC。
よくよく考えると、例えばvector<pair<char>> v={{'B','Y'},{'Y','R'},{'R','B'}};みたいにして、for eachで探索しても良かった気がします。何もかもが鈍ってる。


B問題

問題リンク：https://atcoder.jp/contests/abc477/tasks/abc477_b
推定diff：79（灰diff）
Nが高々100なので、愚直にforループを2回回せば終わりです。終わりなのですが、実装に、何故か手間取り......。
7:50、AC。


C問題

問題リンク：https://atcoder.jp/contests/abc477/tasks/abc477_c
推定diff：456（茶diff）
なんと、ここで2回WAを吐いてしまいます。「部分文字列」の意味を勘違いしてしまっていたのでした。おバカ！
部分文字列なので、Tの文字列長をnとして、S.substr(i,n)==Tとなるようなiを全て記録しておけばいいだけです。
40:32、AC。悲しすぎる。


D問題

問題リンク：https://atcoder.jp/contests/abc477/tasks/abc477_d
推定diff：946（緑diff）
......全く分かりません。マジでわかんない。
クエリ逆読みも考えますが、うまいこと処理できません。無為に時間が経ち、ふと、双対セグ木で良くない？　と気付きます。
vector<pair<int,char>> fd(n,{-1,'a'})のような配列に盤面情報を持たせて、q番目のクエリを以下のように処理することにします。
・Type1 query

int x; cin >> x;
if(fd[x].first==inf){ fd[x].first=q; }
else{ fd[x].first=inf; }

・Type2 query

char col; cin >> col;
for(int i=0; i<n; i++){ chmax(fd[i],{q,col}); }

要は各マスにつき{色が更新された時刻,現在の色}を持っておき、タイルが置かれた場合は更新時刻をinfにすることで、Type2をchmaxと捉えるとタイルの置かれたマスだけが色の更新がされなくなるのでした。どう考えても迂遠です。というか今気づいたのですが、単にvector<int>で色を管理していても双対セグ木で解けたような......。
さておき、Type2を上記のようにforループで回していると破滅するので、この全体にchmaxを行う操作が双対セグ木のapply操作で行えればいいわけです。
いや自分双対セグ木ライブラリ持ってねぇな......
仕方ないのでacl::lazy_segtreeに乗せることにします。ここで異常にもたつくなどして、結局83:16にAC。悲しいくらいひどい出来です。
悲しかったので双対セグ木ライブラリを作りました。
github.com
このライブラリを用いてACしたもの：https://atcoder.jp/contests/abc477/submissions/79599130


E問題（解けず）

問題リンク：https://atcoder.jp/contests/abc477/tasks/abc477_e
推定diff：1235（水diff）
明らかに'S->(頂点Nを経由せず)->T'と'S->(頂点Nを経由する)->T'のうち短い方を採用すればいいはずです。前者は単なる累積和、後者はダイクストラで出ます。
なぜか本番中、一切「ダイクストラ」のダの字も頭に浮かびませんでした。うぅ......


結果

解けた問題：A,B,C,D（4完） 自分のrating変化：1358->1332

つらい
これ年内に調子戻るのかなぁ......。何とか頑張りたいです、要は演習不足なので。つらい。
それではまた次回！　ここまで読んでいただきありがとうございました。

【ABC476】コワスギ銀行特製のグリッド問題に苦戦

ABC

今週の参加記担当の山田です！ABC476の参加記を書いていきます。

ABC476

コンテスト前の山田のレートは 2001 でした。本当に久しぶりの黄色安定期に入ってきました。なので今回は unrated での参加記になります。

コンテスト告知

この高めの配点と writer 陣を見て嫌な予感がしました。unrated でよかったかも。

苦手 writer を３人挙げろと言われたらこの３人を挙げます。特に先頭のひらきちという人物は難実装・非典型要素の大きい問題を出してくることが多いです（でも最近は落ち着いてきたと思います）。競プロ界隈では「コワスギ銀行頭取」「Σexの人」などの通り名で恐れられています。

A問題

問題文: A - Appender
Difficulty: 14
KCPCメンバー(rated参加者のみ)の正答率: 12/12

（C++ では）S.back()で最後の要素を取得できます。知らなくてもS[S.size() - 1]でできます。

0:30 AC。

B問題

問題文: B - Wild Card
Difficulty: 28
KCPCメンバー(rated参加者のみ)の正答率: 12/12

拡張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問題

問題文: C - Third Largest Number
Difficulty: 165
KCPCメンバー(rated参加者のみ)の正答率: 12/12

Wavelet Matrix で殴ります。

2:30 AC。

↑これになりました。

D問題

問題文: D - Automat
Difficulty: 860
KCPCメンバー(rated参加者のみ)の正答率: 10/12

K ドル紙幣しか受け付けないというありえん問題設定は sheyasutaka イズムを感じます。

A の自販機では自由に買えて、変な制限があるのは B の自販機です。

自販機ごとに買う優先順位は安い順でいいと思います。なので「A での購入個数」「B での購入個数」の二つさえ分かれば「購入可能か」は累積和でもなんでも自動的に求まります。両方固定しようとすると当然 {O}(N^{2}) 以上になって駄目です。A の方が単純な構造をしているので、B での個数を決め打ち全探索すれば高速化可能だと思います。

まだ詳細があやふやですが、手癖ですぐ解ける自信があったので実装開始しました。

A,B はソートされてあるものとします。C_i=\lceil B_i/K\rceil となる数列 C を作っておきます。これは各商品で消費される K ドル紙幣の枚数を表します。

B での購入個数を固定したのち、A でどれだけ買えるかの計算を {O}(\log N) ぐらいでやろうと思います。まず B,C の累積和で「K ドル紙幣が足りるかの判定」と「残金」を O(1) で計算します。これでA で何ドル使えるか分かったので、A の累積和上の二分探索でどこまで買えるかを {O}(\log N) で求めます。ちなみに累積和上の二分探索は直接やるより、区間和セグ木に乗せてセグ木上の二分探索でやった方が、山田的に楽なのでそうします。

9:25 AC。

E問題

問題文: E - Min-Max Swap
Difficulty: 964
KCPCメンバー(rated参加者のみ)の正答率: 9/12

まあ……やるだけ。

セグ木で区間最大値（最小値）を取得するのはよくありますが、今回は \operatorname{argmax}（＝最大値の添字）も取得したいです。それは素直にセグ木に（最大値、最大値の添字）を両方持たせておけばできます。セグ木に乗せられがちランキングで「最大値／最小値」「和」の次ぐらいに来るモノイドです。

16:21 AC。

添字を乗せなくともセグ木上の二分探索で \operatorname{argmax} を取得できることが、コンテスト終了後の Twitter に書かれていました。確かに。そっちのほうが山田にとっては楽です。

F問題

問題文: F - Chebyshev Cafe
Difficulty: 1728
KCPCメンバー(rated参加者のみ)の正答率: 1/12

本日のメインディッシュ問題。最終的に別解での AC となりました。

「住人の数が A_i\times B_j\pmod M で与えられる」「出力するのはハッシュ的なもの」という変な設定は入出力の削減のためだと思います。入出力は定数倍が重く、この巨大なグリッドを入出力させると言語やテンプレートによって有利不利が出まくってしまうので、それを解決するための設定だと思いました。

よってこの設定を利用することはなさそうです。各マスの住人の数がランダムに与えられても解ける解法で、普通にマスごとに答えを計算してから出力すべき値にするんだと思いました。

二通りの方針があると思いました。１つ目は、カフェの場所を固定して、かかるコストを累積和か何かで直接取得する素直な解法。２つ目は、人の場所を固定して、各場所のカフェへの寄与を 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 を変な方角に作用させる問題だと思います（実際そうです）が適当な方向に作用させても全然所望の形にならなくて絶望していました。

破滅の予感がしたので人固定方針を忘れて、カフェ固定方針を考えます。一個一個のカフェに関して独立に求めようとして難しいと判断してさっき棄却しました。独立に求めるのではなく差分更新を利用するのはどうでしょうか。

カフェを右に動かした場合にその差分を {O}(1) で求めたいです。

このように斜め方向の区間和的なものを O(1) で求める問題になりました。ただしただの区間和ではなく邪魔な重みが付いています。数列 A の添字の一次関数で重みが付いた数列の区間和は、A_i の区間和と iA_i の区間和を組み合わせる、という典型があるので一応求まることが分かりました。累積和を駆使します。

解けたと思います。でも実装がしんどそうです。i+j 固定、i-j 固定系（つまり斜め方向ごとの抽出）の添字はただでさえ頭を壊しやすいですし、それを組み合わせて色々やるのは大変です。

考察開始から 20 分ぐらいで実装開始。

i-j 固定のところを抽出する際に、std::vectorの負の添字を有効にするテクニックが便利です。

vector<int> A_base(101);
auto A = A_base.begin() + 50; // これで A の添字は [-50, 50] が有効
A[-10] = 10; // RE にならない

これで i-j 固定の扱いが楽になります。座標変換後の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問題 (間に合わず)

問題文: G - Increasing Popcount
Difficulty: 2477
KCPCメンバー(rated参加者のみ)の正答率: 0/12

B_{i}=\operatorname{popcount}(i) とした数列 B の範囲 [L,R) から、「狭義単調増加な部分列を何本取れるか」という問題です。それは「広義単調減少な部分列の最大長さ」（つまり LDS）と一致するという有名な話があります。ちなみにこの事実は競プロerが Dilworth の定理を履修する際に最初に見せられがちな具体例です。

miscalc.hatenablog.com

「\operatorname{popcount} の LDS を求めよ」っていう問題の方が元のよりやりやすいと思うのでこの言い換えで考えるのは確実そうです。LIS-DP をどうにかこうにかしてこのクソデカ制約でやるっぽいです。

ここから何も考察が進みません。\operatorname{popcount} の増減にしかない性質を利用するのが必須だと思いますが見当がつきません。

時間が多く余っている上にやることがないので大胆予想をします。最初に採用する要素の \operatorname{popcount} を決め打つと、あとは \operatorname{popcount} の大きいものを貪欲に採用していけばいい、という解法です。

半分ぐらい証明したつもりになっていましたが普通に嘘です。しかも思ったより実装が大変で、桁 DP をバグらせている間にコンテスト終了。

１５分後ぐらいに、想像した通りに完璧にコードが動いていそうという状況まで来ましたが、サンプルが合いません。しかも小さいケースでは全部合っているのでデバッグできません。

必殺ランダムテストを書いて、落ちる小さいケースを発見しました。

info.atcoder.jp

LDS で選ぶべき添字は (7,9,10,12) ですが、この解は先述のアルゴリズムで拾われません。

嘘だったので考え直します。

まず区間内の \operatorname{popcount} は、「動くビットのうち半分ぐらいが立っているもの」に非常に偏っていると思います（二項係数 \binom{n}{m} は m が n/2 に近いほど大きくなるため）。序盤の時点で考えていたことです。これを利用できませんか。

「動くビット」というのが曖昧なので、一旦考察対象を [L,R) がセグ木的区間である（つまり非負整数 i,j を用いて L=2^{i}j、R=2^{i}(j+1) で表せる）もののみに限定します。これで「動くビット」が均等に下位 n 個となります。

先述の通り「ほとんど同じ \operatorname{popcount} から選ぶことになる」と考えていましたが、セグ木的区間なら「全部同じ \operatorname{popcount} から選ぶことになる」なんてことはありませんか。それ以外の \operatorname{popcount} から取ってくる必要を感じません。

証明ができないので、さっきのランダムテストで書いた愚直解を再利用し、実験してみました。……どうやら全部同じ \operatorname{popcount} を選ぶのは正当らしいです。

よって与えられる [L,R) をセグ木的区間に分割すると、LIS-DP が \log R の多項式時間で可能です。

実装やり直し。一旦 {O}((\log R)^{3}) で書いて最大ケースで試すとめっちゃ遅かったので、DP を累積 max で高速化して {O}((\log R)^{2}) に落として提出。

150:36 AC。50分オーバーで未証明 AC。

公式解説を開いたら、山田ができなかった証明に知らない知識が出てきました。後で履修します……。

コンテスト結果

成績証

G 問題以外の六完 (55:01 ノーペナ)、パフォーマンスは 2189 相当でした。正直とりあえず黄パフォあれば OK ということで。

順位の推移

E 問題まで癒やしセットだったのに F 問題がコワスギ問題すぎてやられました。

↓画面録画

https://youtu.be/LIcZD6gt50E

【ABC475】茶diffで実装方針を見誤り、highest付近で下降...

ABC

こんにちは、はるはるです。

今回はABC475の参加記です。

ABC475

コンテスト前のレートは1566でした。ABC470で爆勝ちしてhighestが†1573†になり、入青リーチの激アツ状態だったのですが、前に出たABC472で少し冷えてしまいました。それでも自己ベ相当のパフォーマンスを出せば入青なので、入青リーチ継続です。アツいですね。

配点は100-200-300-400-475-525-575です。525は最近はほぼ解けないので5完速解きして青パフォを狙いたいところです。

A問題

問題文:A - mnclr

推定diff: 18

KCPCメンバー(rated参加)のAC数: 12/12

1文字ずつリストに入れ、その間に"o"を挿入します。最後の"o"は出力時にスライスで取り除くようにしました。

00:38にAC。

B問題

問題文:B - Change

推定diff: 75

KCPCメンバー(rated参加)のAC数: 12/12

最初、「各会計でおつりの枚数が最も少なくなるように硬貨を含めてお金を出す」だと思い、混乱しましたが、よく見たら出すのは1000円札だけでした。

まずは支払う額を決めたいのですが、1000円紙幣の枚数は$A_{i}$を$1000$で切り上げ除算したらいいですね。

$A$を$B$で切り上げ除算する方法はいくつかあって、(A+B-1)//Bだったり、$A$が$B$の倍数でないときだけ$A//B$に1を足したりでもいいのですが、自分は-(-A//B)が気に入っています。

負の切り捨て除算の仕様の関係でC++では使えないのがネックですが...

お釣りの額が決まれば、あとは100円、10円、1円の順に取れるだけ取ります。結果的には、お釣りの額は1000円未満なので、お釣りをx円とすると、x//100枚、(x//10)%10枚、x%10枚もらえますね。

05:53にAC。

C問題

問題文:C - Walk the Line

推定diff: 549

KCPCメンバー(rated参加)のAC数: 12/12

$O(N^{2})$まで通るので区間DPか...？と思いましたが、よく考えると最適な動き方としてありえるのは、

  • ずっと右に進む
  • ずっと左に進む
  • 右にある程度進んでからずっと左に進む
  • 左にある程度進んでからずっと右に進む

の4通りしかありません。なのでこれらを全探索すればいいです。

実装上は、最初に右に行くケースのみ考える関数を作っておけば、配列全体を反転して渡すことで最初に左に行くケースを計算できます。

$O(N^{2})$が間に合うことを忘れており、にぶたんを書きました。

20:45にAC。

こんな感じで関数化することで場合分けを減らすテクニックはC、D問題で頻出です。

D問題

問題文:D - Alphametic Prime

推定diff: 741

KCPCメンバー(rated参加)のAC数: 11/12

$S$が7文字以下なので、全探索ができそうです。

自分は、条件を満たす数字を全探索し、それが素数か判定する、という方法で実装してしまったのですが、週明けにKCPCの某メンバーと感想戦をしていたところ、「素数を全探索し、それが条件を満たすか判定する」という方法の方がかなり楽に実装できることに気づきました。

コンテスト中に10進数のbit全探索のようなものを書いた挙句バグらせて2ペナを食らってしまったので、かなり悔しいです...

今回はE以降が青diffと難しかったので、4完した人の中でもタイムによってかなりパフォーマンスに差が出たようです。

42:57にAC。

E問題

問題文:E - Quiz Competition: Qualifiers

推定diff: 1737

KCPCメンバー(rated参加)のAC数: 7/12

あるクエリの結果が後続のクエリ計算に影響を及ぼすので、クエリはそれぞれ処理しないといけなそう...ということで、各クエリにかける計算量を$O(K)$で考えてみます。

かなり長いこと考察に時間を使ってしまったのですが、正解したときはo、間違えたときはxとしてそれぞれの参加者のリザルトを$K$文字であらわしたとき、これらを辞書順に並び替えると、

「予選通過者」「未確定者」「予選脱落者」はすべてかたまってこの順に並ぶ、ということがわかりました。最後の問題が終わった時未確定者はいなくなるので、この文字列を追加、削除、辞書順での二分探索ができるようなデータ構造を使えばよさそうです。

間に合わないだろうと思いつつ他に実装方針も思い浮かばなかったので、SortedMultiSetを使い、文字列の代わりにタプルを使って管理するコードを書き提出したのですが、案の定TLEになってしまいました。WAも出てしまい、そのままコンテスト終了...

解説を見てみると、pythonなら多倍長整数を使って各問題の正誤を2進表記で表した1つの整数持つことで、数字の大小が辞書順と一致し、高速に管理できるようでした。試してみたところ、AC。

Dに時間をかけすぎてしまったのがよくなかったかもしれません...

コンテスト後

結果は43+5*2分4完で、パフォーマンスは1307、レート変化は1566→1543(-23)でした。

highest付近での-23はとても痛いです...
また入青が遠のいてしまいました。

夏休み中は結構積極的に水青diffを解いているので、近いうちに成果が表れると信じて気長にやります。。。

【ABC474】お久しABC

こんにちは、柑橘です。
今回はABC474参戦記となります。7月～8月、学部の方が色々と忙しくてというか勉強してこなかったツケが回ってきて自分は一切ABCに出られていませんでした。2か月ぶりのABC、果たして勘を取り戻すことはできるのか......！？

ABC474

配点：100-200-300-400-450-500-575

A問題

問題リンク：https://atcoder.jp/contests/abc474/tasks/abc474_a
推定diff：15（灰diff）
コンテスト開始、なんとatcoder-cliにログインできていないことに気付きます。結局この日はatcoder-cliを使用できずにコンテストをやる羽目になりました......。
なお、何故か手元の環境からはAC counterも消滅しており、今回KCPCメンバー(rated参加)のAC率は出せていません。すみません......。
気を取り直して、1から3まで走査してXと異なる瞬間に出力してループをbreakすればよいです。2:47、AC。


B問題

問題リンク：https://atcoder.jp/contests/abc474/tasks/abc474_b
推定diff：65（灰diff）
客を10人ずつ前から区切ってグループにすることを考えます。グループに左から0,1,...とindexを振るとして、i番目のグループ内の客の座席番号のindexの最大値、最小値をそれぞれmaxid[i],minid[i]とすると、全てのiについてmaxid[i]<minid[i]となればよいです。実装にやや混乱して、11:08、AC。
......今気づいたのですが、この解法はどう考えても迂遠です。客を10人ずつ区切って、グループ内で客の座席番号を昇順にソートしていくことにします。
ソート後の列が1,2,...,nと一致すればYes、そうでなければNoを出力すればいいだけの問題でした。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; cin >> n;
    vector<int> p(n);
    for(int i=0; i<n; i++){ cin >> p[i]; }
    //10人グループを各グループ内でソート
    for(int i=0; i<n; i+=10){
        sort(p.begin()+i,p.begin()+min(i+10,n));
    }
    for(int i=0; i<n; i++){
        if(p[i]!=i+1){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}


C問題

問題リンク：https://atcoder.jp/contests/abc474/tasks/abc474_c
推定diff：243（灰diff）
突然ですが、長さN+Qの列Vを考えます。列の先頭N要素は与えられた列Pと一致しており、末尾Q要素は0埋めされています。
このとき、要素からその要素のV上のindexを返すような配列idを持つことにして、あとlast=n-1と初期化されている変数lastを持って、本問の各クエリは以下のように言い換えられます。

aを入力;
int prev_id=id[a];
V[prev_id]=0; //aが元々いた場所を0埋めして
V[last+1]=a; //列の末尾に置く
id[a]=last+1; //idも更新
last++;

我ながらなかなかうまい解き方だったのではないかなぁと思います。もちろん両端の要素を持つような構造体（スタックを実装するときとかに使うやつ）を用いても良いと思います。16:14、AC。

//参考: スタックとか動的セグ木とか実装するときに使うやつ
struct node{
    int val; //値
    node* left,right; //左右の要素
    //本問では値->nodeを管理するような配列を持てばいいでしょう
};


D問題

問題リンク：https://atcoder.jp/contests/abc474/tasks/abc474_d
推定diff：389（灰diff）
構築だ！　と一瞬身構えますが、a[i]>b[i]となる石についてはw[i]=1e18、逆にa[i]<b[i]となる石についてはw[i]=1とすればいいだけでした。
総和の大小判定にはオーバーフローを警戒して__int128_tを使いました。便利でありがたすぎる。25:41、AC。
簡単な割に各実装に時間がかかっています。勘が鈍ってる！


E問題

問題リンク：https://atcoder.jp/contests/abc474/tasks/abc474_e
推定diff：1153（緑diff）
dpか！？　いや違いそう......。正直さっぱり方針が立ちません。
立たないまま1回WAを吐いたりしつつ30minくらいが立ちます。こうしてあなたたちは競プロ戦争に負ける。ちなみに時間戦争に～の方は未読ですがサムネにしました。ほら、表紙が格好良いから......。
とりあえず何かしらの貪欲的な解き方はしそうで、列をソートすることを考えます。クーポン適用時の値引き幅をd[i]=a[i]-b[i]として、dの昇順（値引き幅が小さい順）に列をソートします。dが等しい場合は......え～っと......aの降順（素の値段が高い順）とかでいいんじゃないか？
このときできた列の左側の商品をなるべくクーポン取得のために買って、右側の商品にはクーポンを適用したいです。同じ商品を複数買ってどれかは素の値段で買いどれかはクーポン適用で買うみたいな挙動は明らかに無駄なので、境界をどこかに取って、ここから左は購入、ここから右はクーポン適用で購入、みたいな挙動をすればいいことに気付きます。
問題は素の値段で買う商品を何個にすればいいかですが、例えば左からx種類の商品を合計何個買えばいいかについて、右側N-x種類の商品はそれぞれ1つずつクーポンを適用して購入します。ということは左からx種類の商品は合計max(x,N-x)個買えばいいです。条件よりx種類いずれも少なくとも1個は買う必要があるとして、N-x>xの場合、残りN-2*x個をどう処理すれば良いかが問題になりますなりません一番安い種類の商品を追加でN-2*x個買えばいいだけです。
あとはこれを書くだけだったのですが、なんかめちゃくちゃ実装に手間取った挙句2つ目のWAを吐いてしまい、そんなこんなで87:30、AC。
今にして思うと、総和や最も安い種類の商品取得に関してはあまり頭を使わずにseg木に載せた方が手早かった気がします。せつない。


F問題（解けず）

問題リンク：https://atcoder.jp/contests/abc474/tasks/abc474_f
推定diff：1911（青diff）
当然コンテスト時間内に解けるわけがなく、解説を見ながらコンテスト後ACしました。
この問題、解法が個人的にはかなり面白かったです。数iを選んだ回数をc[i]とおくとして、最終的に全ての数の値をxにできたとき、任意のiについて次の計算式が成立します。
x-a[i]=c[i]+c[2*i]+c[3*i]+...
これをc[i]について変形すると、c[i]=x-(a[i]+c[2*i]+c[3*i]+...)となります。よって、iを降順に走査することで、c[i]=p[i]*x+q[i]となるようなp[i],q[i]が得られます。
ここでc[i]>=0なので、p[i]*x+q[i]>=0を各iについて解くことでxの取りうる値の範囲が求まり、x-a[1]=c[1]+c[2]+...+c[n]より、求める答えは(xの最小値)-a[1]です。計算量は各iについてc[2*i]+c[3*i]+...を計算するステップ数の総和に等しく、要はN/1+N/2+...N/N（調和級数）でO(NlogN)となります。すっげ～～。
コンテスト後に提出したACコード


結果

解けた問題：A,B,C,D,E（5完） 自分のrating変化：1397->1391

#Atcoder最高の瞬間

腕の鈍りをはっきりと自覚した回となりました。ここから頑張って調子を戻していきたいです！
ここまで読んでいただきありがとうございました。また次回もよろしくお願いします。

【ABC473】全完！だが足りない

こんにちは、みうねです！今回は AtCoder Beginner Contest 473 の参加記です。

またまた青落ちしてしまいました。rated ABCでレートを稼いで黄色復帰したいです。

コンテスト前のレートは 1966 で、2267 perf 以上で再入黄です！

船の中でこのブログを書いているため、図が用意できず文字だけになります。すみません。

宣伝

宣伝です！TUNA Camp 東京Stage の開催日が 9/23~9/27 に迫っています！参加無料で様々な大学の競プロサークルが主催するコンテストにオンサイトでチーム参加できる楽しいイベントなので、どなたでも是非ご参加ください！

tunacamp.connpass.com

tuna.camp

A問題

問題ページ: A - Second Half Sum

diff: 13

KCPCメンバー（rated）のAC率: 11/11

累積和を取れば良いです。

00:40 AC。

B問題

問題ページ: B - Old Maid

diff: 31

KCPCメンバー（rated）のAC率: 11/11

奇数枚ある数字は1枚ずつ残ります。

02:17 AC。

C問題

問題ページ: C - Change Schools

diff: 120

KCPCメンバー（rated）のAC率: 11/11

転入前で一番人数の多いクラスの人数を $x$ 人とすると、 $x$ 人または $x-1$ 人の人数のクラスに転入すると嬉しくなります。

04:13 AC。

D問題

問題ページ: D - Coefficient Stair

diff: 120

KCPCメンバー（rated）のAC率: 8/11

よくわからないのですが、D問題だしとりあえずDFSで全列挙せよということな気がします。

09:22 TLE。

あれれ、単に前からDFSで列挙するだけではダメなようです。ここで制約を読むと、「条件を満たす数列が $3 \times 10^5$ 個以下であるような入力のみが与えられます」とあります。

前から単にDFSすると、条件を満たす数列以外の数列も大量に走査してしまうので、この制約をうまく利用できません。一方、後ろからDFSしていくと、最後の1つは残りの和から自動的に決めることができます。これなら条件を満たさない数列まで最後まで走査する必要がなく、条件を満たす数列を効率よく全列挙できます。

14:11 AC。

E問題

問題ページ: E - K-Divisible Subarrays

diff: 966

KCPCメンバー（rated）のAC率: 9/11

総和が $K$ の倍数になる連続部分列を互いに重なることなくできるだけたくさん選びたいです。

このような区間は $O(N2)$ 個存在し得ますが、区間を互いに重ならないようにできるだけたくさん選ぶ問題は「区間スケジューリング問題」なので、右端が最も左にある区間を貪欲に選んで良いです。したがって、右端を左から順に見ていき、その右端を持つ区間が存在すればその場で選ぶことにすれば、区間をすべて列挙する必要はありません。

累積和を $\bmod K$ で考えると、総和が $K$ の倍数になる区間は、両端に対応する累積和が等しい区間です。そこで、各累積和の値について最後に現れた位置を持っておけば、現在位置を右端とする区間のうち、直前に選んだ区間と重ならないものが存在するかを判定できます。

21:19 AC。

F問題

問題ページ: F - A/AB Insertion

diff: 1303

KCPCメンバー（rated）のAC率: 7/11

括弧列の問題っぽいです。A を開き括弧、B を閉じ括弧だと思うと、AB を挿入することだけで得られる文字列がいわゆる「正しい括弧列」で、そこにさらに A を挿入することだけが許されています。

左からの累積和を考えて、A ならば $+1$、B ならば $-1$ とします。A の挿入では $+1$ が、AB の挿入では $+1,-1$ が挿入されるので、これらの操作によって得られる文字列では、すべての累積和が $0$ 以上である必要があります。また、逆にこの条件が成り立っていれば、必ず上記の操作でその文字列を得ることができそうです。

したがって、ある部分文字列がこの条件を満たすかどうかは、その部分文字列の先頭を $0$ として見たときに累積和の最小値が $0$ 以上であるかを調べれば判定できます。

文字列を1点更新すると、それ以降の累積和がすべて $+2$ または $-2$ されます。そのため、累積和の区間加算と区間最小値取得ができればよく、Range Add Range Min の遅延セグメント木を使えば処理できます。

31:11 WA。

コードを睨むと境界処理をミスっていることに気づきました。

31:18 AC。

G問題

問題ページ: G - Wipeout

diff: 1974

KCPCメンバー（rated）のAC率: 1/11

$\mathrm{mod} ~ 998244353$ で600点の場合、十中八九FPSです。

まず、最適な戦略がどういうものかを考えます。

  • 次に欲しいカードが見たことのあるカードである場合、そのカードをめくる

  • 次に欲しいカードが見たことのないカードである場合、見たことのないカードのうち1枚を選んでめくる

という戦略にするのが良さそうです。1つ目の操作には自由度がありませんが、2つ目の操作には自由度があります。

そこで、あらかじめ各カードに優先順位をつけておき、見たことのないカードをめくるときには最も優先順位の高いものをめくることにします。この優先順位に沿ってカードを並べ、$P_i$ を $i$ 番目に優先してめくるカードに書かれている数字とします。すると $P$ は $1,2,\dots,N$ の順列になります。

このとき、ある $i$ について、$P_i$ が $P_1,P_2,\dots,P_{i-1}$ にまだ現れていない正整数のうち最小のものであるとき、またそのときに限り、そのカードは初めてめくったときに食べることができます。

つまり、$P_i=\mathrm{mex}(P_1,P_2,\dots,P_{i-1})$ であるときに1回で食べることができます。ただし、ここでは $\mathrm{mex}$ を「まだ現れていない正整数のうち最小のもの」という意味で使っています。

逆にこれが成り立たないとき、そのカードは初めてめくったときには欲しいカードと一致せず、2回目にめくったときに食べられます。

さて、$i$ 番目のカードを1回めくるだけで食べることができるとき o、2回めくらないと食べられないとき x とした文字列を考えます。このとき、$($o の個数$)+2\times($x の個数$)$ が操作回数です。したがって、操作回数が $K$ 回であるためには、o の個数が $2N-K$ 個であれば良いです。

例えば、xxoxxxoxo という文字列を考えます。最後の文字は必ず o になることに注意してください。

この文字列が得られるような順列の総数は、$(8\times7)\times(5\times4\times3)\times1$ となります。これを分子が $9!$ になるように書き直すと、$\displaystyle \frac{9!}{9\times6\times2}$ となります。

一般に、長さ $N$ の文字列で o の位置を $p_1<p_2<\dots<p_t=N$ とすると、この文字列が得られるような順列の個数は $\displaystyle \frac{N!}{N(N-p_1)(N-p_2)\cdots(N-p_{t-1})}$ となります。

したがって、o が $t$ 個あるような優先度順列の総数を考えると、分母に現れる $N-p_1,N-p_2,\dots,N-p_{t-1}$ は $1,2,\dots,N-1$ から異なる $t-1$ 個を選ぶことに対応します。

最終的に欲しいのはこの確率なので、全体を $N!$ で割ります。つまり、$\displaystyle \frac11,\frac12,\frac13,\dots,\frac1{N-1}$ から異なる $t-1$ 個を選び、その積の和を求めれば良いことになります。

o の個数は $2N-K$ なので、最終的には $\displaystyle \frac1N x\prod_{i=1}^{N-1}\left(1+\frac1i x\right)$ の $x^{2N-K}$ の係数を見れば良いです。

これでやっと見慣れたFPSの典型問題になりました。

88:31 AC。

時間をかけすぎました。解説を読むと、もっと分かりやすい考え方があったみたいです。

結果

全完でしたが、perfは 2094 と、再入黄には届きませんでした。

早く黄色に戻りたい！そしてARCでも勝ちたい〜（このABCの次の日のARC++は青パフォでした）

【ABC472】久しぶりのアンレ参加記【KCPCブログ】

ABC

はじめに

こんにちは！jastawayです。ABC472の参加記です！！

ABC473の後に先週のKCPCブログの担当だったことに気づきました🙇

はじめに告知です！

京大ICPCチーム「bogosort」主催の有志コンテストをAtCoder上で開催させていただくことになりました！

Div.1 / Div.2 同時開催予定なのでぜひ参加してください！

問題セットはほとんど決まっており、writer作業をがんばって進めています！

目次

ABC472

参加前の私のレートは2017でした。

ABC470で36位カンストパフォを取り無事再々々々々々々々々入黄！

ARC連敗も一応ストップしてギリギリ耐えています。

なので久しぶりのアンレ参加記です。ABC396の参加記以来？

いつ青落ちするかわからないのでABCは基本休みません。

配点は、100-200-300-400-450-525-600でFまで早解きをしたいですね。

以下、各問題の考察&感想です。

A問題

問題文: A - A

KCPCメンバー(rated 参加)のAC数: 11/11

diff: 14

for文で A 以外を . に変えるだけです。

for(auto& c : S) if(c != 'A') c = '.';

のように書きました。

0:20に提出、AC。

20秒で解けていいですね！2位らしいです！

B問題

問題文: B - Break a Stick

KCPCメンバー(rated 参加)のAC数: 11/11

diff: 40

切れ込みを入れる箇所を全探索すればよいです。

毎回総和を取るのでもいいですが、 $L$ の総和をはじめに取っておいて、前から加算しながら見るとこで線形時間で求められます。

累積和を取るのでもいいですね。

1:59に提出、AC。

C問題

問題文: C - On a Diet

KCPCメンバー(rated 参加)のAC数: 11/11

diff: 183

愚直にシミュレーションすればよいです。

$i$ 日目に食べなかったときに $A_{i} \leftarrow 0$ と書き換えておくことで、 $A_{i-M}$ を引くことでひとつずらすことができます。

5:23に提出、AC。

添字とかでちょっと迷って時間がかかりましたが誤差。

D問題

問題文: D - Bomber Mad

KCPCメンバー(rated 参加)のAC数: 10/11

diff: 605

各行、列に爆弾があるかどうかを調べておくことで、安全な空マスを列挙できます。

その後、安全なマスから多始点BFSをすることで、安全な空マスへの最短距離を求められるので各マスの判定ができます。

9:03に提出、AC。

E問題

問題文: E - Odd Cycle

KCPCメンバー(rated 参加)のAC数: 8/11

diff: 1029

奇閉路が存在しないことと二部グラフであることは同じです。

二部グラフの判定は適当な始点からDFSなどで色を2色で塗っていくことで判定できます。

同じ色が隣り合うところをDFSで発見できたとき、そこでDFSを打ち切って、バックトラックで閉路を復元できます。

DFSをするときに始点からのパスを持っておくと楽に復元できます。

16:02に提出、AC。

F問題

問題文: F - Centroid of a Slice

KCPCメンバー(rated 参加)のAC数: 3/11

diff: 1707

Eまで結構早く解けていていいです。Fも早解きしたいです。

AtCoderではめずらしい幾何の問題です。

最初、頂点の平均で良くね？となって累積和を書いて実装しましたが、サンプルが合いません。

とりあえず凸多角形の重心を調べるとWikipediaがあったので、なにかヒントがないかなと読むとちょっと下の方に多角形の重心の式がそのまま書いてありました。

この和を累積和で持つとできるので、実装します。

実装を終えてサンプルを試しますが合いません。

どうせこうやろと適当に添字を決めていたのでそこかな？と思って色々いじってみますが、合いません。

それもそのはず、単に累積和の差を使っていますが、 $v \to u$ の辺の寄与を入れていませんでした。

場所が分かったので修正して提出！

39:14に提出、AC。

ミスに気づくまでちょっと時間がかかりましたが、無事通りました。

G問題

問題文: G - Cascading Grid

KCPCメンバー(rated 参加)のAC数: 1/11

diff: 2018

左右にも広がるので、各段は # で区切られたところだけを考えて良さそうとなりました。

上には影響しないので、下から各段の状態を持ってdpができそうだと思いました。

各段の状態が $2^{30}$ 通りあって難しいなと最初思いましたが、# で区切られたところを考えると、隙間は高々 $15$ 通りしかないので、 $2^{15}$ となって管理できそうです。

しかし、次の段との遷移を考えると $2^{15} \times 2^{15}$ で厳しそうです。

意外と状態数が少ないと踏んで状態を map で管理して提出してみますが、3ケースTLE😭

ゼータ変換などでできそうだと思いましたが、あまり得意でなく、 $2^{30}$ になってしまってうまくできませんでした。

これまで、サイズ $W$ 固定で管理していたので、大変でしたが、頑張って # で区切って長さが高々 $2^{15}$ の vector で管理できるようにしました。

これでゼータ変換などができそうでしたが、あまり自信がないので、部分集合を $O(3^W)$ で列挙するやつで通るやると思って実装します。

サンプルが合ったので提出！

98:40に提出、AC。

全完です！！！

コンテスト終了後、これが燃やす埋めるだと聞いて、確かにすぎました。

実装も簡単なので思いつきたかったです・・・

コンテスト結果・感想

7完（108:40）で 287位、2086パフォでした。

青落ちしたくないですが、落ちても帰ってこれそうで少し安堵。

ARCが本当に勝てないので勝ちたいです！

2連続ARCがありますが、青落ちしたくない😭

【ABC471】因縁の高難易度F問題に完全勝利もパフォーマンス激渋

ABC

今週の参加記は山田のABC471です！

ABC471

連続21回目の rated-ABC です。（助けて！）

先週は１日だけ黄色状態に戻れたものの、翌日の ARC226 で即剥奪されました。

コンテスト前の山田のレートは 1994 でした。復帰に必要なパフォーマンスは 2050 で、コンテスト中普通にしていればそのまま復帰できると思います。

ここ数ヶ月は配点が信用ならない傾向にありますが一応確認しておくと 100-200-300-400-450-550-600。E 問題までは普通 or 簡単めの配点で F 問題が難しいっぽいです。ですが最近特に E までに落とし穴がありまくるので、ここをいかに躓かずに駆け抜けられるかでも差がつきそうです。また G 問題を通せる可能性も低くなく、F 飛ばし 6 完で一気に上位に浮上なんてルートもありえます。

A問題

問題文: A - Nice or Nein

Difficulty: 19

KCPCメンバーのAC率: 10/10

条件を a == 9 || b == 9 と誤読して若干ロスしました。

1:42 AC。

B問題

問題文: B - Survey Tabulation

Difficulty: 48

KCPCメンバー(rated参加) のAC率: 10/10

区別しない文字列を文字列として同じにしたいです。小文字か大文字に揃えれば正規化できます。

黒魔術を使います。

ASCII における英大文字／小文字は二進数表記 2^{5} の位のみによって区別されます。例えば 'A' が 1000001 と対応するのに対し、'a' は 1100001 です。

よって char c の英大文字／小文字の切り替えは c ^= 32 とすればよい、というテクがあります。大文字に揃える場合は c &= ~32 、小文字に揃える場合は c |= 32 です。

しかし何を思ったのか山田は c &= 32 と書いてしまいました。これでは {2}^{5} の位以外を全部ゼロにするというアホ処理になってしまいます。

3:02 WA。

びっくりしました。この時は本当に何が間違っているか分からなかったので、if ('a' <= c && c <= 'z') c += 'A' - 'a'; と普通のやり方に書き換えました。

4:33 AC。

この崖の予感がする回でペナルティはまずいです。

C問題

問題文: C - Cookies and Greedy Takahashi

Difficulty: 301

KCPCメンバー(rated参加) のAC率: 10/10

列上で「最も近くにある有効なもの」を取ってくるタイプの問題は std::set 想定がちです。

しかし山田はこういう問題はセグ木上の二分探索で片付けています。境界の調整が難しいのでアンチの多い典型だと思いますが、慣れれば楽でかつ応用性が高いと思います。

開始地点である座標 0 も含めて座標圧縮しておき、現時点での各地点のクッキーのあるなしを 0,1 に置き換えたものを Max 取得セグ木に乗せます。

二分探索は ACL と同じ設計なら、cur を現在の座標（座圧後）とすると、

int L = seg.min_left(cur, [](int mx) { return mx <= 0; }) - 1;
int R = seg.max_right(cur, [](int mx) { return mx <= 0; });

これで右・左のクッキーの座標（座圧後）が取得できます。

実装完了して何故かサンプルが合わないと思っていたら、何故か座圧に座標 0 を追加するところ座標 1 を追加していました。何故？？？ ３分半失いました。

13:37 AC。今日はもうダメですか。

D問題

問題文: D - Chargers

Difficulty: 570

KCPCメンバー(rated参加) のAC率: 10/10

状況が複雑な上、競プロにおいて慣れない用語がいっぱい出てきて、把握に時間がかかりました。

バッテリーの最大容量は V です。

この書き方で大量のバッテリーを扱う問題なのはすごいと思います。

問題を競プロ的な捉え方にすると、整数（残量を表している）の多重集合に対して追加・最大値取得・最大値削除・全体加算（ただし V に到達したら一定）を行う問題です。全体加算がなければ優先度付きキュー以外の何物でもないです。

全体加算をキュー内の値に一個一個直接やるのは無駄です。「これまでの加算の合計」と「加算される前の値」を別々に持っておくパターンです。今回は時刻 0 での残量を「加算される前の値」とします。途中から追加される場合や、V に到達した場合も、全部毎秒 1 ずつ残量が増えていると考えて大丈夫そうです。

言い換えると「（最大容量無限と仮定した場合の）現在の残量 -t」を優先度付きキューに入れます。

17:44 AC。

E問題

問題文: E - Sum of Square of Sum

Difficulty: 990

KCPCメンバー(rated参加) のAC率: 7/10

総和の 2 乗って書いてあるのでとりあえず展開した光景を考えます。大量の各項の寄与を求めたいです。

i を固定した場合の A_i^{2} が寄与する回数は \binom{N-1}{K-1} で一定です。i,j (i\ne j) を固定した場合の A_i A_j が寄与する回数は \binom{N-2}{K-2} で一定です。（N-2,K-2 が負の場合はゼロであるものとする）

よって \sum_{i} A_i^{2} と \sum_{i\ne j} A_i A_j をそれぞれ求めて、それぞれの寄与回数をかければいいです。前者は普通にそのまま求め、後者は累積和でも (\sum A_i)^{2}-\sum A_i^{2} でもなんでも求まります。

23:50 AC。今日の癒し枠でした。

────────

ここで初めて順位表を確認しました。

現時点でのパフォーマンスは 2122 程度でした。悪くはないものの、B 問題のペナルティと後ろの問題を通した人で抜かされていき、青 perf まで落ちるかもしれないです。

そして F 問題の現時点の AC 人数は 10 人、G 問題は 0 人でした。まだ序盤なので最終的にどういう難易度になるのかよくわかりません。ただ今日は F 問題と心中することにするのが良さそうです。

前の山田担当回で話したように、最近頻出の難しめの F 問題を山田は落としまくっており、嫌な予感がします。

F問題

問題文: F - Concat (maximize)

Difficulty: 1895

KCPCメンバー(rated参加) のAC率: 2/10

開始 24 分で F 問題と対峙。時間はたっぷりあります。

こういう辞書順が絡む問題は嘘解法祭りになりやすいですが、丁寧に合法な考察を繰り返せば確実に通せると思います。頑張ります。

「全て選んで辞書順最小化（最大化）」の場合は有名問題です。S_i+S_j\leq S_j+S_i (i\lt j) が成り立つように特殊なソートをします。以降これをソート①と呼びます。

drken1215.hatenablog.com

全部あらかじめソート①しておけば、使う文字列集合を決めれば最適な順番はその添字順になるということになります（同じ長さの文字列同士なら辞書順比較がそのまま大小関係になっています）。この時点で LCP Array などを使ってえげつない複雑さに脳味噌を破壊しながら文字列の比較をする系なんじゃないかと身構えました。（が、実際は LCPA を使うことはありませんでした）

というわけでどんな文字列集合が最適解の候補になるか考えます。まず答えの桁数を知りたくなります。最大桁数を達成していない解はまず最適解の候補としてありえません（ABC443F をどうしても自力 AC できなかった悔しさを覚えていたのですぐ桁数に着目できました）。leading zero がない場合は簡単で、長さ上位 K 個の文字列を取ってくれば最大桁数になります。

leading zero について考えると頭を壊しかけたので、一旦 1 から 9 までしか入力に含まれない場合を考えてみました。

同じ長さのもの同士でどういう優先順位で採用すればいいか考えるのが課題です。辞書降順で良い気がしました。長さが違うもの同士を適当に扱うと崩壊するのであって、同じ長さならシンプルなやり方でいい思いました。

「◯◯の形をしている最適解が必ず存在する」を証明する際は、「◯◯の形でない最適解」が存在すると仮定し、そこから解を悪化させずに「〇〇の形」に修正していけるという背理法チックなやり方になりがちです。今回は（長さ降順、辞書降順）の順に採用していくことの最適性を証明したいです。長さ降順で採用していいのは確かなので、「（長さ降順、非辞書降順）で取ってきた最適解から、（長さ降順、辞書降順）への最適解に修正可能」を証明します。これは「修正しなければならない区間」の辞書順だけを、他の区間に一切触れることなく増やすことが必ずできます。証明できてると思います。

以降（長さ降順、辞書降順）によるソートをソート②と呼ぶことにします。

このように leading zero 非考慮の場合は思いの外すんなり解けました。なのでこの問題の AC 人数を減らしている主要因は leading zero の扱いだろうと思いました。

選んだ二個目以降の文字列に関しては今までの考察がそのまま適用できそうです。leading zero が二個目以降まで伸びている場合は全部ゼロの場合のみです。よって一個目を決め打ち全探索し、残りが自動的に決まるのでそれを比較、というやり方で一旦正当な多項式解法が得られると思いました。

難しいのは比較パートを準線形に落とすところですが……。まあ先述の通り LCPA ゴリ押しでいけると思います。

残り 53 分ぐらいで実装開始。余裕があるように見えますが、比較の詳細詰めで沼ると思うので集中していきたいです。またこの問題の現時点での Difficulty 予想が青黄境界ぐらいとなっており、あんまり遅いと黄色に戻れないかもしれません。

まずソート②の上位 K 個をソート①して連結させたものを作りました。以降これを文字列 T と呼ぶことにします。「（決め打った一個目の文字列）+（T からある区間を抜かしたもの）」が最適解の候補です。T を LCPA ライブラリに突っ込むところまで書きました。

いよいよ今の解法の最難所、「値の比較」を LCP Array を駆使して実装するぞ、と覚悟を決めました。しかし比較の光景を具体的に想像してみると、決め打つべき候補はそんなに多くないのでは？ と思いました。もしそうなら愚直に比較しても大丈夫です。

具体的には、長さが同じものの中では辞書順最大のものしか決め打つ候補にならないのではないかと思いました。

長さが同じ二つの文字列 s,t をそれぞれ一個目として選んだものを比較してみます。s\ne t の場合、生成される文字列を左から比較していく光景を想像した時、s,t 部分の比較中に必ず決着が付きます。よって s,t のうち小さい方は負ける運命なので候補にしなくて良いです。s=t の場合は生成される文字列が変わらない（気がする）ので、片方は捨てて良いです。

よって LCPA は要らないです。危うく沼解法に走るところでした。

公式解説ではここから更に候補を 2 個に絞っていました。言われてみれば当たり前ですが、考察が積み上がっていくにつれて状況を脳内でうまく回せなくなっていました。

66:24 WA。うわ。

速攻で順列全探索の愚直解を書き、ランダムテストを回しました。

↓参考

info.atcoder.jp

すぐに実装ミスが二つ見つかりました。大雑把に書くと

  • 順列と逆順列の混同

  • 比較を単に文字列の比較でやってしまった

根本的な論理ミスはなくて良かったです。

77:08 AC。助かった。

苦手な理詰めゲーを（考察面は）ランダムテストなしで詰め切れたのは成長を感じます。

しかし……。通した時点でパフォーマンスは 2136。時間をそこそこ残した AC にも関わらず思ったより高くないです。しかもペナルティ２個によってどんどん抜かされていきそうです。

────────

こういう嘘解法祭り問題は通常マルチテストケースで作られます。writer が想定していない嘘解法を物量作戦で確実に落とすためです。なのでこの問題がシングルテストケースなのは、テストケース作りへの自信が感じられて格好いいと思っていました。

ところが実際は嘘で通されまくっていたらしいです。格好いいどころか最もダサいパターンでした。

こういう場合コンテスト後に After Contest というテストケースが公式に追加されます。（が、コンテスト中の順位は不動）

山田のコードはこのケースも通過しました。

もしテストケースが強ければどれくらいパフォーマンスが上がったかは分かりませんが、フレンズさんは山田の恨みを買ってしまいました。

G問題（間に合わず？）

問題文: G - Caeser Syllables

Difficulty: 2464

KCPCメンバー(rated参加) のAC率: 0/10

残り時間に絶対間に合わないので気楽に行きます。

問題が複雑です。こういうのを人類の脳に優しくするには、適当に二次元グリッドを描いて捉えるのがいいと思います。

これの各ブロックを上に一つずつ rotate させていき、rotate 回数ごとに 1 が連続する区間の個数を数えろという問題になります。これは階差\bmod 2 が 1 になる数をカウントすれば計算できます。競プロ頻出の言い換えです。

そうなると重要なのは (A_i,A_{i+1}) (0\le i\lt N-1) の頻度列です。

C_{a,b} = (A_i=a, A_{i+1}=b を満たす i の数)

として、 以下の画像のようなイメージになりました。

この半市松模様（もしくは値）を右下に rotate していき、「赤マスに書かれた数の総和」を各 rotate {O}(K) ぐらいで求めればいけます。

求まらないなと考えているうちにコンテスト終了。

────────

rotate 回数を先に固定することに拘りすぎていました。埒が明かなくなってきたので、視点を変えてA_i,A_{i+1} 間の高低差を固定して寄与を求めることを考えました。つまり上に描かれたグリッドを斜めに分解するということです。rotate されるのは右下方向なので、高低差ごとに独立に考えることができます。

高低差 d が固定されているものとして C_{i,(i+d)\bmod K} を単に C_i と書くことにすると、

ここから rotate 回数ごとの赤マスの総和を {O}(K) ぐらいで一度に抽出しようと思うと簡単でした。「添字」と「いくつ rotate したら加算されるか」の関係が足し算になっているので、この挙動はまさに畳み込みです。解けたと思いました。

しかし不安なのは計算量です。K\le 2300 で {O}(K^{2}\log K) が確実に間に合うかと言われると……わかりません。（この時はそう思っていましたが、今考えると実行時間制限 5 秒だしまあ想定だと思うべきです。ABC469E の時といい最近定数倍にビビりすぎな気がします）

コンテスト終了から 20 分経過。とりあえず実装してみます。

────────

入力部分の実装に 30 分かかりました……。

こんなに時間がかかった原因はオーバーフローです。ありとあらゆる場所がオーバーフローしていました。本番中じゃなくて良かった。

実は C++ なら uint32_t、uint64_t がそれぞれ modint 2^32 と modint 2^64 になっている（除算以外）ので、楽に書けます。そしてその事実を山田は知っていましたが、不安なので __int128_t などを使って書きました。それが裏目に出ました。しかもオーバーフローを解決した後、流石に不格好すぎると思って結局 uint32_t と uint64_t を使った実装に書き換えました。

（何故このような特殊な入力形式になっているか、ここを読んでる層は知ってる方が多いと思いますが一応説明すると、入力は（特殊な高速化をしない限りは）定数倍が重いからです。数列の長さ N\le 7\times 10^{6} という大きい制約下で、入力テンプレートなどで差がつかないよう配慮されています。稀によく見る形式です）

メインの実装も手間取りました。状況の複雑度が高く混乱します。畳み込みを使いそうなのは分かっていますが、どっちを reverse するかそれともしないかみたいな細かい判断でも混乱したので、頭を使うのをやめてサンプルに合わせに行く方向でガチャガチャと合わせました。

172:36 AC。実行時間は 660ms / 5000ms で余裕でした。想定も {O}(N+K^{2}\log K) でした。

72分36秒オーバーで全完。入力復元の実装で馬鹿なことしてなければ F との所要時間の差があまりないです。

コンテスト結果

順位の推移

C 問題までで炎上しているものの最終的なパフォーマンスへの寄与は小さいです。

コンテスト成績証

ABCDEF の六完 (77:08 + ペナルティ 10 分)。黄色にギリギリ戻れました。（が、翌日の ARC227 でやらかして -46 の刑に処され、またしても黄色から大きく遠ざかりました。Help）

画面録画↓

https://youtu.be/jF258aFS0gI