競プロのすゝめ - yudegakiのブログ

はじめに
競プロとは...
競プロができるサイト
面白い問題
競プロ入門
おすすめの問題
さいごに

はじめに

この記事はKogakuin Univ Advent Calendar 2019 - Adventar8日目です。

adventar.org

記事を丁寧丁寧丁寧に作成していたところ、時が過ぎていました。

気を取り直して記事を書いていきます。今回は競プロのすゝめということで、僕のTwitterを見てる方ならお気づきの方も多いと思います。

そうです、競プロはいいぞという記事となります。

競プロとは...

安心&安全のWikipediaで見てみましょう

競技プログラミング（英語: Competitive programming、略称: 競プロ）とは、プログラミングコンテストで行われる競技の一種である。

競技プログラミングでは、参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。

出典：競技プログラミング - Wikipedia

情報学部の1年生には、新入生のつどいの際に紹介させていただいたので、覚えてる人もいるかな...?

簡単に言うと、プログラミングの授業の課題の発展版です。

2年次に受講できる「離散数学」や「アルゴリズムとデータ構造」を履修した人なら面白いと感じるかもしれません。感じるよね？？？

競プロができるサイト

ここではリンクを貼るだけに留めておきます。

初心者の方にはAtCoderとAIZU ONLINE JUDGE(通称：AOJ)がおすすめかな。

面白い問題

先程紹介したAtCoder社が開催するコンテストでは、時々(文章が)面白い問題が出題されます。面白いからといって舐めてかかると顔面に右ストレートを喰らいますが...

実際に問題文を見ていきましょう

Mulitple GIft

高橋君*1は、日頃の感謝を込めて、お母さんに数列をプレゼントすることにしました。お母さんにプレゼントする数列 $A$ は、以下の条件を満たす必要があります。

$A$ は $X$ 以上 $Y$ 以下の整数からなる

すべての $1 \leq i \leq | A | - 1$ に対し、 $A_{i + 1}$ は $A_{i}$ の倍数であり、かつ $A_{i + 1}$ は $A_{i}$ より真に大きい

高橋君がお母さんにプレゼントできる数列の長さの最大値を求めてください。

出典：C - Multiple Gift

日頃の感謝を込めて母親に数列をプレゼントするなんて... 普通の家庭ならサイコ扱いされてもおかしくないですよね(笑) お金はかからないので最後の手段としてはアリかもしれない？？？？

Card Eater

すぬけくん*2はカードゲームで遊ぶことにしました。 $N$ 枚からなるカードの山があり、上から $i$ 枚目のカードには整数 $A_{i}$ が書かれています。

すぬけくんはこのカードの山に対し $0$ 回以上、以下の操作を行い、残ったカードに書かれた値が互いに異なるようにしたいです。最大で何枚のカードを残すことが可能か求めなさい。なお、 $N$ は奇数であり、少なくとも $1$ 枚のカードを残すことが可能であることが保証されます。

操作：カードの山から任意の $3$ 枚のカードを抜き出す。抜き出したカードのうち書かれた値が最大であるようなカード $1$ 枚と最小であるようなカード $1$ 枚の合計 $2$ 枚を選んで食べる。その後残った $1$ 枚をカードの山に戻す。

出典：D - Card Eater

一見まともな問題のように思えますが、操作をみるｔ、、、

口からトランプを出す人*3ならたくさん見てきましたが、カードを食べる人は見たことがないですね。逆再生であることを祈るばかりです。

ドキドキデート大作戦高橋君

高橋君の通っている学校で大掃除が行われることになりました．学校には $N$ 個の教室があり，各教室は $1$ から $N$ まで順番に番号付けられており，左から右に並んでいます．

高橋君の学校には高橋君を含め $M$ 人の生徒がおり，掃除すべき連続した教室の区間(掃除区間と呼ぶ)は $M$ 個既に決まっています．しかし，それらの掃除区間を誰が担当するかは決まっていません．異なる生徒には異なる掃除区間が割り当てられ，割り当てられた生徒はそれに含まれる全ての教室を掃除しなければなりません． $1$ つの教室が複数の掃除区間に含まれることがあります．

高橋君は大掃除の日に女の子とのデートの約束をしていることに気づきました．デートをサボってしまうと何が起こるか分からないので大掃除をサボることに決めました．前述の通りいくつかの教室については複数の掃除区間に含まれていることがあるので，高橋君の担当分をサボっても全ての教室を誰かが掃除してくれさえすれば，サボったことがバレないことに気づきました．掃除されていない教室があった場合には，サボったことがバレます．

