Atcoder初心者が成績アップに繋がったと感じた考え方の工夫
こんにちは。
id:shallow1729です！この記事ははてなエンジニア Advent Calendar 2020の7日目の記事です。
昨日は
id:stefafafanさんで「iTerm2の機能を使いこなして日頃の作業の効率をあげたい2020」でした！
iTerm2僕も使ってるはずなんですけど知らない機能がいっぱいでした。
はじめに
この記事は半年ほど前から参加していたAtcoderというプログラミングコンテストを振り返って、特に成績アップに繋がった問題を解く時の思考方法の工夫について書いたものです。まだ始めて4ヶ月ほどで十分に参加できていないのでまだ茶色ですが、ここ三回はパフォーマンスが一気に上がって、Atcoder Begineer Contest(以下ABC)の問題ならD問題までは安定して解けるようになってきましたし、E問題も方針はうまく選べるようになってきました。まだまだ初心者ですが、工夫が成長に繋がった事がすごく嬉しかったので試した事をいろいろ書いてみようと思います。なお、この記事ではABC181からABC184の問題のネタバレも入っているのでそういうのが嫌な人はブラウザバックしてもらえたらと思います。
アルゴリズムの勉強
メインの考え方の話の前にアルゴリズムの知識に関する話から入ります。プログラミングコンテストに参加するとなるとアルゴリズムの知識が結構いると思っていたのですが、少なくとも僕が参加していたABCのD問題ぐらいまでだと、自分の実装の計算量を見積もるなどの基本的なアルゴリズムの解析やメモ化を使った高速化はできる必要がありますが、名前のあるアルゴリズムの実装についての知識はそれほど多くは求められていないような印象です。計算量の見積もりが重要な理由は、コンテストの制限時間は結構短いので、明らかに間に合わなそうな実装の時はパフォーマンス改善を考えたり、逆に不必要にパフォーマンスチューニングをして実装コストを増やさないなどの判断を素早くできる必要があるからです。経験上はO()あたりがギリギリ間に合うか間に合わないかという感覚なのでそういうイメージで設計をすると良い気がします。ただ、もう少しテクニカルなアルゴリズムの知識についていうと、スタックやキュー、グラフの全探索あたりは頻繁に出てくるので実装に慣れておく必要があるかなと思います。あと、場合の数を求める問題などで出てくるでかい素数で割った余りを答えよみたいな奴対策でmod計算用のライブラリは事前に用意しておいたほうがいいと思います。modの計算というのはこちらで紹介されているようなやつです。
drken1215.hatenablog.com これだけは持っておかないと方針があってる回答でもTLEになってしまったりするので。。。
E問題になると整数問題で使うアルゴリズムや二分探索、Union-Find Treeなど、もう少しアルゴリズムの知識を必要とする問題も出てくる印象なので勉強はやっとくに越した事は無いと思います。ただ、知識があるのと実際に知識を使えるようになる事の間は結構あると感じているので、知識があれば問題が解けるかというとそうでは無いと思います。
数学的な問題解決の思考方法
今回メインで書きたかったのは数学の問題を解く時によくやるような試行錯誤のテクニックです。数学の勉強ってもちろん覚えないといけないことがたくさんありますけど、大事なのはそれをうまく使って問題を解くところというのは受験などを経験した人は分かるんじゃないかなと思います。そこの能力って才能として見られがちですが、案外訓練で改善できるものだと思っています。実際数学の問題解決の方法についてはいくつか本があって、有名な本だとG.Polyaの「いかにして問題をとくか」があると思います。今回はそういう試行錯誤の技術について、実際の問題を解いた時の思考の流れと一緒に説明できたらなと思います。
実験する
見慣れない問題や方針に困る問題を見たらとりあえず手を動かしてみましょう。いくつか試してみるとアイデアが思いつく事があると思います。
なんか難しそうな問題ですね。難しそうな問題はとりあえず手を動かしてみましょう。(0, 0)から(100, 0)だと(0, 0)->(50, 50)->(100, 0)で二手、(0, 0)から(101, 0)だと(0, 0)->(50, 50)->(100, 0)->(101, 0)で三手になりそうです。じゃあ(0, 0)から(105, 0)なら四手になるかというとそうはならなくて(0, 0)->(52, 52)->(104, 0)->(105, 0)で三手になってしまいます。こんな感じで実験をすると最大でも三手でクリアできると分かってくるんじゃないかなと思います。あとは一手か二手か三手かを判定する方法を考えるという形になります。(この場合分け難しかったんですよね。。。今後の反省点です。。。)
全ての都市間について移動ができるようなグラフの問題に見えます。グラフの問題として全探索を行っても解けるかなと思いますが、実際に経路を並べてみるともっと単純なパターンが見えてきます。4都市の場合は例にあるように
- 1->2->3->4->1
- 1->2->4->3->1
- 1->3->2->4->1
- 1->3->4->2->1
- 1->4->2->3->1
- 1->4->3->2->1
というパターンがあります。1を除くと2, 3, 4については単純に順列の全列挙になっている事がわかります。順列の全列挙はPythonだとitertoolsで用意されているのでそれを使ってしまえば良いという感じです。これを紹介した理由として、実験する時は元の問題の文章に引っ張られずにフラットに見ると良いよと伝えたかったからでした。もちろん問題文から得られるイメージは解決に役立つ事もありますが、変にバイアスになって重要な性質を見落としたりする事もあるので要注意です。
逆から考える
問題の道筋が見えない時はゴールから逆算するという戦略が有効です。
この問題は各人iについてから
までの間
リットル水を使おうとした時に使おうとする水の量がWを超える瞬間があるか？という事に答える問題です。NとTが 最大で
なので単純に時刻ごとに全件を足してると間に合わなさそうです。この問題に答えるために各時刻で使われる水の量の総和さえあれば良さそうです。ある時刻に使われる水の量の総和は「その一つ前の時刻に使われている水の量」+「その時刻に使い始める水の量」-「その時刻に使うのをやめる水の量」で求められます。つまり、この問題を解くためにはこれらの情報を準備すればいい事がわかります。「その時刻に使い始める水の量」は時刻
の関数として
で初期化の時に計算できる。「その時刻に使うのをやめる水の量」についても同様ですね。「一つ前の時刻に使われている水の量」は初期値0で時間発展の中で都度計算されるものなので特別な準備は不要です。このようにすると計算時間が間に合うようになります。大事なのは問題を解くのに必要なデータ構造を先に考えて、それをもらった入力から作れるか？と考えた点です。ゴールから考えた事で実装までの流れが見えやすくなりました。
簡略化した問題を考える
複雑な問題をそのまま解くのではなくて、それをもう少し簡単な問題にした時に解けるかを考えてそこから考えるという奴です。
atcoder.jp 例えばこの問題はN人の児童と身長の変わる一人の先生でペアの身長差が最小になるような組み合わせを作るという問題です。この問題だと「先生の身長が変わる」というのは明らかに問題を難しくしています。なので、いったん先生の身長は変わらないと仮定して自由度の少し減った問題を考えます。そうすると小学校でよくやるように背の順で並んでペアを組むという戦略が多分思いつきやすくなると思います。N人の児童を背の順にソートして隣同士をペアにすればいいという基本方針が思いついた段階で、先生の身長が変わるという条件を持ってきます。この問題は先生の身長のパターンを全て試した中でペアの身長差が最小の答えを求めればいいとわかりますね。この問題を解くために考える必要がある事は二つで、一つは先生の身長が決まった場合にペアを決めるという事、もう一つはペアが決まった時に合計をどのように求めたらいいかという問題があります。前者についてはソートされた配列の中での自分の場所を決める問題なので二分探索が使えそうです。後者のペアが決まった時に合計をどのように求めたらいいかについてですが、児童のペアの作り方は先生とペアになるか、前の人とペアになるか、後ろの人とペアになるかになります。例えばもともと前の児童とペアになっていた児童の間に先生が割り込んできた場合、その児童は後ろの児童とペアを組むことになります。同様にそこから後ろの児童は全員ペアが前の人から後ろの人に変わります。なので、ペアの身長差の総和は先生より前のペアについての総和と先生と児童のペアの身長差と先生と児童のペアから後ろのペアの身長差の総和の三つで計算できるようになります。先生と児童のペア以外は事前に前のペアと組む場合と後ろのペアと組む場合について累積和を作っておけば定数時間で総和を計算できますね。難しい問題に見えますがステップを分割して一つ一つの段階をよく考えればきっと解けるんじゃないかなと思います。
最後に
というわけで今回は僕が成績アップに繋がったと感じたプログラミングコンテストの問題を解くための考え方の工夫をまとめてみました。一番伝えたかったのは数学の問題を解くイメージでプログラミングの問題を解くと筋道を立てやすいよというところです。プログラミングと数学の関連はよく強調される一方で個人的にはなかなか実感を持てなかったのですが、今回試行錯誤をする中でなんとなく分かってきたような気がします。とはいえ僕もまだまだ解けない問題多いので、もっと試行錯誤して今後もプログラミングコンテスト楽しめたらなと思います。
明日は
id:kouki_danさんです！よろしくお願いします！！
