kichi2004's BLOG

競技プログラミングの参加記とか日常とか。(※Google Analyticsを使用しています)

競プロ

JOI 2020 / 2021 二次予選 参加記

投稿日:2020年12月14日 更新日:

はじめに

おひさしぶりです.kichi2004 です.
競プロ関係の記事は今年の 3 月以来 9 か月ぶりなので,まずはそれについて簡単にお話します.
今年の 2 月に,JOI に二次予選落ちしたことや Rating が停滞していることによって,競技プログラミングに対する「楽しさ」が見えなくなり,モチベーションを失ってしまったため,競技プログラミングから離れました.しかし,やめたらやめたで競技プログラミングがやりたくなって,3 か月がたった 5 月に復帰しました.
その後も 8 月頃までは水色で停滞が続いていましたが,その後調子を伸ばして青色になり,現在では 1 級 (青の上半分) のレーティングになっています.
また,PCK(パソコン甲子園)プログラミング部門にも出場し,予選を突破することができました.

準備

一次予選は前年度 B ランクのため免除ですが,1 回目と 3 回目に参加しました.
1 か月前あたりから本格的に JOI に向けた準備をはじめ,難易度 7 を半分くらい埋めました.実力的には通る可能性が十分高いということは理解していましたが,前年度のトラウマ等もあって,「どうせ落ちるんだろうな」とずっと思っていました.

予選当日

競技前

当日は脳の体力を維持しておくことや,直前に得た知識で混乱しないようにするため,精進はしていません.

競技中

13:00 (競技開始)

まずは A 問題を見ます.これは今いる地点の左右の '#' の座標をリストに持っておけばいいということがすぐに分かり,実装して提出します.バグらせて RE と WA をもらいますが,原因はすぐに分かり,AC を得ます.(ここまで 17 分)

13:17~

\(2 \leq N \leq 13\) を見て,ひっくり返すところを bit 全探索するのかな,と思いましたが,Q 回のクエリを処理しなければならないので,間に合わない.また,実験をして,そもそも bit 全探索では解けないことに気づき,ふりだしに戻ります.
どこかで見たことがある問題だなと思って検索すると,順列に対しての同じようなソートについての記事はいくつかあったものの,今回のような問題では使えなさそうでした.
いろいろと考えてもわからないので,とりあえず操作を BFS で全探索する愚直解を提出し,64 点を得ました.(ここまで 67 分,164点)
昨年は 3 完が前提で,その上での勝負になっていたことから,この時点で「落ちたな」という気持ちになっていました.

14:08~

B とは違い,こっちは読んだだけで大体の方針は浮かびました.誤読していた部分等もありましたが,比較的すぐに解くことができました.(87分,264点)

14:27~

続いて D を見ます.パッと見た感じは DP っぽかったど,少なくとも前から計算はできないでしょということで捨てました.
満点解法が思い浮かばないので,部分点を回収する方針に切り換え.
\(K = 1\) の場合は自明,\(K = 2\) の場合も軽い考察で比較的簡単に求めることができ,18 点を得ました.(104 分,282 点)

14:44~

次に E を見ます.こういうパズルみたいなやつは嫌いなんだよねと思いながら,小課題 1 は bit 全探索で解けるな,ということで実装し,7 点を得ます.(140 分,289 点)
そのあとも 25 分ほど小課題 2・3 を考察していましたが,解けそうになかったのでこれも捨てました.

15:43~

ここからは B や D の満点解法を考えますが.まったく浮かばず.競技終了.「今年もだめだったな」という気持ちでした.

16:00~ (競技終了後)

まず,準備していた得点表を公開し,書き込んでもらいました.すると,想定していたよりも多くの人が B や C で苦戦していたことが分かりました.書き込んでいただいた人数等を考えて,ボーダーが 200 点台の前半になりそうということが分かり,通った可能性が見えてきました.

おわりに

例年では木曜頃に結果が通知され,それまでは何とも言えませんが,80% くらいの確率で通っていそうなので,ほっとしています.しかし,新型コロナウイルスの影響で今年は本選がオンライン開催となっているため,嬉しさは激減しているというのも事実です.東京行きたかったなあ.

結果

12/18 (金) に結果が通知されました.無事に念願の予選 A ランクを取得し,本選に出場することができました.

-競プロ

執筆者:


comment

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA


関連記事

no image

「diverta 2019 Programming Contest」に参加しました

コンテストページはこちら 結果 4完 [A(100), B(200), C(400), D(500)] 47:04 ペナルティ: 1 (47:04 -> 52:04) ・順位: 446位 (Unrat …

no image

「AtCoder Grand Contest 033」に参加しました

コンテストページはこちら 結果 2完 [A(300), B(600)] 139:48 ペナルティ: 7 (139:48 -> 174:48) ・順位: 817位 (Rated) ・パフォーマンス: 1 …

no image

「AtCoder Beginner Contest 126」に参加しました

コンテストページはこちら 結果 5完 [A(100), B(200), C(300), D(400), E(500)] 57:43 ペナルティ: 0 ・順位: 662位 (Unrated) 各問題の解 …

no image

「AtCoder Beginner Contest 138」に参加しました

コンテストページはこちら 結果 5完 [A(100), B(200), C(300), D(400), E(500)] 20:16 ペナルティ: 0 ・順位: 84位 (Rated内39位) [ABC …

no image

「AtCoder Beginner Contest 127」に参加しました

コンテストページはこちら 結果 4完 [A(100), B(200), C(300), D(400)] 57:43 ペナルティ: 0 ・順位: 751位 (Rated) ・パフォーマンス: 1466 …