hogecoder

tsutaj 競技プログラミングの記録

ARC-E を全部解いたので 10 問選んでみた

この記事は Competitive Programming (1) Advent Calendar 2018 の 17 日目の記事として書かれました。本来なら日本で執筆する予定だったんですが、飛行機運が悪すぎて機内でスマホを使って記事を書いています。限界すぎる。

先日、2018 年 12 月 17 日現在で公開されている ARC-E を全て埋めたので、個人的にオススメの問題を 10 問ピックアップして紹介していきたいと思います。自分の好みが原因でジャンルが偏ってるんですが、まあお許しください・・・。

以下ネタバレを含むので、注意です

絶対に落としたくない問題

以下で紹介する問題は、たしかに難しいけれどもコンテスト中に絶対に落としたくないと感じる問題です。(主観ですが) 他でもよく出てくるような考察を必要とします。

Snuke Line (ARC068, 700 点)

この問題は、条件を少し言い換えるだけでかなり見通しが良くなります。ただし言い換えた後も工夫しないと想定解法の計算量にはたどり着かないでしょう。これは自力で思いつきたい問題です。

N! / K 番目の単語 (ARC047, 旧 ARC-C)

よくある問題設定ですね。ここで使う考察は他の問題でもよく出てくるので、是非一度トライすると良いと思います。

キャンディーと N 人の子供 (ARC059, 800 点)

おそらく 800 点の中では簡単な方だと思います。少し高速化しないと AC は取れませんが、他に比べればそれほど難しくはありません。

Meaningful Mean (ARC075, 600 点)

これもよくある設定の問題です。わかってしまえばかなり素直に解くことができますが、自力でこのアプローチを思いつくのは難しいかもしれません。上位勢を目指すなら絶対に外せない枠になるでしょう。

考察重視の問題

以下で紹介する問題はいわゆるアドホック系で、考察寄りの問題です。筆者はこういう系統が一番苦手なのですが、数をこなして考察力をつけるしかないのでしょうかね・・・?

Papple sort (ARC088, 800 点)

問題設定自体は非常にシンプルです。解法も分かればかなりシンプルなものですが、考察力がないと導くのは難しいと思います。普段から考察がちゃんとできているかで明暗が分かれそうな問題です。

Ball Coloring (ARC073, 700 点)

個人的にかなり苦労した問題です。考慮すべき状態の数がそこそこ多いので、その全てを考えきれるかが大きなポイントです。このようにいくつかの場合に切り分けるような問題は解くのに時間がかかりますが、地道にやっていくしかありませんね・・・。

GraphXY (ARC089, 900 点)

グラフの構築問題です。構築系はアドホックな考察が必要とされることが多いと感じていて、これもその一つです。まずは解説を見ずに、じっくり考えてみることをお勧めします。

高度典型を養う問題

以下で紹介する問題は、「このテクニックは自分が知る限りだとこの問題でしか練習できないし難しいけど、大事だよな〜」と思った、いわゆる高度典型の問題です。ARC-E にはたまにこういう問題も混じっているので面白いです。ただ、解くまでに無限時間かかるんですけどね・・・。

Smuggling Marbles (ARC086, 1000 点)

部分点解法は操作に関する簡単な特徴をつかむことで比較的楽に解くことができます。ただし、満点解法はそうはいきません。詳しくはご自身で解説を読んでいただきたいのですが、なんと部分点解法のアイデアを変えずに高速化することで解くことができます。ここで使うテクニックは自分の知る限りではこの問題でしか見たことがないのですが、上位勢からすると典型とのことなので、類題はいくつかあると思われます。たぶん。

NarrowRectangles (ARC070, 1000 点)

この問題は、自分が ARC-E を埋める際に最後の砦的存在になっていた問題で、解くまでに相当時間がかかりました。

問題設定は非常にシンプルで、慣れていれば部分点解法も容易に思いつきますが、満点解法は関数の性質をうまく利用しなければならず、思いついたり実装したりするのは至難の業です。いつかこのような問題を本番中に解きたいものですね。

MUL (ARC085, 700 点)

言わずと知れた有名高度典型です。この問題をきっかけに、某テクニックを知った方も多いのではないでしょうか?最近でいうと CODE THANKS FESTIVAL G 問題で、これに似た考察で解けるものが出題されました。

というわけで、ARC-E から 10 問ピックアップしてみました。当然この 10 問だけ取り組んでも不十分で、やはり全部解くと良いと思います (害悪)

ここまで読んでくださりありがとうございました。来年の今頃には ARC-F が全部埋まってればいいんですが、できているかなあ。