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

競技プログラミングと音ゲーをしています。 AtCoder銀冠 ICPC 2020/21 Yokohama 3 位, WF 15 位 (good_yamikin) ICPC 2021/22 Yokohama 3 位 (tonosama) ICPC 2022/23 Yokohama 1 位 (tonosama)

この記事をシェア

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

関連する記事

2022年4月7日
traPグラフィック班の活動紹介
annin icon annin
2021年8月12日
CPCTFを支えたWebshell
mazrean icon mazrean
2021年5月19日
CPCTF2021を実現させたスコアサーバー
xxpoxx icon xxpoxx
2021年3月19日
traPグラフィック班の活動紹介
NABE icon NABE
2023年9月26日
traP コンペ 2023 夏 sponsored by ピクシブ株式会社 運営後記
abap34 icon abap34
2023年7月13日
アルゴリズム班はやとき王選手権「競(けい)プロ」を開催しました!
abap34 icon abap34
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記