feature image

2020年11月19日 | ブログ記事

ICPC国内予選2020参加記【AdC6日目】

これはアドベントカレンダー2020 6日目の記事です。
昨日の記事はこちら : ICTSC予選「ダイエットしようぜ!」で極限ダイエットする (1) 【AdC2020 5日目】

はじめに

こんにちは、20B の tatyam です。 AtCoder をしています。

11/6 に tatyam + baton + mikit = good_yamikin で ICPC 国内予選に参加しました。

チーム決め

20B の黄・青コーダーはもうチームを組んでいて、私はだれと組むのかな〜〜 って言ってた

----------2020-11-18-9.22.18

らいつの間にか橙橙黄のチームが出来てた。ありがとう 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 できませんでした。

結果

----------2020-11-18-10.49.49

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 時間が終了しました。

結果

----------2020-11-18-9.01.23-1

5 完最速で 5 位でした。

反省としては

という感じでしょうか。 yokohama では Poyashi に勝てるようにがんばります。

おわり

明日の担当者は @d_etteiu8383 さんです。楽しみ〜

tatyam icon
この記事を書いた人
tatyam

競技プログラミングと素数大富豪と音ゲーをしています。

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase icon Silviase
2019年3月16日
競技プログラミングを始めよう【新歓ブログリレー2019 8日目】
eiya icon eiya
2018年12月16日
ICPCアジア地区横浜大会参加記【アドベントカレンダー2018 52日目】
eiya icon eiya
2018年12月3日
ハル研究所プログラミングコンテスト 2018に参加しました[アドベントカレンダー2018 40日目]
ninja icon ninja
2020年11月27日
GORMを使い始めたら…【AdC2020 14日目】
mazrean icon mazrean
2020年11月26日
インターネットを作ってみよう【AdC2020 13日目】
temma icon temma
記事一覧 タグ一覧 Google アナリティクスについて