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

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

この記事をシェア

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

関連する記事

2021年3月19日
traPグラフィック班の活動紹介
NABE icon NABE
2021年4月18日
ベズー係数とN項の拡張ユークリッドの互除法
0214sh7 icon 0214sh7
2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase icon Silviase
2021年4月26日
CPCTF2021 作問者writeup by hukuda222
hukuda222 icon hukuda222
2021年4月25日
CPCTF2021 作問者writeup by xxpoxx
xxpoxx icon xxpoxx
2020年12月4日
【一緒に始めよう】VSTプラグインをつくる【AdC2020 21日目】
liquid1224 icon liquid1224
記事一覧 タグ一覧 Google アナリティクスについて