プログラミング講座 #5 競プロをやってみよう

プログラミング講座 #5 競プロをやってみよう @ZOI_dayo

「競技プログラミング」とは? 「問題が与えられて、それを解くコードを書く」というものです 「アプリ作ってプレゼンして競う」って感じではなく、その場での瞬発力がいる感じです 競プロを少しやっておくと、いろんな分野に役立ちます 特に、「より早く動くコードを書く」力がめちゃくちゃ身につくので、 (ガチらなくてもいいですが)一度は参加してみることをお勧めします ※ #3「コードを書く」までは理解しておいてください

例題 AtCoder Beginner Contest 100より「A - Happy Birthday!」(考えてみてね)

問題を解いてみる 「どちらも8以下ならもちろん可能、どちらかが8超えると無理」では?

コード(イメージ) if(A <= 8 && B <= 8) { print(“Yay!”); } else { print(“:(”); } ↑本体部分はこれで終わり (上のは仮言語なのでこのままでは動きません)

なんの言語で解く? 競プロはAtCoderというサイトでやるんだけど、かなりの数の言語に対応してる ただ、利用者が多い言語を使った方が、勉強する時に楽 なので、ほぼほぼPythonとC++の2択になる

Python vs C++ Pythonは最近流行ってるし、書きやすくていいんだけど、型というシステムがない (型については#2でも書いてるのでぜひ見てね) 型がないから楽に書けるという面もあるんだけど、一度はしっかり型を理解した方がいい ってわけで勉強も兼ねてC++で解説します (あとPythonよりC++の方が実行速度が速かったりもする)

とりあえずC++書く VSCodeを開いて、好きな場所にファイル作って開いてください それから、とりあえず右の文を書いてください (なにこれ)

とりあえずC++書く これの説明をしてもいいのですが、色々知識がないと意味がわからないと思うので省略 今のところは「絶対変わらない呪文」として 書いておいてください (覚えなくても毎回コピペでOKです) プログラム本体は5行目のあたり、 {}の内側に書いていくことになります

とりあえずC++書く それでは先ほどのコードを書いてみましょう if(A <= 8 && B <= 8) { print(“Yay!”); } else { print(“:(”); } ↑こんなイメージでしたね

とりあえずC++書く これをC++で書くとこうなります (とりあえずA=5、B=4で固定で、正答ではないです) 1行ずつ解説していきます まずは5行目、これは変数定義ですね int型(整数)の変数A、Bを作り、値を入れています もちろん、int A=5; int B=4;と 2行に分けてもOKです

とりあえずC++書く 6、8、10行目は普通のif文です 他の言語とあまり違いはないので、 わからなかったら#1を見てください 「かつ」を「&&」で表すところがポイントかな? ちなみに「または」は「||」(Shift+¥を2つ)です あとA<=B<=Cみたいにはかけません、 2つづつ比較してください

出力のやり方 7、9行目はprint()やconsole.log()に相当するものです 表示というか出力というか、そんな感じです coutが出口、<<がゲームとかの加速床(左向き) というイメージで見てください 7行目では、coutに向かって、”Yay!”という文字と endlという何かが飛び込んでいきますね

出力のやり方 “Yay!”は他の言語と同じように「文字列」です (string型、と名付けられています) endlとは、end line、すなわち改行です 答えをcoutに流し込んだ後はendlを送るように してください 答えを入れて、Enterキーをパーンと押す感覚です

(おまけ) endlとは? 細かい話をすると、endlは改行+flushというものです coutに流し込んだ文字は、実はまだ出口から 出ていない、すなわち画面に表示されてません ある程度貯まったら一気にまとめて出力しようと 考えているのですが、”Yay!”が表示されなければ 間違いになってしまいます なので、解答の終わりにはendlを付けでflush(送信)し 最後まで送信されるようにしてるわけです

入力のやり方 ところで、このままではA=5、B=4の場合しか 考えていません 競プロというのは、誰かがコードを採点するのでは なく、大量のサンプル全てで正解の答えを出せば 正解、ということになっています そのためには、A、Bが何なのかを 毎回受け取らないといけません

入力のやり方 そこで使えるのがcinです (coutが出口、cinは入口) 使い方はこんな感じ int A, B; cin >> A >> B; cinは「AtCoderからの入力を一つ一つ代入する」だけなので、 先にA,Bを定義するのを忘れずに! (int A=0, B=0;としてもいいですが、上書きされるので必要ないです)

C++の実行 つまり、右のコードになります これを実行してみたいのですが、どうすれば..? 自分のPCでの実行はまあまあ大変なので、まずは AtCoderさんが提供してくれているコードテスタを 使いましょう

AtCoderへ登録 AtCoderは、日本最大級の競技プログラミングサイトです 毎週土曜日の夜にAtCoder Beginner Contest (ABC)というオンライン大会が開かれていて、 日本で競プロやるならAtCoderが一番人気です (なお難易度はBeginnerではないので、1~2問解ければ十分です) とりあえずアカウント登録してきてください https://atcoder.jp/

• https://atcoder.jp/

C++の実行 これはAtCoderのコンテスト、 「AtCoder Beginner Contest 100」のA問題です このページに飛んでみます https://atcoder.jp/contests/abc100/tasks/abc100_a 右上の を押してください

• https://atcoder.jp/contests/abc100/tasks/abc100_a

C++の実行 まずは右のコードをコードテスト画面に 貼り付けてください 言語は「C++(GCC)」を選びましょう (バージョンいくつかあれば好きにどうぞ)

C++の実行 そして、標準入力欄には、AtCoderからの AやBの入力を入れます 問題ページの入力例1、「5 4」を入れて実行です 結果が「Yay!」となりましたか?

C++の実行 入出力例の2、3についても結果が合うか確認してください もし合った場合、問題に書いてある3つのテストケースはクリアです! ただ、3つだけでは本当に合ってるのかわかりません AtCoderでは、コードがあっているかを判定するために、 もっとたくさんのテストが用意されています

提出 なので、テストを受けさせる、つまりコードを提出してみます 問題画面下のところに、先ほどのコードテストと同じような画面があります ソースコードを貼り付け、言語がC++(GCC)になっていることを確認して、 提出をしてみてください 提出結果は、画面上部「提出結果」→「自分の提出」で見れます

提出 右の方に、「結果」という色がついているところがありますね ここが「WA」(灰)なら実行待ち、「AC」(緑)なら正解、 「WA」(橙)なら間違い、「TLE」(橙)なら実行時間が長すぎてアウト、です テストを1つでも間違えれば0点になるので注意してください(部分点は基本無いです)

過去問を解く こんな感じで色々解いてみましょう ただ、AtCoder公式ページでは、過去問がかなり見にくいです なので、AtCoder Problemsというサイトを使います https://kenkoooo.com/atcoder#/table/

• https://kenkoooo.com/atcoder#/table/

過去問を解く AtCoder Problemsでは、過去問を見るだけでなく、その難易度も表示してくれるので とても楽しいです 問題の難しさ(およびユーザーランク)は、灰→茶→緑→水→青→黄→橙→赤(→銀→金) と上がっていきます Problemsの茶色の問題は、茶色ランクの人が50%で解ける、というイメージです

適当に解いてみる 例えばABC297-A「Double Click」を解いてみます まず入力を受け取るのですが、今回は入力される個数が不定ですね

配列 こういう時は、Tという配列を作り、その中に一つずつ入れていくと楽です ただ、C++の配列はクセがあるので、vectorというものを使います

C++の配列(vector)

JavaScriptなら、let a=[1,2,3];
Javaなら、int[] a = {1,2,3};のように書きます
これが、C++では vector<int> a({1,2,3});となります
(int a[] = {1,2,3}とも書けますが、メモリとかの知識が必要で使いにくいです)

vectorですが、数学のベクトルとはあまり関係ありません、ただの配列です
a({...})の()部分は省略できます、つまりvector<int> a;でもOKです

C++の配列(vector)

長さや初期値をセットすることもできます
さっきのように、初期値が決まっている場合はvector<int> a({1,2,3});、
要素数(長さ)は決まっている場合はvector<int> a(100);、
要素数が決まっていて全部-1にしたい場合は vector<int> a(100, -1);と書けます

競プロでは、vector<int> a(N);で使うことが多いかな? まあ色々あります

配列での入力 ではこれの入力を考えてみましょう

配列での入力 int N, D; cin >> N >> D; vector<int> T(N); for(int i=0; i<N; i++) { cin >> T[i]; } こんな感じでできます forでN回ループして、cinからTの該当箇所に 一つ一つ代入している感じです (T[0]がT1となります)

実装 あとは簡単です つまり、「Tを前から見ていって、前との差がD以下のところがあればその秒数を、 最後までなければ-1を出力する」ということです for(int i=1; i<N; i++) { if(T[i] - T[i-1] <= D) { cout << T[i] << endl; } } これがベースです(はみ出さないように1~(N-1)のN-1回ループになってるのがポイント)

実装 これを、「T[i]の出力をしたらそこで実行終了、最後まで出力しなければ-1を出力」したい 実行の強制終了は「return 0;」でできるので、こんな感じ for(int i=1; i<N; i++) { if(T[i] - T[i-1] <= D) { cout << T[i] << endl; return 0; } } cout << -1 << endl; 一度もreturn 0;が実行されない場合だけ最終行が実行されることに注意

実装 あとはこれを#includeナンタラ〜とかと組み合わせる ぱっと見るとややこしいかもだけど、 よく読めばわかるはず... こんな感じで、ProblemsからA~B問題を いくつか解いてみてください〜

コンテストへの参加 AtCoderでは、ABCなどのコンテストに参加することで、レートが変わるという仕組みに なっています なので、もし予定が空いていれば、ぜひ参加してみましょう! (最初は1問も解けなくてもちょっとだけ上がります) 基本、ABCは土曜日の夜9:00から10:40の100分間です ただ、もう無理だなーと思ったらそこで終わってもいいと思います (もちろん、コンテスト終わるまでは他人に教えてはダメです)

コンテストへの参加 AtCoderのトップページにこんな欄があるので 参加したいものを選び、 しましょう Ratedはレート変動あり、Unratedはなしです 体調悪ければUnratedとかでもいいですが、 最初はレートが減ることはあまり無いので、 せっかくなのでRatedにしておきましょう 時間になったらコンテストページにいき、問題を見てコードを書いて提出する感じです ちなみにネットでの検索とか事前に書いたコードのコピペとかはOKです

(おまけ) AtCoder Junior League 2023/5から、中高の学校対抗システムができたらしいです https://atcoder.jp/contests/ajl2023 に参加登録して、 あとはいつも通りコンテストに参加すれば、勝手に学校のスコアが上がるそうです 参加しておいて損はないと思うので、ぜひ登録してみてください〜

• https://atcoder.jp/contests/ajl2023

(おまけ) AtCoderの色(レート)について AtCoderをやってみるとわかりますが、しばらくは灰色から抜け出せません というか参加者の50%は灰色なので、灰=最低ランク、というイメージは少しズレてるかも AtCoderはかなりレベルが高いので、 ● ● ● レート200(灰の真ん中)以上なら「他社サイトであれば十分なランクがつく」 茶は「(他社転職サイトで)上位1~2%の最高ランクに到達出来る人が数割いる」 緑は「エンジニアとしてもある程度の安心感がある」 みたいな感じらしいです(AtCoderの社長が言ってた) https://chokudai.hatenablog.com/entry/2019/02/11/155904 つまり、ずっと灰だとしても全く心配しないでください、とりあえず楽しみましょう

• https://chokudai.hatenablog.com/entry/2019/02/11/155904

まとめ 競技プログラミングとC++の紹介でした〜 普通にプログラミングしてるだけだとネタ切れになりやすいし、めっちゃ勉強にもなるので 暇つぶしネトゲ感覚でぜひ楽しんでもらえればと思います 競技プログラミングしてると、何かやりたいことができた時、 「やりたいことをコードに起こす」ということが早くできるようになります あとC++は、特にゲームやアプリ作ろうとしてる人はぜひ触っておくべきです そういうの作るには型とか高速化とか大切なんです、まあ詳しいことはまた別の時に ...

終わり