feature image

2022年3月15日 | ブログ記事

競プロをやるメリット

新歓ブログリレー7日目の記事です。
競プロが何なのか、始め方や精進の仕方は以下の記事を読むと良いでしょう。

競プロをやるとどんな良いことがあるのかを独断と偏見で列挙してみました。

データ構造の理解が深まる

データ構造を知っていますか。僕は知っています。スタックやキューなんかの構造化されたデータの集まりのことです。データ構造というのはそれだけ知っていても意味がなくて、具体的な問題に適用することで初めて効果を発揮するものです。

例えば、要素数Nのある集合に対して

という操作を高速に行いたいとします。例えば{2, 3, 5, 7, 11, 13}という集合に対して以下のように操作すると

> 5は存在するか
> ある

> 4は存在するか
> ない

> 4を追加
> {2, 3, 4, 5, 7, 11, 13}

> 4は存在するか
> ある

という風になります。

最初の操作では集合の中で5があるかを求めます。人間がこれをやるのは簡単ですが、コンピュータにこれを指示するにはどうすれば良いでしょうか。データがばらばらに並んでいる状態では結局はソートするかそれに相当する操作を挟む必要があるでしょう。そこでデータは予めソートされているとします。前から順番に調べていくこともできますが、二分探索というアルゴリズムでに比例する計算時間で実行することができます。があるかを求めるには、まず真ん中の要素にアクセスして、がそれより小さければ前半を探索、大きければ後半を探索します。辞書で単語を探すときに真ん中のページを開いて、次に前半または後半の真ん中のページを開いて、という風に徐々に探索範囲を狭めていくやり方をしていた人も多いかもしれません。それと全く同じです。

3番目の操作で{2, 3, 5, 7, 11, 13}に4を追加して{2, 3, 4, 5, 7, 11, 13}としました。人間がこれをやるのは簡単ですが、コンピュータにこれを指示するにはどうすれば良いでしょうか。C++の固定長配列やvectorならデータはメモリ上でも連続的に並びます。しかしデータを追加する度にそれより後方にあるデータを全て移動させるのは効率的ではありません。前方にあるデータを移動させるときも同様です。しかしデータが昇順に並ぶ保証が無ければ二分探索が使えなくなるように見えます。

そこでデータが以下のような平衡二分木というものになっているとします。平衡というのは二分木のノードが縦ではなく横に広がっていることです。AからBへ矢印が引かれているときAからBへアクセスできることを表します。データ間の関係を抽象的に表したものなのでデータのメモリ上の配置とは無関係です。左の矢印の先にあるデータは元のデータより小さく、右の矢印の先にあるデータは元のデータより大きくなっています。

二分木の一番上のノードから辿っていけば二分探索と同じことができます。ここでは解説しませんが、データを追加しても二分木の平衡を保つことができます。C++のsetなどは平衡二分木で実装されています。

アルゴリズムの理解が深まる

競プロの問題は答えが出れば良いというわけではありません。実行時間やメモリ使用量に関して制約があります。アルゴリズムを内容だけ理解するのではなく、実際に手を動かして実装してみることのメリットの一つは、計算機のリソースに対する感覚に敏感になれることです。与えられた時間/空間計算量の制約の中で、このアルゴリズムは使えるがこれは使えないとか、データ構造はどうすべきかなど、考えることは色々あります。「自分に作れないものは理解できない」[1]って良い言葉がありますが、その通りだなあと思います。


  1. リチャード・ファインマン ↩︎

難問が揃っている

大学で出される課題とは雰囲気が違うタイプの問題が大量に揃っているのは嬉しいです。

難問の例(↑易↓難)

レベルの高い環境

センター/共通テストは受験者が世代あたり半分弱で平均が6割というところです。AtCoderでは、参加する時点で既にバイアスがかかってますが、人数がレートに関して単調減少なので上位層に対して解像度が高いです。このような高いレベルの環境で自分がどの位置にいるか分かるのは面白いかもしれません。

AtCoderの色のランクに対する評価があるので貼っておきます。

ちなみに

自分は今競プロやってないです(は?)

明日はUzakiさんの記事です。楽しみ~~

season1618 icon
この記事を書いた人
season1618

数学と物理と競プロをやります。

この記事をシェア

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

関連する記事

2022年4月7日
traPグラフィック班の活動紹介
annin icon annin
2022年4月5日
アーキテクチャとディレクトリ構造
mazrean icon mazrean
2022年3月29日
課題・レポートの作成、何使う?【新歓ブログリレー2022 21日目】
aya_se icon aya_se
2021年4月18日
ベズー係数とN項の拡張ユークリッドの互除法
0214sh7 icon 0214sh7
2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase icon Silviase
2022年4月19日
【入門】JUCEを使ってVSTプラグインを作ろう!!
kashiwade icon kashiwade
記事一覧 タグ一覧 Google アナリティクスについて