競技プログラミング なぜ問題が解けないのか?

何故問題が解けないのか

競技プログラミングを2020年4月に始めて、2か月半くらい経ちました。

pythonで競技プログラミングはじめました。atcoderでレーティング灰色です。まずは目指せ茶色です。PASTは初級でした。単純にコー...

ほぼ毎週末行われる、Atcoder Beginner’s Contest (ABC)のほか、週1回職場のソフトウェア部隊のバーチャルコンテストに混ぜてもらったりしながら精進しています。

競技プログラミングの経験や本格的なコーディングの経験があるわけでもない私にとってはまだまだ思うように問題を解けないことも多いです。今後どのように精進していくか、については方針を考えることが大事です。そのためには「現状なぜ問題が解けないのか」をクリアに見つめなおす必要があると考えました。一般的に当てはまると思われるケースを以下に列挙します。

問題がわからない

文章読解

いちばん基本的な部分です。問題文の文章読解ができないケースです。読んでもよくわからないのでサンプルケースを見るが、それでもよくわからず自分でノートに手計算してみてようやく理解できる、といったことがあります。時間がかかるのでもったいない。「AI VS 教科書が読めない子供たち」という本がベストセラーになりました。あれも文章読解能力が足りないことを嘆く内容でしたが、文章読解はいかなる分野、場面でも基本となる能力であることを思い知らされます。

なお昨年RST(Reading Skill Test)を受験した結果はかなり好成績だったんだけど。。。

誤読

文章読解と関連しますが、上記は読んでも「わからない」という状態なのに対し、読んで「わかった」つもりになって読み間違えている、というパターンです。「理解していない」ことを理解できていないケースなのでハマると厄介なパターンです。サンプルケースを通そうとして大概は気づくと思われますが、時間のロスは痛いです。

数式の読解

数式で問題文が記述されるとビビるパターン。いちおう理系だしエンジニアなのだが。苦手意識は否めないです。

解法がわからない

典型アルゴリズムを知らない

競プロにおいては典型的なアルゴリズムや解法が複数存在します。全探索、貪欲法、動的計画法etc…。知らない状態から問題を解くためにそれらのアルゴリズムを一から考案するのは至難です。類題を解いたり、アルゴリズムの勉強をするなど、ある程度アルゴリズムや解法の知識を持っておく必要があります。

どのアルゴリズムを適用するかわからない

典型アルゴリズムや解法を知っていたとしても、目の前の初見の問題に対してどの解法を適用するべきか、思いつくことができなければ問題は解けません。ある程度過去問を解いていくことで問題の発する“におい”からわかるようになる、気がします。

考察が足りない

問題の本質を見極めて解く能力。有名な蟻の例題で言えば、蟻が正面衝突して向きを変える、ということとそのまますれ違う、ということが等価であることを推察する能力。計算量を落としたり、典型アルゴリズムで解ける形式に翻訳したりする能力。センスが良い人はこの能力が高いと思います。筋の良い解法を思いつける人は憧れます。

数学がわからない

時に数学的な考察が必要な時もあります。整数や素数、偶数、奇数の性質などは頻出する印象があります。それ以上に難しいものも多々あると思うけどまだ出会っていないだけかも。

実装できない

解法を意図通りの動作で実装できない

筋の良い解放を思いついたとして、それをどのようにプログラムに実装させるか、という時点でつまづく、あるいは時間がかかりすぎてしまうパターン。言語仕様の理解不足、知識不足ということですね。私はコーディングの能力がまだまだ低すぎなので課題です。

バグらせてしまう

何とか実装したとしてバグらせてしまうケース。正答が出ない、あるいはランタイムエラー(RE)。サンプルケースでバグるのはまだデバッグが簡単なので良いのだが、本番のコードテストでサンプルケースが特定できない状態でWAが出るパターンは厄介です。コーナーケースの見落としが無いか、テストケースを自分で考えながらデバッグする能力が必要。

職場ではコーディングはしないが、ソフトウェアのテスター、デバッガーとしてソフトウェア開発には関わるので、その中でソフトがどんなバグりかたをするのか見てきているのでその経験は役に立っていると思います。

メタ的なもの

体力・体調管理

メタ的な要素の筆頭は、何にもましてまずは体力、体調管理。何でもそうだが体が資本なのは竸プロも一緒。自分の場合、コンテストのある日に限ってアレルギー性鼻炎が激悪化するので勘弁してほしいです。。。

メンタル

メンタルも体力に負けず劣らず重要です。謙虚な心と自信のバランス。競技中に失敗した時に崩れずに挽回するリカバリー力。諦めずに最後まで取り組む姿勢。最近業務中ではここまで時間的なプレッシャーをかけられて何かをするという経験が無いので新鮮。

競技時間確保

わざわざ挙げるか微妙な線だが、体力、メンタルと並んで、ちゃんと競技のための時間を確保する、スケジューリングの能力はもちろん大事です。どれだけ竸プロに重きを置くか、という優先順位の問題でもあります。PASTの場合は5時間の試験時間を確保できなかったため、変な遅い時間から始めたため、試験時間2時間を残して気力・体力の限界を迎えギブアップすることになったので。

自分の現状分析

私自信の場合、現状は圧倒的な基本知識不足が課題としてあげられると思う。これはアルゴリズム及びコーディングの能力、言語仕様の双方に当てはまる。まずアルゴリズムの存在を知らず、おまけに実装するための構文やライブラリの知識も無い。それをググろうとした時点で若干萎えてしまう。

ただし、ここはそれなりに時間をかけて学習していくことで身に付けられる部分でもある。過去問を解くさいは、知識不足で100年考えても解けない問題があることを念頭に、解けない時にあまり時間をかけすぎずに回答をみて勉強していくことが大事かと思っている。

続いて2義的なもので、アルゴリズムを適用する能力、考察能力、バグ、コーナーケースへの対処、などがあるが、これらは場数を増やすことで成長を期待する方針である。Atcoder problemsで過去問をとく、コンテストに参加する、と言った実践をこなすしか無いだろう。職場で行われているバーチャルコンテストでは終了後、上級者からレクチャーを受ける機会があるので、これも大変参考になる。

競技を続けていく上で、ネックになるのは数学への対処かもしれない。今のところ、それ以前の問題が大きくて顕在化していないが、どこかで数学と向き合う日がくるのだろうか。数学能力がネックとなるほど成長できればそれ自体大した進歩ではあると思う。

モチベーションはどのように維持するか

竸プロのレーティングに一喜一憂するのは楽しいが、あまり他人と比べすぎない方が良いのかもしれない。上には上がいるものである。私から見れば雲の上のような高レートの方でも他者との比較の中で劣等感に苛まれていたりするので。純粋に問題を解くことを楽しんでいるのが幸せな付き合い方では無いか。

スポンサーリンク
スポンサーリンク




スポンサーリンク




シェアする

  • このエントリーをはてなブックマークに追加

フォローする

スポンサーリンク
スポンサーリンク