あなたの仕事は高橋君のために，サボってもバレない掃除区間を全て教えてあげることです．

なお，この学校の生徒は高橋君を除きみんな真面目なので，高橋君以外がサボることは無いと仮定してください．

出典： B - ドキドキデート大作戦高橋君

デートのために大掃除をサボるとは漢の鑑ですね(泣)

AtCoderでは、このように模範となる人の行動が問題として出題されることがあります。問題を解くだけで、人としてもプログラマとしても成長できるとはお得ですね(?)

器物破損！高橋君

良く見てみるとカードの有効期限が切れていたので、高橋君は諦めて魚屋に直接うなぎを買いに行くことにしました。
　彼の住む街は長方形の形をしており、格子状の区画に区切られています。区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。また、塀の区画は通ることができません。高橋君の家から魚屋までの道のりは非常に複雑なため、単純に歩くだけでは辿り着くことは困難です。
　しかし、高橋君は腕力には自信があるので道に上下左右で面している塀を $2$ 回までなら壊して道にすることができます。

　高橋君が魚屋に辿り着くことができるかどうか答えてください。

出典：
C - 器物損壊！高橋君

腕力に自身があると、塀を壊して進むっていう発想が出てくるんですね...

僕もリングフィットアドベンチャー*4 で上腕二頭筋を鍛えて、講義に遅刻しそうな時に壁を壊していけるようになりたいです

他にも面白い問題はたくさんあります！興味があったらこのサイトに飛んでみると幸せになれるかも？(上記の問題はこのサイトの一部を選んで紹介させていただきました)

ugis.hatenadiary.jp

競プロ入門

さて、先程の問題をみて「解けねぇよ...」と思った方もいらっしゃるでしょう(私もそうでした)

何事もそうですが、触れたことのない分野の内容は実際の難易度よりはるかに高く感じてしまうものです。ん？楽に解けてしまった？？？*5

では本題の競プロ入門についてお話していきます。

先程色々なサイトを紹介しましたが、結論から言うとAtCoderで問題を解いてみるのがおすすめです。

主な理由としましては

コンテスト後の公式解説がしっかりしている(YouTubeでの解説放送&PDF)
多数の言語に対応している(言語アップデートがもう少しで来るはずなので更に増える)
解法(考察)をブログ等でアウトプットする人が多い
コンテスト数が多い
UI面(直感的に操作できる)

などなど、他のコンテストでは(あまり)無い特徴が多く、初学者にはおすすめのポイントがたくさんあります。

特にUI面は本当に重要だと思います。コンテストまで辿り着けなければ元も子もないですからね。あれ？そういえば、ついこの間UIが変わる前まで、、、だったところがあったような無かったような

さいごに

いかがでしたか？少しでも競プロに興味を持っていただけたならば幸いです。

これを機に参加してださる方は、はじめの頃はレートなんて気にせず、週１のちょこっとした趣味として気軽に参加してみるのがいいと思います。#月刊競プロは役に立たない等の意見をお持ちの方もいらっしゃると思いますが、年々参加者が増加してますし(今年の増加率はやばかったな、、、)やっておいて損するものでは無いと思います。

また、分からない問題や、聞きたいこと等ございましたら、私とか

twitter.com

メンバーに聞いていただければ(できる範囲で)お答えできると思うので、遠慮せずバシバシ聞いてください。(そのままKogCoderに入って♡)

次回の記事は、面白い問題から1問選んで解説するものになると思います。また丁寧に書いて時空を歪めてしまうかも

それでは、某学院大学に競プロ勢が増えることを願ってこの記事を終わりとさせていただきます。

最後までご覧いただきまして、ありがとうございました。

*1:AtCoder社の社長である高橋直大氏の名字から取ったと予想されている

*2:AtCoderの社員さんのTwitter垢名から取った可能性が微レ存？？？

*3:マジシャン

*4:Nintendo Switch用のソフトで、プレイするとガッキーになれることから全国各地で飛ぶように売れ、転売ヤー達がこぞって求めるようになった伝説のゲームである。ちなみに発売から約2ヶ月たった今(執筆当時)も入荷未定で予約待ちすら難しい状況である。

*5:KogCoder (@kogcoder) | Twitterに入りませんか？いつでもお待ちしております。