コンピューティングオリンピックで 3 つの金メダルのうち 4 つを獲得した方法

私は Google HashCode World Championship Finals 2017 の準備をしていました。これは、Google が主催するアルゴリズム問題を扱う最大のコンテストです。

私は XNUMX 年生のときに C++ をゼロから学び始めました。 私はプログラミング、アルゴリズム、データ構造について何も知りませんでした。 ある時点で、最初のコード行を書きました。 XNUMX か月後、プログラミング コンテストが目前に迫ってきました。 自分のプログラミング学習スタイルがどれだけ効果があるのか​​を知りたかったのです。 それは絶好の機会でした。

XNUMX日間の競技の後、結果が出ました。私は金メダルを獲得しました。

私はショックを受けました。 私は 5 年の経験を持つ競合他社よりも先を行っていました。 一生懸命努力してきたことは分かっていましたが、この成果は私の期待をすべて上回りました。 スポーツ プログラミングが自分のテーマであることに気づき、真っ向からそれに取り組みました。

私は何が私を成功に導いたのかを知っているので、それを皆さんと共有したいと思います。

この記事は EDISON Software のサポートを受けて翻訳されました。 プログラマーの健康と朝食の世話をしますと カスタムソフトウェアを開発します.

どのプログラミング言語を選択するか

• C++ - 強くお勧めします! 彼はとても速いです。 STL によりアルゴリズムの実装にはほとんど時間がかかりません。 C++ はすべてのコンテストで受け入れられます。 最初のコード行は C++ で書きました。
• C - STL のために C++ を学びます。 C の知識がある場合は、C++ でプログラミングすることもできます。
• Java は遅いプログラミング言語です。 Big Integer クラスがありますが、あまり役に立ちません。 競技に制限時間がある場合でも、Java を使えば必ず制限時間を超えることができます。 Java はすべてのコンテストで受け入れられるわけではありません。

どこで練習できますか

私はお勧め スフィアオンラインジャッジ（SPOJ）。 量・質ともに有効な資源です。 問題を解決する過程で行き詰まった場合は、エディターとソリューションをオンラインで利用できます。 このサイト以外にもお勧めします SPOJ ツールキット и SPOJ.pl の問題分類子.

まずは基礎知識を磨く必要がある

言語の構文に慣れると、克服すべき問題がいくつかあります。 練習が必要な簡単な問題から始めてください。 この段階で重要なのは、プログラミング スタイルを決定することです。 空白を多く含むコードを書くのが好きな人もいるかもしれませんし、そうでない人もいるかもしれません。 括弧を「if」と同じ行に置くことも、別の行に置くこともできます。

それはあなたのスタイルなので、自分のプログラミング スタイルを見つける必要があります。

それを探すときは、次の XNUMX つの基本原則を思い出してください。

• コードは実装が簡単である必要があります。 思いついたソリューションを安心して実装できるはずです。 なぜ？ なぜなら、競技中にコードに夢中になることは絶対に避けたいからです。 コードの実装を簡略化する方法を考えるために追加の 5 分を費やしたほうが、コードを理解するのに 10 分を費やすよりも常に優れています。
• コードは読みやすくなければなりません。 コードが読みやすいと、デバッグも簡単です。 正直に言って、バグは常に発生します。 残り 10 分なのに間違いが見つからないときのこの気持ち、わかりますか? もちろんそうでしょう。 この状況を回避するには、読みやすいコードを作成してください。 デバッグを開始すると、コードは自然で理解しやすいものになるでしょう。

これは私の例です プログラミングスタイル。

開発スキルを向上させる方法

練習、練習、そしてもっと練習。 最初の 250 個の最も解決可能な問題に取り組むことをお勧めします。 スポジ。 順番に解決してください。 それぞれの解決策について少なくとも XNUMX 時間かけて考えてください。

「この問題は私には難しすぎるので、次の問題を解いてみます」とは言わないでください。 敗者の考え方はこうだ。

紙と鉛筆を用意してください。 考えてみてください。 解決策が見つかるかもしれないし、見つからないかもしれない。 少なくとも、アルゴリズム的思考を養うことになります。 XNUMX 時間以内に解決策が思いつかない場合は、フォーラムまたは記事で既製の解決策を探してください。

このアプローチで何を達成できますか? コードを使用してアイデアをすばやく実装する方法を学びます。 そして古典的な問題とアルゴリズムを勉強してください。

次に、アルゴリズムとデータ構造をマスターする必要があります。

階層的なアプローチに従います。 歩き方を知らずにランニングを始めましたか？ いいえ。 しっかりした基礎がなければ超高層ビルを建てることはできますか？ 二度とない。

学習パスに沿ったステップを無視することはできません。 それらを無視すると、知識のギャップが残ることになります。 時間が経つにつれて、それらは悪化するだけです。

基本的なアルゴリズムとデータ構造から始める

始めるのは難しいです。 おそらく、最初に何を勉強すればよいかわからないからです。 それが理由です ビデオコース「アルゴリズムとデータ構造」を作成しました。 このコースを作成するとき、私はどのように教えてもらいたいかを基準にしました。 反応は信じられないほどでした！ 最初の 3000 か月で 100 か国以上から XNUMX 人以上の学生がコースに登録しました。

簡単な問題を解くことに取り組んでも、上達することはありません。

知らないことを理解する最も効果的な方法は、実際に経験することです。 そうやって学びました。 挑戦的なタスクを選択することで、これまで聞いたことのない多くの新しいテクニックを学びました。

XNUMX 番目の問題に取り組むごとに、何か新しいことを学べるはずです。 問題を選択するときはより注意してください。 より難しい問題を選択してください！

SPOJ のこれら 250 の問題を完了すると、スポーツ プログラミングの核となるトピックの基本を理解できるようになります。 基本的なアルゴリズムの背後にあるロジックを深く理解していれば、高レベルのアルゴリズムはそれほど複雑ではないように見えます。 こうすることで、自分の知識を最大限に活用することができます。

それぞれの主要テーマをさらに深く掘り下げる

貴重な資料はこちら たくさんの情報とともに。 そこには、各トピックのトップ 10 のアルゴリズムとデータ構造が表示されます。 SPOJ からの 250 の問題を解けば、このリストから多くのことが分かるでしょう。 しかし、これまで聞いたことのない多くのことに遭遇することもあります。 したがって、これらのトピックを昇順に学習してください。

新しいことを学んだ後に知識を強化しないと、すぐにすべてを忘れてしまいます。
新しいアルゴリズムを学習したら、実際に使用することをお勧めします。 2 ～ 3 つのタスクを実行してください。 SPOJ でアルゴリズム タグを探します。 そこでは、このアルゴリズムを解決する必要がある問題が見つかります。 まずこれらの問題に対処してください。

動的プログラミングをマスターしてください。それがあなたを勝利に導きます
私の経験から言えば、どの競技にも少なくとも XNUMX つは問題があります 動的プログラミング。 「動的プログラミング」という言葉を聞くと、まったく理解できずに頭が痛くなる人も多いでしょう。

そして、これは良いことです。 動的プログラミングを理解していれば勝てるからです。

私は動的プログラミングが好きで、一番好きなトピックです。 動的プログラミングの秘密は、ローカルな選択だけでなく、グローバルに最適な選択を行うことです。 問題をより単純なサブ問題に分割する必要があります。 これらの下位問題はそれぞれ XNUMX 回だけ解決してください。 次に、解決された部分問題を組み合わせたソリューションを作成します。 貪欲なアルゴリズム - 動的プログラミングの逆。 各ステップで局所的に最適な選択を行う必要があります。 そして、局所的に最適な選択は、悪い全体的な解決策につながる可能性があります。

新しい概念を学びながら、次のことを確認してください TopCoder チュートリアル。 とても詳しくてわかりやすいです。 彼らのおかげで理解できました バイナリインデックス付きツリー.

一生懸命働く

何年も練習せずにオリンピックで優勝したアスリートのことを聞いたことがありますか? 私は違います。

毎年、コンピューター オリンピックの準備は XNUMX 月に始まり、XNUMX 月に終了しました。

この8か月間、私は毎日5時間練習しました。

はい、私はこの 5 時間をアルゴリズムの問​​題を解くだけに費やしました。 8時間、場合によっては10時間も練習した日々を思い出します。 なぜ？ 好きだったから。 毎日学校から家に帰ると、私は寝室に直行し、コンピューターの前に座って、新しい問題の分析を始めました。 あるいは、この問題を解決するために知る必要のある新しいアルゴリズムを学んでいました。

勝ちたければ、同じことをしなければなりません。 問題を選択し、それに固執します。 スーパーに行くときや車を運転しながら考えてみてください。

睡眠中、脳はその日に収集した情報を断片化解除することをご存知ですか? 彼は本棚に本をアルファベット順に積み上げているようだ。 基本的に、あなたの脳はあなたが直面しているさまざまな問題について考えます。

これは上手に使えますね。 寝る前に難しい問題を読んで、それを解決するために何が必要かを思い出してください。 この段階では、解決策自体を探す必要はありません。 寝る。 あなたの脳はこの問題を処理し始めます。 目が覚めると、寝ている間に解決策を見つけたことに驚くでしょう。

自分で試してみてください。 まるで魔法のようです。

動画ブログを作りました

この短い段落はスポーツ番組とは関係ありません。 もしあなたがXNUMX代で、私が世界をどのように見ているか疑問に思っているなら、ぜひチェックしてみてください。 Youtube 上の私のビデオ ブログ。 その中で世界、生命、コンピューターサイエンスについて話します。

賢く仕事をする

これが成功の秘訣です。 目標が必要です。

私たちは人間であり、それが好きです 先延ばしにする。 私たちは常に、今やらなければいけないことを先延ばしにしたくなります。 ダイナミック プログラミングの問題に対処するよりも、Netflix を見るほうがずっと楽しいです。 あなたはこれを知っているので、それを修正する必要があります。

先延ばし癖を克服する方法

自分自身の目標を設定します。 新しいことを学べる興味深い問題が必ず見つかります (上記のリソースを確認してください)。 しかし、これらの問題は単に読むだけではなく、解決する必要があります。

そこで私が先延ばし癖を克服した方法をご紹介します。 私は紙のカレンダーを始めて、解決したい問題を毎日詰め込みました。 私はいつもXNUMX日前に問題を記入していました。 そのため、その後の数日間で時間を管理する方法がわかりました。

だから私は常にモチベーションを保っていました。 カレンダーの次の日を埋めるために、いくつかの問題を解決し、新しい問題を見つける必要がありました。 解決した問題を消していくのはとても気持ちいいです。 あなたも気に入っていると思います。

自分だけの紙カレンダーを手に入れましょう。 明日忘れてしまうような別の ToDo リストを携帯電話に作成しないでください。

効果的にデバッグする方法

プロになりたいですか？ そうであれば、「頭の中でデバッグする」必要があります。
これはデバッガーをまったく必要としないため、私が知っている中で最も効率的なデバッグ手法です。 あなたの脳は複数のコードブランチを一度に調べて、コードのより広範な概要を得ることができます。 クラシックデバッガ.

自分自身を、チェスをプレイして 3 手先を考えるグランドマスターにたとえることができます。

私はこのテクニックを最初の防御線としてのみ使用します。 次に、実際のデバッガを使用します。

頭の中でデバッグする方法を学ぶには、練習する必要があります。 問題の解決策を検証して「間違った答え」が得られた場合は、すぐにデバッガー ボタンに進まないでください。 コードをもう一度読んで、「この行で何が起こっているのか?」、「ここの "if" はプログラムにどのような影響を与えるのか?」、「ループを終了するときの反復子の値は何か?」を考えてください。

こうすることで自分で考えることができます。 時間が経つにつれて、コードを書いてその場でデバッグする方法を学びます。

著者について

Andrei Margeloiu は、起業家精神、スタートアップ、アウトドアに興味を持つ熱心なプログラマーです。 彼に連絡できます LinkedIn で.

翻訳: ダイアナ・シェレミエワ

出所： habr.com