BETA

初心者日記(16)『ノートに書く』

投稿日:2020-07-12
最終更新:2020-07-12

ABC127 C問題のPrisonを解くときに初めてノートに書く試みをしました。
AtCoderの解説を見てると何かしらの公式等を導き出していることが多いので、ノートに書けばその公式もないよりかは自力で導き出せるかなと。
今回の問題も馬鹿正直に全探索しようと考えたけど流石にTLEになるのを経験から理解しているので、何とか簡単に導ける方法を考えた。

N枚のカードがM個のゲートを全部通れるか一つずつ調べる。これだと全探索になるので、M個のゲートを一つずつ調べるのを条件に当てはまったら全部通れる探索にすればかなり探索量が減るのではないかなと。実際に入力例をノートに書いて整理した。

すんごい見やすい。Mのゲートを通る条件『max(L) <= i <= min(R)』がすぐに分かってすぐAC。
こういう問題って数学に似ていて、そういえば数学のテスト受けるときも計算用紙を一緒に配られていた。無理に頭の中で解こうとするから解けないわけで、複雑な問題ならノートを使って熟考すればいいんだなと思った。

余談

最近のABC問題ってAとBはちゃんと初心者でも解きやすいように難易度が灰(0~)になっていて、Cだと灰から茶(400~)、たまに緑(800~)、Dを超えると茶緑、さらに上の水色(1200~)や青(1600~)が多くなっている。
Virtual Contestsでみんなが灰~青の問題を入れたり、水と青メインで構成する理由はこれなんだなぁと。自分がABCを全部解けるようになるにはこの色を解けるようにならないといけないんだなぁと。

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

tnodino(つのでぃの)のブログ。日頃の内容を記事にしています。

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう