今年もやってきました、春季トレーニング(通称:春合宿)。日記形式で毎日書こうと思います。(ので、ブログをこの五日間鍵にしていました)

Day 0 (3/20)

表彰式でした。chokudaiさんがマイクを軸に左右に体を動かすという話を聞いてからスピーチを聴いていると、実際そうだなと話し方に目が行ってしまった....

交流会は楽しみました。交流してくれた人ありがとう。

practiceはまあVM配布されたからVM上で練習してきたので大丈夫。ただ、家のPCより重く感じた(ノーパソなので当然スペック悪め)。過去2回解ききれなかったpracticeで初全完。まあ今年はonline practicecもあって問題は知っていたのでね。

今年のテンプレート

モリモリにしました。cerrのデバッグがめんどいので関数を作った。いつも使う感じのやつらを全部入れた。正直ちょっと多い

#include <bits/stdc++.h>
#define overload4(a, b, c, d, ...) d
#define rep1(n) for (ll _ = 0; _ < (ll)(n); ++_)
#define rep2(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep3(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (ll i = (ll)(b) - 1; i >= (ll)(a); --i)
#define rrep(...) overload4(__VA_ARGS__, rrep2, rrep1)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define eb emplace_back
#define pb push_back
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vi = vector<int>;
using ull = unsigned long long;
using vvl = vector<vl>;
using ld = long double;
using pl = pair<ll, ll>;
using vp = vector<pl>;
template <typename T, typename U>
inline constexpr bool chmax(T& a, const U& b) { return (a < b ? a = b, true : false); }
template <typename T, typename U>
inline constexpr bool chmin(T& a, const U& b) { return (a > b ? a = b, true : false); }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto it = v.begin(); it != v.end(); ++it) {
        if (it != v.begin()) os << ' ';
        os << *it;
    }
    return os;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (auto& e : v) is >> e;
    return is;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << p.first << ' ' << p.second;
    return os;
}
template <typename T, typename U>
istream& operator>>(istream& is, pair<T, U>& p) {
    is >> p.first >> p.second;
    return is;
}
template <typename T>
void print(const T& v) { cout << v << '\n'; }
template <typename Head, typename... Tail>
void print(const Head& head, const Tail&... tail) {
    cout << head << ' ';
    print(tail...);
}
template <typename T>
void dbg(const T& v) {
#ifndef EVAL
    cerr << v << endl;
#endif
}
template <typename Head, typename... Tail>
void dbg(const Head& head, const Tail&... tail) {
#ifndef EVAL
    cerr << head << ' ';
    dbg(tail...);
#endif
}
static constexpr ll inf = numeric_limits<ll>::max() / 2;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

無思考で書けるってレベルのデータ構造等は以下の通り

Segment Tree
Lazy Segment Tree
Binary Indexed Tree
Heavy Light Decomposition
DSU(Union Find)
Bitwise and,or convolution
ダブリング LCA

まあ書けそう

O(N)空間LCA
64分木 Set
Sparse Table
Wavelet Matrix
永続配列
Undo可能Union Find
SCC
Rolling Hash

ギリギリ

CHT
Static Top Tree
Dinic(フロー)

これを書いていて今年はいよいよ最後なのかと思うとしみじみとした気持ちになります。

おおまかな戦略

昨年の反省を生かしてルーティーンみたいなものを作って冷静でいられるようにしました。

最初の10分は環境設定とテンプレートやらスクリプトやらだけに使う。実際にそのくらいかかる。終わってから問題が入っている封筒を開く。
最初に解く問題はBatchの中で制約/小課題の設定や問題の分量から総合的に判断して一番簡単そうな問題を選んで解く
どうせ時間はあるのだから、分かった小課題はすぐ実装する(多少は次の小課題を考えたりはするが、わからなそうだったらすぐ撤退する)
20~30分くらい進捗がなくなったら次の問題を開封する
Communicationは2問目として見る。自明な部分点がよく配置されているから。
トイレは気分の切り替えのために行くのを惜しまない
2時間30分時点ではすべての問題を開封する。

(以降、問題のネタバレがあります。)

Day 1 (3/21)

おはようございます。良い睡眠ではなかったけど十分な睡眠は取れました。頑張ろう行きで吉祥寺でhiikunZと遭遇してそこからNTT駒場まで一緒に行った

競技(覚えてる範囲で書く)

A

まず読んで、嘘貪欲が生えてそれを実装して小課題1が通らないな～を30分くらいして、他の小課題を見たら小課題4でTLEしてることに気付く。

制約を見ると、Aに含まれるiの個数も大事であることに気付いて、1,2,3,....と追加していったときにiで被覆できるかできないかという問題になることに気付いて、ちょっと考えると区間スケジューリング問題に帰着できる。2年前も区間スケジューリング問題がそういえばあったな。テキトーに $O(NM^ 2 \log M)$ を書いて19点。嘘貪欲の方も二次元セグ木を使うと高速化できるが、とりあえず後回しにしようと思う(45分くらい)

B

コミュニケーションは意外と正の得点は得られるから見た。問題読んで確認がてら3点を取る。得点計算を見るとなんか点数のつけ方キモくない？となる。

ちょっと考えると2文字ごとに00と11だった場合に送れば450を基準に差分が取れることがわかる。これで16点。どう考えても優位になる点数を取るのにL=40とかを達成しないといけなくて、ちょっと考えるけど無理そうと思い撤退した。(75分くらい)

A

9点の小課題2や19点ある小課題3も解きたいと思って考えるけどどうやっても $O(NM^{2} \log M)$ かかるが？とか言ってた　100分も経ってたのでさすがにCを見ることにする

C

グリッドで一瞬嫌な気持ちになるが、問題を読むと意外に素直な設定で、50点まではストレートにいける。50点を取って、ちょっと考えてみるとダブリングが降ってきて、クエリで並列二分探索すればうまく行くことに気付く 100点の実装は40分くらいかかった。180分くらい

A

ここらへんでUcupにdynamicな区間スケジューリング問題があったことを思い出す。これ

ただ、upsolveしてなくてlink cut treeであることしか覚えてなかったので何も役には立たなかった。

とりあえずBはやりたくないしわかってる二次元セグ木解(小課題4)を書く $O(M \log^{2} M)$ とかでTLの余裕はそんななかった。実装に時間かかった上、うんうん考えてたら残り30分くらいで空間/時間 $O(MN \log M)$ の解が思いついて実装してみるが、MLEした。ギリギリまで粘るも伸びず

31-16-100 計147 で 2位でした。上が173で下が143と団子の先頭みたいな感じで順位にしては余裕がない立ち位置。つらい。

Day 2 (3/22)

おはようございます。快眠。頑張るぞ～

競技

今日は提出画面の写真を撮ってきたので、色々書ける

A

自明な指数として $O(4^{N})$ がある。次に $O(NT^{3})$ の多項式があるが、多項式はできれば N に偏らせたい気持ちになる。

別の指数として $O(N2^{N})$ が小課題にあったので、とりあえず $O(NT^{3})$ だけ実装する。

うんうん考えていると、対角線上の二つの救急車は患者を取るか取らないかは X+Y (あるいは X-Y) について単調なので、片方の対角線で取る患者を決め打って取れるだけ取るを実装すると $O(N2^{N})$ になり、無事35点。

Y座標が全部同じやつは今度は単純に Y軸に平行な組の救急車同士で考えると部分和問題もどきになる。それを通して 50点。ここで60分経って、$N \leq 45$ を通したいので、考えるが無理なので70分時点で撤退。

C

またCommunicationだけど、自分のプログラムがやり取りする系ではなく、木系なので高得点は狙えるかもと思う。

とりあえず直線とスターグラフが自明だったからテキトーな二分探索をする20点 (100分)

とりあえず木でうまくやれば 2N になるので、それも実装してさらに15点 (120分)

さらに5点は取れそうだったが実装がめんどうだったので、先の小課題を考えていた。わからずAに戻る(135分)

A

有意な進捗はほぼないが、ななめ二つを固定したいみたいな考えはこのときあった。結局諦めてBをとりあえず見ることにする(145分)

B

問題を読むと、実は単純な設定であることに気付く。(二回目のiの出現,一回目のjの出現)となっているような組のswapで高々1種しか増えず、結局01列の転倒数が本質。愚直で確認しようと思い、実装すると45点入る(160分)

転倒数の前計算部分でBITをテキトーに使えばまず自明な改善ができて、66点になる。(170分)

クエリ計算の部分ではLi Chao Treeが必要とか一瞬思うが、実はx座標だと思っていたものが傾きで、傾きが定数なのでテキトーにやればいいことが判明する。問題文のXって変数やっかいすぎ！テキトーに実装して無事100点 (180分)

