ABC322 振り返り
はじめに
参加から少し時間が経ってしまったけど、記念すべき？競技プログラミング初参加の記録として記事にする。
動機
これまでのキャリアを振り返ってみると、業務で一般的なCSのアルゴリズムが求められる機会があまりなかったせいか、基本的なアルゴリズムに対する理解が不足しているんだろうなーという自覚はあった。
正直言って、現在の仕事も特にそういった知識が求められる場面は少ないが、将来の転職の面接でコーティングテストがあった時に最低限のアルゴリズムや計算量の理解は必要になりそうだし、今まで眼の前で頓挫してしまったパフォーマンス改善系のタスクも、実はこの辺りの知見があれば解決できていた可能性もあるな、と感じ[1]、急遽ABC322の当日か前日にアカウントの作成と提出などのやり方を調べて参加した。
A - First ABC 2
普段余り文字列処理系の実装を行う機会がないが、朧気に「std::stringである文字列に対して、指定文字列が現れる位置を返すAPIがあったなぁ」程度の記憶があったので、試験中に調べた。
結果、こちらのstd::basic_string::findが見つかったので、こいつを使って終わり。
B - Prefix and Suffix
問題見たときに、2問続けて文字列操作系の問題かいと思ったのは内緒
接頭辞はstd::basic_string::substrで先頭からN文字取ってきて比較で終わり。
接尾辞についても、同様にstd::basic_string::substrで末尾からN文字取ってきて比較で終わり。
あとは、上記の結果を使って、接頭辞である/ない、接尾辞である/ないの組み合わせの計4パターンのどれに該当するかチェックする形で解けた。
C - Festival
個人的に今回の鬼門だった。
なぜかというと、手元で普通に全探索で実装しテストケースが普通に通ったので、提出してみると、TLE×5が表示され、そこから深い沼にはまってしまったからだ。
TLEを見た時に、「実はstd::coutやstd::endlは遅い」みたいな事を誰かがどこかで言っていたのを思い出したので、記憶とGoogle先生を頼りに、出力をprintfに変えてみたり、入力をscanfに変えてみたり、std::vectorの宣言時に要素数を指定してみたりと、それっぽい事を色々やってみたが、結局それらではTLEは解消できなかった。
そして上記の様な試行錯誤で7回提出 & TLEしてからようやく、「これは小手先ではなく、解法のアルゴリズムやロジックそのものに問題があるのでは？」と思考を切り替える事ができた。
→ここに至るまでC問題の最初の提出から30分経過していたが[2]。
自分の実装を見直したところ、「ループ毎に各日付から、それ以降のインデックスを探索して、何日後に花火が上がるかを求めていたけど、花火の翌日のみそれを計算→次の花火までは1日ごとに求めた結果-1日していけば、探索しなくてもわかるんじゃない？」という疑問が湧いてきたので、それを実装 & 提出したところ無事ACになった[3]。
ちなみに、やっとの思い出ACまで漕ぎ着けたのがコンテスト終了の9分前だった。
流石に残りの問題が9分以内に解ける訳はないだろうな、という事は分かっていたので、残りの問題の問題文を眺めたりしているうちにコンテスト終了となった。
まとめ
結果としては初参加でギリギリ3完する事ができた。ただ、この回のレベルがどれくらいだったのかが分からないので、この成績をどう受け止めて良いのか分からないのが事実。
一回参加してみただけだけど、継続に取り組めば知識の引き出しは増えていきそうだなと感じられたし、何より単純に面白かった。特にC問題をあーでもない、こーでもない、という試行錯誤の末にコンテスト終了9分前にギリギリACできた時は流石に脳汁が出た。
どこまでいけるかは分からないけど、まずは茶色を目標にこれからも継続的にコンテストに参加できると良いなーと思っている。
Discussion