見出し画像
Photo by takaren

初中級者が解くべき過去問精選 100 問を全問解いてみました

Kenta Nakajima

e869120さんの初中級者が解くべき過去問精選 100 問をC言語で全問解いてみました。全問解ければ、「水色コーダーどころか青色コーダーくらいの実力が付く」らしい。レポジトリは https://github.com/knknkn1162/blue_e869120_100 です。レポジトリ内には難易度(1~5まで。自分調べ)と解答へのリンクがあります。可能な限りわかりやすいコードと必要に応じてコメントを記述するようにしています。
良かったらGitHubにてスターを押してもらえると励みになります。

流石に100問解説する記事を書くのは大変なので、この記事では全問解いた感想をつらつらと書き綴たいと思います(需要がありそうなら、難しそうな問題に対しては解説記事を書くつもりでいます)。

解く順番は?

大体順番に解いていくのが良いと思いますが、
強いて言うなら、累積和(及び、いもす法)を利用する問題が累積和の項目(76~80)より前にあったりするので、累積和を早めに片付けることをおすすめします。全探索の後に解くのが良いと思います。
また、最小全域木問題はクラスカル法を用いて解くのですが、Union Find木というデータ構造を知っていないといけないので、Union-Find(85~87)まで先取りすると良いです。
動的計画法：bit DP(49~52)が難しければ、全探索：ビット全探索(10~14)を先に解くことをおすすめします。
幅優先探索の問題30~32はやや大変なので、飛ばして時間の余裕のあるときに取り組むのが良いかもしれません。

また、単元ごとに必ずしも簡単な問題から並んでいるわけではないので、出来なかったからと言って気落ちする必要はないです(これについては、GitHubの上記のレポジトリに難易度を記載しています)。
例えば、
・"全探索：工夫して通り数を減らす全列挙"の8問目 Square869120Contest #6 B - AtCoder Markets
・二分探索法の21問目 AtCoder Beginner Contest 023 D - 射撃王
・深さ優先探索の26問目 AtCoder Beginner Contest 138 D - Ki
・動的計画法の40問目 JOI 2012 予選 4 - パスタ
はそれぞれ、単元の途中の問題ですが、比較的難しいと感じました。

高校生なら一通りできそうな難易度

プログラミングと高校数学が苦手と感じない高校生なら(文系、理系問わず)大体の問題は解けるのではないか、と思いました。

大体は中学数学レベル以下で解けるはずですが、DP(動的計画法)は漸化式を組むので、高校数学の数列の事前知識があったほうが良いかもしれません(とは言っても、数列の概念とシグマの和の公式(一次と二次)だけ。漸化式を解く公式などの知識は一切不要です)。逆元を求める問題は高校から逸脱してはいるのですが、e869120さんの初中級者が解くべき過去問精選 100 問の記事に紹介されているリンクをたどれば、かなり詳しい解説記事があるので、しっかり読めば理解できると思います。

普通の高校生が水色~青色になって、大学生になったらそのスキルを生かしてバイト/インターンすれば、おおよそ余裕を持った生活が出来ますね。。いい時代になったもんだ。

配列が0-indexedか1-indexedかを意識する

初中級者にとっては意外と大事なのではないかと思いました。 0-indexed, 1-indexedというのは配列の番号を0で始めるか、1で始めるかくらいの意味で使っています。文法的にはC言語の配列は0から始まるのですが、array[0]を無視して意図的にarray[1]から始める場合に1-indexedとして扱う、と呼ぶことにします。配列を0-indexedで扱うべきか、1-indexedで扱うべきかの適切な判断は、紛らわしい場合はコメントに書いてしまって、バグを回避するほうが無難です。

配列を0-indexedで扱うべきか、1-indexedで扱うべきかは問題や選択するアルゴリズムによって変わってきます。普通の場合は0-indexedで良いのです。自分は、ある問題で番号1スタートになっていたら、特に問題なければ0-indexedに変更して配列に詰めたりします(その後は全て0-indexedとして考えればよい)。そもそも大体のプログラミング言語において配列は0-indexedとして使用するものであり、必要でない場面で1-indexedを使うと、forループの始点終点の書き間違えをしたりややこしいです。

が、問題によっては、1-indexedにしたほうが都合が良い場合がいくつかあります。