一気に30分くらいで100点取れてさすがにほっとする

A

さっきのななめ二つ固定を考えるが4次元セグ木とかになり、明らかにおかしい。結局よくわからず一旦わかっているめんどいCの部分点に行くことにする

C

2Nだったのを $N+4\log_{2} N$ とかに改善する。最後の二分探索を結構さぼったので怖かったけど無事通る +5点 (計40点) 200分

A,C

70分くらいずっと行き来して考えてたが全然わからん。Cはどうせ重心分解/HLD系統なのでさすがに通せる見込みはなさそうと判断して途中からはAに比重を重くして考えていた。

A

終了十分前にトイレに言っていたら天からAの81点(最後の小課題以外)の解法が降ってきて、4つに区切って4つとも部分和もどきをするとうまく行くことがわかる。熱烈実装をするが、間に合うはずもなく....

競技終了後にForestedさんにAの思いついていた解法を話したらそこから満点はすぐだよと言われた。昼飯中は頭が働かなかったのでよくわからなかったが、解説聞いたらもう10分くらい考えたら思いつくようなシンプルな改善だった。もうちょっと早く思いついていたら....と思うがまあ仕方がない。 hirayuuがA,Bの満点を開始150分でしたらしく、圧倒された。

今日はA,Cを考えている時は特にイライラしてしまい、マスコットに当たっていました。他にも振り回していた気がする。

自分のマスコットである猫のぬいぐるみをほぼクッション扱いしてる(潰す、殴る、叩く等)ので、競技後にチューターに動物虐待を注意されてしまった！
— 松阪 (@mt_saka) 2025年3月22日

day2 は 50-100-40 計190 で単体2位、二日間総合2位です。トップが入れ替わったが、相変わらず激しい代表争い集団の先頭になんとかいるって感じで苦しい。昨日からしおむすびと4点差だし。逆にトップとの差は開いて、結構しんどい。明日も頑張るぞ！

Day 3 (3/23)

5:45に一回起きたけど二度寝に成功。おはようございます。やるぞ～

朝、会場でOutput-Onlyは出ないだろ～（笑）とかしおむすびとほざいてた(フラグ)

競技

最初の十分の環境構築をしていると、唐突に競技システム上にアナウンスがあるので確認してくださいというアナウンスがありテンプレートの実装中だったが見てしまい、なんと今日Output-Onlyがあることが判明した。とんでもない。助けてくれ

B

一番素直そうな見た目していたので考えることにする。11点は簡単なDPなので実装して一回TLEするがpragmaとかテキトーにつけて通る(24分)

$ N \leq 5000$ を考えていたが、テキトーに考えた貪欲はなにもうまくいかずうんともすんともいかない。

小課題が多いので後の方を見ると文字種が少なくなる部分問題の小課題がある。これは簡単な貪欲が回るので実装してさらに8点を得る (52分)

Z=0も考えるがわからんのでもう一つのBatchであるAに行くことにする

A

とりあえず愚直なシミュレーションが $O(QN \log {L} \log {N})$ になるので、書いてワンチャン59点ないかな～とか思いながら24点をとりあえず取る。(69分)

35点は取れたらデカいので色々定数倍高速化を試みる priority_queueやsetを使うような解法しか思い浮かばず、色々苦戦して気づいたらほぼ1時間経ってたので仕方なく重い腰を上げてOutput-Onlyを見ることにする。ついでに、乱数とかの書き方を頭の中で思い出させる。

C

問題文がとにかく長い！読解を頑張るととりあえずN=4は手で解をすぐ書けることに気付く。とりあえずL=3で9点(127分)

提出する時にL=2になったので1分後に出して16点になる(128分)

N=32を考えると、とりあえずbitごとの情報をまとめて～とかしたくなり、考えると $\frac{N}{2}+ log_{2} {N} -1 $ が思いつくので実装する。5bitなのを忘れててペナを積んだが無事通る(139分)

急にBinary Indexed Treeの気持ちになり、頑張るとL=9が達成できそうなことがわかるので、実装する。バグらせたりしたが一発で73点になる。うれしい。(160分)

よくよく考えると、BITの子の方が無駄なクエリを投げているので、そこで情報をできる限り得ようとするとL=8が達成できるのでうまく実装する。ちょっと遠回りして時間かかったが無事通る。76点(174分)

最後にN=48を考えるが、N=32でやっていたのと同じ感じで、BITみたく和を計算していくパートをやってそのあとにN=32のときから一手だけ多くかければまたN=32の時の状態に戻ることが分かったのでコードの定数とその1手を書き加えて無事満点！(181分)

A

35点が取れる可能性が割とあって、取れたらデカいので粘着することにする。とにかく色々な $O(QN \log {L} \log {N})$ 解法を考えて、全部実装するという気持ちでやる。紆余曲折し、bitsetで高速化が効く解法が思いついて、実装すると35点の小課題を正解できた！最高！ (270分)

この35点がとにかくしんどかった。

B

テキトーな貪欲を書いては捨てるを30分くらい繰り返して終わった。まあ今日の最難かな？とは競技中感じていた。

結果的に 59-19-100 で計178点 Day3単体2位で全体1位になりました。hirayuuがOutput-Onlyで大きくコケていたので、1位になってしまった。5位との差は69点で4位との差は67点。明日は何もやることが無くなるまで粘着を絶対にしないことを肝に銘じて取り組まねば....

Day 4 (3/24)

いい睡眠をとって無事起きました。おはようございます。やったるぞ

競技

今日は色々あってあまり覚えてないですが、なんとなくの動きは覚えてる。

C

初手で読むと15点はとりあえずわかるので通す(30分くらい)

なんとなく小さい方から右から取って行く貪欲が思いついたのでそれも実装してみると30点(54分)

この貪欲をいい感じにやるとどうやら満点解になるようだがどう考えても高速化できないだろ！とか言ってわからなかったのでCommunicationのAに行くことにする。

A

初手で $N \leq 1000$ は自明なので通す(10点)

次に直線と二分木をそれぞれ考えるとそれぞれいい感じの二分探索が回るので通せて、これで50点になる。$(R \leq 70)$ しか取れていないが、どう考えてもこれより早くならなくてこまったな～をずっとしていた。

ただ、これらの実装でかなりバグらせて焦っていた。

+27点の解法はHLDしてheavy-pathを頂点とするとうまくいくことはわかっていたが、競技開始120分経っていたのでBを見ることにした。

B

読んだ感じマージテクとかを頑張る実家な感じがする。頑張って落とそうとするがなかなか二乗とかから落とせなくてこのあたりでかなり苦しくて、代表落ちを覚悟し始めた。

わからないのでとりあえず自明部分点を回収すると12点が得られる。

$T_i=2$ がない場合をとりあえず考えることにしてしばらく考えていたが、なんかそれらしき解法が思い浮かんだので実装してみるとなんかTLEする解法しか生えてないしで流石に焦り始める。色々実装してなんとか $T_i=3$ が5個以下の小課題は取れた。

C

この頃(210分くらい)からどの問題も満点は諦めて取れる部分点を取り切ることにしようと思い始めた。他の人がそれなりに失敗している可能性を信じ、自分がなんとかこの三日間で得た貯金を消費しきるギリギリまで部分点が取れればそれでいいんだという気持ちです。

とりあえず $A_i \leq 2$ の場合を一旦考えていい感じに関数合成で表せそうなことに気付き、実装するがWAが返ってくる実際ランダムテストを回してみると落ちることがわかる。流石にどうしようもない気持ちになり途方に暮れていた。(解説を聞いた感じ実際に関数合成みたいになってセグ木に乗るらしいが、競技中生やしていた関数合成は明らかに嘘であった)

B

時間が無くなり残り 15分とかになって、なぜか自明なの実装していなかった $D \leq 20$ を実装するが焦りもあり合わない。シグナル11(メモリ制限違反の可能性があります)のREで落ちているらしいが、メモリは全然使っていなくて本当に焦った。結局通らず終わってしまった。この13点で代表落ちしたら実装しなかった自分を一生恨むだろうな～とか思った。

点数は50-27-30 で107点でDay 4 単体は8位だった。

競技終了後は代表落ちたと思い絶望していました。競技会場を出て最初に点数を聴いたのがしおむすび,hirayuu,hiikunZで、自分がかなりの点差で彼らに負けていたため彼らがこの点数なら4,5,6位の点数もかなり良いだろうと思えて更なる絶望を味わいました。

結果的には、4,5,6位が失敗していて差が広がらずに済んだため3位フィニッシュでした。147-190-178-107 の合計622点でした。