| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ||||
| 結果 | AC | AC |
全体感想
beginnerコンテストよりも、難しめな回にしっかり結果を出していきたいのですが、空回り。
CとEをずっと考えていた。どちらも最終的にはほとんど分かって、コンテスト中でもどちらかだけに時間をかければ十分解けたと思う。
分かっても短時間で正しく実装しきってやっと正解になる競技。考察も実装もバグ取りも、ハマるとあっという間に1時間消し飛ぶので、短時間で確実に結果を残すのが難しいです。
問題A – Kenken Race
はじめ$A<B<C<D$だと思って（2人が追い越す場合がないとして）解いた。
beginnerのA問題のイメージで読んだからかもしれないｗ
それに追い越せるかどうかの判定を足して提出。
無理やり判定を追加したので、雑すぎて一度TLEになった^^;
問題B – ABC
問題C – Tests
残り40分くらいで、計算量が落とせた。「部分的に埋める科目」が1つ以下としてよく、科目選択も満点性能か部分点性能の優れたものに限られる。フルに埋める科目数も、計算できる。
そこから部分的に埋める科目をどれにするとどうなるのか、地味に場合分けがうざくて、残り時間25分でバグなく書ける自信がない。諦めてEに移動した（たぶん判断ミスだけど、結果は同じだったかも）
実際には、部分的に埋める科目については、理論的にそれほど絞らなくても、$N$個とも試せばよかった。どうせ$N\log N$の事前計算はするし、ひとつひとつの判定は$O(\log N)$なので、判定回数を節約することには計算量オーダーの改善の意味がない。そこを頑張って場合分けが増えてしまうようなら、計算量オーダーの増えない範囲で無駄に探索する代わりに実装難易度を下げると良かったのか。
問題E – Complete Compress
集める目標地点を決め打って、そこからの距離を調べようというのは自然なアイデア。
再帰的に解けば、各分岐ごとの深さの和としてどのような値がありうるかが計算できることが分かる。よって、作れるかの判定をする問題は解けた。ここまででコンテスト残り20分。
実装は比較的簡単なので、何とか間に合うかもしれない。残り10分。コードテストにかける段階で、操作の最小回数も出力することを忘れていたと気づく。
これも同じように再帰的にやれば良いと思ったが、残り時間で修正が利かない。終了。
解説PDFを見ると、ほぼ正しい方針に乗れていて、最小回数についてはもう少し簡略化がきくようだった。