例えば、33問目 AtCoder Beginner Contest 088 D - Grid Repaintingは二次元地図が入力として与えられるのですが、配列を1-indexedにすることで境界条件の煩瑣な分岐を避けることが出来ます。また、DP(動的計画法)や累積和で用意する配列はindex: 0での値を初期値として用いるため、1-indexedで考えることが多いです。最小ヒープを自力で実装する場合は、用意する配列のindexは1から始めるほうが便利です。

一方、1-indexedにすることで、配列の個数の最大値に気をつける必要がります。例えば、問題のサイズが100000だった場合、もし1-indexedの配列を用意する場合は、静的配列の個数を100000ではなく100001にする必要があります。また、前述のようにループの始点終点にも留意します。

問題を解く際は、少しでもこんがらがると思ったら1-indexedか0-indexedかコメントに記述するのをおすすめします。1-indexedから0-indexedに変換した場合なども同様です。そうすることで自分は悩ましい(わかってしまえばくだらない)バグがかなり減り、実装が快適になりました。

添字の変数を意味のあるものにする

特にDP(動的計画法)の実装をする際に強く思ったのですが、少しでもこんがらがると思ったら、iやjなどの変数を使うより、cityやday、cur(current: 現在の(状態))や`prev(previous: 前の(状態))など、意味のある変数を使うほうがバグりにくくわかりやすいコードを書けるな、と思いました。

例えば、42番 JOI 2015 予選 4 - シルクロードはループを以下のようにして書くと、問題を読まずとも何をしようとしているのかがある程度わかることでしょう：

   int day, city;
   for(day = 1; day <= dlimit; day++) {
       // 0-indexed
       for(city = 0; city <= cs; city++) {
         dp[day][city] = dp[day-1][city-1] + ..  // do something
       }
   }

もちろん、自分で完全に把握できそう or 一重ループなど明らかな場合であれば、i, j, kでも問題ないと思いますが、自分のプログラミング力を過信しすぎないのも実力のうちということで。

C言語で解くことで、ライブラリに頼らず自力での実装が出来、力がついた

これは賛否両論あるかとは思いますが、個人的にはC++は高々100~200行のコードを記述するには複雑すぎると思うので、C言語を選びました。ライブラリが乏しいというのは、コンテストで早く解くという観点からはデメリットなのですが、教育用で解くという観点からはメリットになりえます。C言語にはまともなライブラリがqsort()とsqrt()くらいしかないので、連結リストやハッシュ、lower bound(二分検索の仲間)なども自力で実装する必要があります。自分で言うのもなんですが、ごまかしの効かないアルゴリズム力がついたのではないか、と思っています。

ただ、デメリットもあって、permutationやダイクストラ法(最小ヒープ有り)の実装はC言語ではなかなかつらいです。atcoderなどのプログラミングコンテストだと、予めライブラリ化しておくのも一つの手かな、とは思います。

やや重い実装の問題が10~15%くらいある

Note) ここで「やや重い実装の問題」というのは、アルゴリズムの難易度とは無関係にコードが100行~くらいの実装になってしまう問題のことを指します。

有名なAtCoder に登録したら次にやること、という記事と比べると、それなりに重い実装の問題があるように感じます。
例えば、幅優先探索の32問目 E - イルミネーション (Illumination), 33問目 Problem B: 迷図と命ず はそれなりに重いです(実装問題は思ったよりも重くはなかったです)。78問目 JOI 2011 本選 1 - 惑星探査 はプログラミングそのものに慣れていないと、同じようなコードを3回書く羽目になります。
ただ、これらの問題含め、過去問精選 100 問では該当の問題で「少し実装が重い」と書かれてあるので、その問題を回避できますし、回避して後で解くのも良いと思います。

参考にした本

・プログラミングコンテスト攻略のためのアルゴリズムとデータ構造(通称 らせん本) .. 初中級者が解くべき過去問精選 100 問 を見る前にやっていましたが、特にグラフアルゴリズムの実装の際に参考になりました。
この本はAizu Online Judgeを中心とした基本問題とその解説が記述されており、プログラミングコンテストチャレンジブック (通称、蟻本) の導入にも良いです。
Note) 今回初中級者が解くべき過去問精選 100 問を解くにあたって、プログラミングコンテストチャレンジブックの知識は不要と感じました。つまり、100問の後に取り組んでも問題ないということです。

おわりに

他にも個々のトピックについて語りたい部分はあるものの(二分探索の実装や拡張ユークリッド法の実装の考え方、C言語のポインタの勘所、難しかった問題の解説などなど)、また次の機会としたいと思います。
最後まで読んでくださりましてありがとうございましたm(_ _)m

いいなと思ったら応援しよう！