リンク
総括
コンテスト前夜にばちゃを3回くらい走って、めげない心の速筋を鍛えたことが功を奏したのかな...と思う。
例えば、C問題に似合わぬデータ構造でごり押ししたり、D問題で解法が合っていると確信することで実装のバグを(自分にしては)早く直せたりで、とても良かった。
一番今までと違ったことは、考察用ノートのページ上に「気を付けるメモ」的なものを書きなぐったところ。事実、それのおかげでもあって、堂々巡りに訳分からん時間を費やさなくて済んだ。
↓例のメモ 字が汚すぎる！
ただ、今回は他の競プロerがルール変更によるデバフを受けていたperfを伸ばす最大のチャンスだったので、それを逃してしまったのがとても惜しい...
A問題
文字列を数値に変換して、後で比較っていうのをやった。
この方針は悪くないけど、比較のために、当時は配列でうにゃうにゃしてて時間がかかった(3分)ってしまった。ラムダ関数とか使ったら、変数宣言するまでもなくパッとかけるから、ACできたとはいえ、余裕で失敗宣言...
後の問題をみても、共通処理を括りだすのがまあまあ苦手っぽい。多分、小問ずつ解いていくってじゃない考え方をしてるのかも。
B問題
これは感謝が実った問題。
全テストケース試してなかったら、入力値が固定長じゃないって気づけなかった。
C問題
めちゃくちゃ難しかった。
どうやら、priority_queueとvectorで数と変動管理が想定解らしいけど、当時そんな$O(Q+N)$解法が見つからなかった僕は、代わりにセグ木で殴りました。
しかも、ただ区間和を取るだけじゃなくて、一点の値も必要だったから、その管理もしなきゃいけなかったのが二重苦だった。
もうすでに挫折しそうだったけど、勝手にライバル視してる方が11分の時点で既に解かれてたので、嘘解法だと諦めずに書きとおした。
セグ木の実装例(C++)
template<typename T, typename F>
class SegmentTree {
private:
int n;
vector<T> v;
F op;
T ide;
T query_sub(int a, int b, int k, int l, int r) {
if (r<=a || b<=l) return ide;
else if(a<=l && r<=b) return v[k];
int m = l+(r-l)/2;
return op(
query_sub(a, b, k*2, l, m),
query_sub(a, b, k*2+1, m, r)
);
}
public:
SegmentTree(int len, T identity, F monoid) :op(monoid), ide(identity) {
n=1;
while(n<len) n *=2;
v.assign(2*n, identity);
}
void set(int i, T val) {
i += n;
v[i] = val;
while(i > 1) {
i = i/2;
v[i] = op(v[i*2], v[i*2+1]);
}
}
T query(int a, int b) {
if(a>b) swap(a, b);
return query_sub(a, b+1, 1, 0, n);
}
};
D問題
みた瞬間貪欲だとわかった。「区間が残ってるときはどう管理すればいいんや...」ってなってたけど、式に落としたら、配列以外にひとつ変数をもって管理すれば、値の引継ぎのみで済むという発想に至る。
これで、挟み撃ちsliding windowで解けた。
統一させたい値を$k$としたときに、変換コストを$k$を$2$にするべきところが、逆にしてて、そのデバッグに死ぬほど時間がかかった...
E問題
みた瞬間三分探索だと分かった。変数が多くなるのは想定してたため、打ち間違えないように、神経削ってキーボードカタカタしてた。結果、なぜか$WA$続き...
もちろん三分探索自体は名前と用途を聞いたことあるだけで、実装はqiitaの記事のをほぼ丸コピしたようなものだった。残り9分で余裕がなくなってた僕は、具体的な原理を理解する余裕を残しておらず、「二次関数になるんやったら、最悪極値が二つになりうるなあ」と、謎の場合分けを展開するしかなかった。
実際は、片方を固定化した時に、動きに法則性が生まれるらしく、いつものパターンなので、「考察典型ちゃんとABC前につくっとけば良かった..」とバリ後悔。もう少し実装が早かったら、仮に典型用意してなくても、自力でたどり着けたかも..?
F問題以降
みれてません。
おわりに
点数配分的に5完狙える回だったので、こんな形で終わってかなり悔しいです。
自分が使ってるツール (nomouse-cli)の改修や、バイトの時間をコンテスト手前から平日に移動など、かなり環境管理に気を配っているので、来週が実力の収束点かも...と少しこわかったりします :(
ただ、まだ完全に諦めたわけではありません。僕が志望している企業さんの申し込み期限が一週間以内であり、それまでに入緑するために$1350$perf出さなきゃいけないわけですが、まだまだ精進のための時間は切り詰められると思ってて、それが正しかったってことを来週の自分に主張できるようにしたいところです。