男もすなる競プロといふものを女もしてみむとてすなり（女ではない）。そもそも出場していないので「すなり」とか言ってるけど実際にはしてすらいない。
年明けに「今年はもう少し色々記事を書くぞ」とか言っときながら書類とセミナー発表とゲームと書類と書類のせいで全然記事を書いてない。しかもようやく書いたこれも技術記事ではない。日記だ。全然解けてないからな。
あんまり時間を縛られて解く系のことが好きではなかったのでこれまで競技プログラミングを敬遠していたのだが（作りたいものをじっくり考えてああでもないこうでもないと言いながら適当に休憩しつついろんなプロジェクトを並行してちびちびやるのが好きだ）、長期休暇だし、いつもはしないことをしてみようと思って調べてみた。参加するのでなく過去問の回答を提出するだけでも登録が必要らしい。そりゃそうだ。なんでサーバーを登録なしで使わせてあげないといかんのだ。というわけで登録した。
適当に一番最近のビギナー向けコンテストの過去問（ABC166）というのを、時間をラフに計りながら解いてみることにした。100分とのことだったがA問題を投稿した後に「あっ時間計らないと」と思ってタイマーをつけたので余裕を見て90分にした。ちなみに前提知識はなかった。twitterでみんなが解いていた時間帯はPS4でBloodborneをプレイしていた。試してないビルドがたくさんあるので定期的に遊びたくなる。
A, B, C問題は単にプログラムが書けるかということを聞かれているらしく、プログラムが書けるので書いた。特に感想はない。とかイキリつつもケアレスミスでBを2回WAしたのだが。入力インデックスが1始まりなことが頭から抜けててout_of_rangeを出した。その時ファイルをアップロードする機能があることに気づいた。AとBの途中まで提出ページに備え付けのエディタで書いて「vimキーバインドないの？」とか言ってた。自分でvim開け。
D, E, Fは解けていない。解けていないので感想が「これを試したが失敗」しかない。まあ反省ということで書いていこう。
D問題はパッと見て因数分解したもののいい感じの解答が思いつかず、タイトル的にもそっちは袋小路なのかなと思ったので別の解答を少し考えた。一瞬ニュートン法的な奴を使ってできないかと思ったが思っただけでそれ以上考えておらず、探索するとなるとどの程度の範囲を調べるかを決めるのがめんどいなと感じてしまったので他のを先やるかと思ってスルーした。そしてそのままになった。競プロの定石を理解していないので、値の範囲という情報をintのサイズを決めるためにしか使っていなかった。解説を見てから「あ〜なるほどね」って言ってた。めんどいなと思った瞬間にやめずにもう少し範囲について考えればよかったんだな。
E問題はデータ数的に二重ループだと時間足りないな、と思いつつとりあえず万一のために二重ループのコードを出してまずは初手TLEした。それを眺めながら、入力を読んでる間に身長の最大値を出しておいて後のループの時に身長の最大値で範囲を絞れば事実上O(N)か？ となってやってみたがTLEした。今からすれば、十分大きい値（データ量が2*105に対して値は109まで許される）が混ざっていれば実質的なスピードアップはないのでこのTLEは当然だと思う。書いてる瞬間はこれでいけると思ってたが。
その後、もしかしたら先頭に馬鹿でかい数があるがあとは小さい数しかない、という風な入力で弾かれているのか？ と考え（信じがたいことに、最後尾に馬鹿でかい値がある場合のことを考慮できていないことにこの段階では気づいていない）、その値以降の最大値を取ってくることを考えた。そこで「これが例のsegtreeってやつか？ twitterで見たんで暇つぶしに書いたことあるんですよ〜」ということでコードを掘り起こして提出したが、無事TLEした。この時点で方針に疑問を持つべきだったと思う。その後、毎回segtreeにquery出してるのが良くないんかな？ と思い、インデックスと値のペアを値が小さい順にソートしておき、最大値のインデックスがすでに現れたインデックスより小さい場合はpopすることにして、常に最後尾を見ればその後の最大値がわかるという風なコードを書いた。これも無事TLEした。このへんで「これで無理なら無理やろ〜」とか言いながらF問題を見にいった。結果的にEで大量に時間を溶かした。今からすれば、最後尾に馬鹿でかい数が入ってたらこの戦略は単なる最大値を覚えておく戦略と同じになるので、「1 1 1 ... 1 10^9」みたいなテストケース一つで全部簡単に弾けるジャッジ側に優しい回答だと思う。
これはあとで解説を見て「は〜〜？ 天才か？」って言ってた。見返すと自分のアプローチが猪突猛進すぎて恥ずかしくなってくるな。せっかく頭が首の上についてるんだからもうちょっと条件とかについて考えを巡らすといいと思います。
F問題はすでに時間が15分くらいしか残ってなかったので諦めムードで読んでいた。操作しないといけない数が両方0になったらアウトか〜というところまで理解し、全ての手の種類が定まってるんだから両方0にならないような操作を作るんだな、片方が0になってる時は選択肢がなくなるけど、両方非ゼロの時の選び方はその後の手全部関係してきそうで大変そうだな〜、これが噂のDPってやつか？ と思いしばらく考えていたが15分とかで書き終わる気がしなかったので普通にギブアップして解説を見にいった。解説では十分でかい時は適当でいいと書かれており、ほんまか？ となった。今も「適当に選ぶと破滅する手」を作れないか考えている。同じペアが2回以上連続する場合はそのペアでやりとりすれば現状維持ができるし、別々のペアになり続ける場合は総和は不変だから誰かが十分大きい値を持ってるのでそこから持ってきたら大丈夫になるのかな。厳密性のかけらもない考察やめてもらえますか。
こうして振り返るとまず、100分の割り振りがクソすぎる。Eの諦めが悪すぎた。これはアルファベット順に難易度が上がると聞いていたので、E解けないならF無理だろという気持ちがあったからと言い訳させてもらう。自分の回答を破壊できるケースがあることは少し冷静になれば思いつけたはずで（入力の範囲を計算量の見積もりにしか使わず、Aの範囲を見てなかったのが一因）、方針転換してしっかり分析していたらもしかすると解き方を思いついたかもしれない。逆にDとFは諦めが早すぎた。調べないといけない範囲がどの程度になるかとかの計算はできてよかったし、Fについては時間を余らせて挑んでおけばよかった。
それと、自分では意外だったのだが、競プロでは計算用紙を手元に置いといた方がいいということがわかった。そもそもそういう発想がなかったので周りに紙がなく、全部頭の中とコメントでやる羽目になり、非常に苦労した。大学では適当に積んである読み終わった論文の裏紙をひっ掴んで使うのだが、家にプリンタがないので家には論文の裏紙がない。久しぶりにノートでも買うか。
普段は何かのアプリケーションやライブラリとかを書いているので競プロ的な部分よりも全体の設計とかに頭をひねることが多く、かつそっちの方が好きでもあるのだが、こういうのもやってみると新鮮で楽しいことがわかった。提出してみると少しずつステータスが変わって正しく動いているかわかるところもちょっとゲーム性があり、ハマる人がいる理由もわかる気がした。飽きてくるまでたまにやってみようかな。
ちなみに昔twitterで知って調べて書いたというsegtreeの実装は以下のような感じです。テストはちょっとしかしてない。なんかAtCoderの環境ではC++17使えないっていう噂を当時聞いたので（今は使えるのかな？ 知らんけど）C++11の範囲内で書いてた。競プロ感なさすぎで草
#ifndef CMP_SEGMENT_TREE_HPP #define CMP_SEGMENT_TREE_HPP #include <functional> #include <algorithm> #include <initializer_list> #include <vector> #include <ostream> namespace cmp { template<typename T> struct plus { T operator()(const T& lhs, const T& rhs) const noexcept { return lhs + rhs; } static T identity_element() noexcept { return T(0); } }; template<typename T> struct maximum { T operator()(const T& lhs, const T& rhs) const noexcept { return std::max(lhs, rhs); } static T identity_element() noexcept { return std::numeric_limits<T>::lowest(); } }; template<typename T> struct minimum { T operator()(const T& lhs, const T& rhs) const noexcept { return std::min(lhs, rhs); } static T identity_element() noexcept { return std::numeric_limits<T>::max(); } }; template<typename T, typename Operator = plus<T>> class segment_tree { public: segment_tree() = default; ~segment_tree() = default; segment_tree(const segment_tree&) = default; segment_tree(segment_tree&&) = default; segment_tree& operator=(const segment_tree&) = default; segment_tree& operator=(segment_tree&&) = default; segment_tree(const std::vector<T>& init, const T fill = Operator::identity_element()) : segment_tree(init.begin(), init.end(), fill) {} segment_tree(std::initializer_list<T> init, const T fill = Operator::identity_element()) : segment_tree(init.begin(), init.end(), fill) {} template<typename InputIterator> segment_tree(InputIterator first, InputIterator last, const T fill = Operator::identity_element()) : values_(determine_size(std::distance(first, last)), fill) { this->initialize(first, last); } T query(std::size_t first, std::size_t last) const { assert(first < last); if(values_.size() < last) { throw std::out_of_range("segment tree does not have enough elems"); } first += this->num_inodes_; last += this->num_inodes_; T value = Operator::identity_element(); while(first < last) { if(first % 2 == 0) { value = this->op_(value, values_.at(first)); } if(last % 2 == 0) { value = this->op_(value, values_.at(last - 1)); } first /= 2; last = (last - 1) / 2; } return value; } void update(std::size_t index, const T& value) { index += this->num_inodes_; this->values_.at(index) = value; while(index != 0) { index = (index - 1) / 2; this->values_.at(index) = this->op_(this->values_.at(index * 2 + 1), this->values_.at(index * 2 + 2)); } return ; } void dump(std::ostream& os) const { std::size_t width = 1; while(width * 2 <= values_.size() + 1) { for(std::size_t i=width - 1; i<width*2 - 1; ++i) { os << values_.at(i) << ", "; } width *= 2; os << std::endl; } os << std::endl; return; } private: static std::size_t determine_size(const std::size_t input) { // when we have 100 elements, we will allocate 128 leaves. // 28 leaves are initialized with the identity element. // initializing all the levels becomes relatively easier // because we have exactly 2^N leaves. std::size_t len = 1; while(len < input) {len *= 2;} return len * 2 - 1; } template<typename InputIterator> void initialize(InputIterator first, InputIterator last) { const auto N = this->values_.size(); this->num_leaves_ = (N + 1) / 2; this->num_inodes_ = N - this->num_leaves_; std::copy(first, last, this->values_.begin() + this->num_inodes_); std::size_t width = this->num_leaves_ / 2; while(width != 0) { const std::size_t offset = width - 1; for(std::size_t i=offset; i<offset + width; ++i) { this->values_.at(i) = this->op_(this->values_.at(i * 2 + 1), this->values_.at(i * 2 + 2)); } width /= 2; } return; } private: Operator op_; std::size_t num_inodes_; std::size_t num_leaves_; std::vector<T> values_; }; } // cmp #endif// CMP_SEGMENT_TREE_HPP
