これはアドベントカレンダー2020 6日目の記事です。
昨日の記事はこちら : ICTSC予選「ダイエットしようぜ！」で極限ダイエットする (1) 【AdC2020 5日目】
はじめに
こんにちは、20B の tatyam です。 AtCoder橙 をしています。
11/6 に tatyam + baton + mikit = good_yamikin で ICPC 国内予選に参加しました。
チーム決め
20B の黄・青コーダーはもうチームを組んでいて、私はだれと組むのかな〜〜 って言ってた
らいつの間にか橙橙黄のチームが出来てた。 traP ありがとう！！
模擬国内
baton さんが休みで、 mikit さんと 2 人で出ました。
AB を tatyam、 C を mikit が解きます。 (なんで mikit さん C からやってるんだっけ)
AB はすぐに通せて、 D が難しいです。しばらく考えると D が解けて、 E を読むと 2-SAT です。
ここからが素晴らしい動きでした。
ちょうど C を AC した mikit さんが戻ってきて、 2-SAT を持っていなかったので E を任せます。
F はサイコロ実装問です。実装の方針を立てて、実装したくないので G を読みます。
G は幾何です。しかも全然糸口が掴めないので H を読みます。
すると、 10 分くらいで解法が分かります。びっくり。
mikit さんが E 、 tatyam が H を通します。
G を mikit さんに任せて、 F を実装します。
1 つのミスをデバッグするのにかなり時間がかかってしまいましたが、 1 時間くらいで通します。
G は幾何の罠にかかってしまい AC できませんでした。
結果
H の FA のおかげで 2 人で 2 位を取ることができました。てんさい？
国内予選
さあ， yokohama に向かって競技開始だ！とあなたは意気込んでいるところかもしれないが，ちょっと待ってほしい．問題文が見れない．
たすけて〜〜 とか言っていたら 10 分後に唐突に始まってびっくりした。
競技開始
A を tatyam , B を baton , C を mikit が読みます。
A 問題はやるだけなので書くと、 AC します。
2 人の様子を確認して D を読みます。 構文解析です。構文解析は習得しておいたので問題ないのですが、そのあとが分かりません。
baton さんが B を通し、 C は難しいのか baton さんと相談をしています。
D が分からないので EF を読んだりしていると、 C を mikit さんが通しています。
D を baton さんに任せ、 F が解けそうなので F を考え、 mikit さんが E を考えます。
F はなかなか難しくて、しばらく考えて の TLE 解法ができることに気がつきます。
37 GB のメモリを確保できることを確認して、 を書きます。 入力ファイル 1 つの実行に 10 分かかりました。
D は JOI::舞踏会 を使えば解けるらしいです。 舞踏会 20 ヶ月前に解いてるなあ…
F を実行している間に E を考えます。解けない〜〜
しばらく考えると、選ぶ場所が隣り合わないから状態数が減っていることに気がつきます。
遷移の計算量が分かりませんが、とりあえず書きます。
G は mikit さんが個数を求める DP が分かったようです。これをがんばって辞書順最小にします。
F の実行は全く進みません。どうやら最悪ケースに 20 分以上かかるようです。
F は高速化を試みたもののまだ遅く、 G も間に合わないまま 3 時間が終了しました。
結果
5 完最速で 5 位でした。
反省としては
- F が TLE 解法でしか解けていない
→ 結局 FA だしこっちの方が早かったのでヨシ！ - E は解けるべきだった
- これ解いたら Poyashi にも勝てたはず
という感じでしょうか。 yokohama では Poyashi に勝てるようにがんばります。
おわり
明日の担当者は @d_etteiu8383 さんです。楽しみ〜
