【電通大生向け】基礎プロの知識だけで始められる(?)競技プログラミング
追記(2022/9/13)
この記事に書かれていることはかなり適当でガバガバなので、真面目に競プロを始めたいという人は以下のようなまともな記事を参考にして、この記事は話半分で聞いておくことをおすすめします。
- 追記(2022/9/13)
- はじめに
- 前置きというか、背景的な何か
- 注意点
- A - 1.00.はじめに
- B - 1.01.出力とコメント
- C - 1.02.プログラムの書き方とエラー
- D - 1.03.四則演算と優先順位
- E - 1.04.変数と型
- F - 1.05.実行順序と入力
- G - 1.06.if文・比較演算子・論理演算子
- H - 1.07.条件式の結果とbool型
- I - 1.08.変数のスコープ
- J - 1.09.複合代入演算子
- K - 1.10.while文
- L - 1.11.for文・break・continue
- M - 1.12.文字列と文字
- N - 1.13.配列
- O - 1.14.STLの関数
- P - 1.15.関数
- 1章終了
- 終わりに
- 追記(2022/12/28)
- 問題の解答例
- 脚注
はじめに
はじめまして、電気通信大学Ⅲ類機械システムプログラム所属なのにプログラミングにのめり込みすぎて*1留年が確定してしまったしゅん/Сюнという者です。みんなは気をつけようね…
要約
- 基礎プロの知識だけでいきなり競プロができるかというと、ちょっと厳しい
- だから先にAPG4bを基礎プロの内容と絡めながらやってみよう
- 基礎プロの予習をしたい人にとっても役に立つ…はず…
想定/対象読者
この記事は電気通信大学の学生のうち、以下のような人を想定しています。
- 基礎プログラミングおよび演習(以下、基礎プロ)を学んだけど知識の使い道がなくて持て余している人
- 基礎プロをまだ習っていなくて予習をしたい人
- 競技プログラミング(以下、競プロ)を始めてみたい人
逆に、以下のような人にはあまりおすすめできません。
- 電通大生でない人(授業のテキストについて触れたりするのでよくわからない部分が多いと思います)
- 既にプログラミングの知識が十分にある人(AtCoderでとっくのとうに灰色を脱出している人など)
- プログラミングに興味がない、あるいは嫌いな人(たぶん苦痛だと思います)
前置きというか、背景的な何か
書いてたら長くなっちゃったので飛ばしてもええんやで(要約:APG4bをRubyでやらないか?)
基礎プロについて
電通大には「基礎プログラミングおよび演習(fundamental programing)」という授業が2学期(1年後期)に存在しており、また必修単位なので必ず受けなければならないことになっています。この授業ではプログラミングに関する基本的なことをRubyとC言語を用いて学びます。おそらくプログラミング未経験者と経験者の間のギャップを埋めるのが目的だと思いますが、当時ほぼ未経験者だった*2自分にとっては少々難しく、特に後半のC言語のパートはついていくのに精いっぱいだったと記憶しています。
…ところで、とりあえず基礎プロの授業が終わった後なんですが、Ⅰ類とⅡ類ならまぁ発展的な授業があったりする(らしい)ので、この授業の知識も役に立つはずなんですよ。きっと。
問題はⅢ類です。ご存じⅢ類は理工系で、がっつり物理とかをやる一方、プログラミングについてはほとんどやりません(一応選択必修で数値計算とかの授業があったりするけど)。そのせいでせっかく習った基礎プロの知識を使う機会があまりありませんし、なんならプログラミングの勉強がそこで終わってしまいがち[要出典]です。もったいないですね。
その知識、競プロで活かしてみませんか?
競プロでスキルを伸ばしてみませんか?
競プロについて
競技プログラミングというのは、ものすごくざっくり言うと「学校とかの試験のプログラミング版」です。試験が「与えられた問題を制限時間内に解く」のと同じように、競プロでは「与えられた問題の条件を満たすようなプログラムを制限時間内に作成し提出する」ことを目標とします。競プロをやっているWebサイトはいくつかあり、日本ではAtCoderが有名です。
AtCoderでは様々なコンテストが開催されています。初心者向けのAtCoder Beginner Contest(以下、ABC)はその1つです。現在のABCではA~GとExの合計8問を100分以内でどれだけ多く、速く解けるかを競います。A問題が一番簡単で、後半の問題になるにつれて難しくなっていきます。*3
まぁそれはそれとして、実はABCのB問題までは基礎プロの知識だけで解けると、しばしば電通大生競プロer*4の間では言われています。…でも、それは本当なのでしょうか?本当に基礎プロの授業で習ったことだけで解けるのでしょうか?
実のところ、基礎プロを終えてすぐ競プロができるかというと、ちょっと厳しいものがあります。というのも…
- 競プロの問題文にはほとんどの場合、「入力は以下の形式で標準入力から与えられる。」みたいに、「標準入力」という初見だと謎の単語があり、これについて基礎プロではほとんど全く触れていない(厳密にはテキストのすみっこに標準入力のための関数がちらっと載っている…けどそれだけ*5 )。
- 追記(2023/6/7) コンピューターリテラシー*6の方の教科書に記述がありました…。
- 基礎プロにおいて、Rubyは「関数を記述したファイルを作成し、それをirb(REPL)で呼び出す」形式でしかやっておらず、一般的な「ruby ファイル名」での実行方法については付録でほんの少し触れるだけに留めているが、競プロでは後者の方式を採用している。
- C言語は、初心者向きではない*7し、競プロ向きでもない(競プロにおいてしばしば必要になるいくつかの機能が最初から使えず、自力で実装しなければならない。)
逆に言えば、この辺の問題を何とかできれば、基礎プロの知識で競プロで戦うこともできるようになる…はずです。
APG4bについて
AtCoderにはAtCoder Programming Guide for beginners(APG4b)というプログラミング初心者のための教材があります。
この教材ではC++という言語*8を用いてプログラミングの基礎を学ぶことができます。当然ながら、基礎プロの内容と被っているところも結構あります。
また、先に述べた通り、プログラミング未経験者がいきなり基礎プロを受けると初見の概念のオンパレードでそれなりに苦労すると思います。まぁ最近なら高校生(なんなら中学生)の時からすでに経験済みだったりもするのでしょうが。
せっかくなので、APG4bで基礎プロの予習/復習をしながら競プロの準備をしてみませんか?
準備
Rubyとかのインストール
AtCoderでもコードテスト機能があるのでブラウザだけでも一応できますが、自分のパソコンでも実行できるようにしておいた方が楽になります。たぶん基礎プロの教材のところに資料が載っているのでそれを参考にRubyをインストールしてください*9。ついでにVSCodeもインストールしておくとよいでしょう(もちろん使い慣れているエディタがあるならそれで)。
(ググったらなんかでてきたので、これを参考にしてもいいかも)
AtCoderのアカウント登録
ここのチュートリアルページを参考にアカウントを登録しましょう。
そうしたらAPG4bのページに移動して、参加登録のボタンを押します。これでAPG4bを始める準備は完了です。
注意点
さて、いよいよここからAPG4bのページを参考にしながら本家の内容をRubyで置き換えたものを使って説明…したいところなのですが…そのまま書くとほとんどが内容丸パクリになってしまうので…本家の内容をもとに作ったコードを貼り付けて、それにちょっと補足する方式で行こうと思います(例えるなら教科書の代わりに授業で取ったノートを公開するような感じ?)*10。
他にもいくつか注意点を
- APG4bの1章だけやります。2章以降のもののうち、基礎プロで触れているものは最後に紹介だけしておきます。
- 各見出しから対応するAPG4bのページに飛ぶことができます。
- タイトルは本家のものに合わせているため、Rubyとは合わない部分があります。
- 本家のページを適宜参照しながら読んでください。本家の文章をそのまま読むだけで済む部分は省略していたりします。
- 私はRubyにはあまり詳しくはありませんし、参考にするのは基本的に基礎プロの教科書だけです。間違っていても許し亭許して…
- [x.x.x]みたいに書かれているところは、基礎プロの教科書において同様の内容が書かれている章の番号を表します。が、自分の基礎プロの教科書(2020年版)を参考にしているので、もしかしたら現在の版と内容が異なっている可能性があります(と言っても大きく内容が変わっていることは無いと思いますが)。
- 何か問題があったらこの記事を削除します。
A - 1.00.はじめに
この記事ではRubyという言語を使います。
問題
言語をRuby(2.7.1)に変更し、以下のコードをコピペして提出しましょう。(PCで見ている人はコードの部分をダブルクリックすると全選択できるようになっています。)
puts("Hello, world!")
自分の環境でやる場合はだいたい以下の通りです。
- 拡張子が.rbのファイルを何かしらの名前で作る(例:1.00.rb)
- そのファイルにコードをコピペして保存する
- PowerShellを起動する(Macならターミナルかな?)
- 「ruby ファイルのパス」と打ち込んでEnterする(例:ruby .\1.00.rb)
B - 1.01.出力とコメント
キーポイント
- C++と違い、必ず最初に何か書いたりmain関数が必要だったりするわけではない
puts("文字列")
で文字列を出力できる#
と書くことで、その行の#
以降がコメントになる
ノート
# Rubyにはmain関数はない # 出力にはputs()を用いる puts("Hello, world!") puts("こんにちは世界") # print()は改行無し出力 print("a") puts("b") puts("c","d") print("e","f") puts("") puts(2525) # コメント =begin 複数行もできる (基礎プロ範囲外) =end
Hello, world! こんにちは世界 ab c d ef 2525
メモ
- Rubyで文字列を出力するには
puts()
を使います[2.2.3] *11。 - Rubyで文字列を扱う場合、
" "
または' '
で囲む必要があります。" "
の場合は様々な機能が使え、' '
の場合は文字列をそのまま扱います[2.1.1]。今後は基本的に" "
の方を用います。 - また、
puts()
では自動で改行が行われます。 - Rubyでは行の最後に
;
を入れる必要はありません。が、1行に複数の文を書きたいときは;
で区切る必要があります[1.2.2]。 print()
を使うと改行無しで出力します[8.4.7]。- 複数の文字列を入れた場合、
puts()
だと1つずつ改行して出力し、print()
だとくっつけて出力するようです(今知った)。どこかで役立つかもしれません。 - Rubyでは
#
からその行の終わりまではコメントとなります[2.3.1]。コメントはプログラムに影響を与えません*12。 - Rubyでは全角文字でもエラーはそんなに出ないはずです。たぶん。でも基本的には半角文字で書く方が良いでしょう。
問題
以下のリンク先に問題文が載っています。解答例は最後にまとめておきます。
サンプルプログラム
puts("Hello, world!") puts("Hello, AtCoder!") puts("Hello, Ruby!")
Hello, world! Hello, AtCoder! Hello, Ruby!
C - 1.02.プログラムの書き方とエラー
キーポイント
ノート
#読みにくい print("a");puts("b");print("c","d");puts("") #読みやすい print("a") puts("b") print("c","d") puts("")
ab cd ab cd
メモ
- 実行時エラーとかは普通に発生するので気を付けましょう。
- インタプリタ型言語とコンパイラ型言語の違いについては省略します。ただ、一般的に前者は手軽に書いて実行できるものの実行速度が遅く、後者は面倒ですが速いです*14。
問題
A君が書いたプログラム
print("いつも, 252) puts(AtCoderくん)
AtCoderのコードテストで実行すると以下のようなエラーが出ます。
./Main.rb:2: unterminated string meets end of file puts(AtCoderくん) ^ ./Main.rb:2: syntax error, unexpected end-of-input, expecting ')'
D - 1.03.四則演算と優先順位
キーポイント
演算子 | 計算内容 |
---|---|
+ | 足し算 |
- | 引き算 |
* | 掛け算 |
/ | 割り算[1.3.1] |
% | 割った余り[1.3.1] |
ノート
puts(1 + 1) puts(3 - 4) puts(2 * 3) puts(7 / 3) puts(-7 / 3) puts(7.0 / 3.0) puts(7 % 3) puts(4 % 5) # puts(3 / 0) <- in `/': divided by 0 (ZeroDivisionError)
2 -1 6 2 -3 2.3333333333333335 1 4
メモ
問題
サンプルプログラム
puts() # ここに式を書く
E - 1.04.変数と型
キーポイント
型 | データの種類 |
---|---|
Integer | 整数 |
Float | 小数 |
String | 文字列 |
ノート
name = 10 puts(name) puts(name + 2) puts(name * 3) puts("") ####################################### a = 10 b = a a = 5 puts(a) puts(b) puts("") ####################################### c,d = 5,10 # 同時に宣言 puts(c) puts(d) puts("") ####################################### i = 30 d = 1.5 s = "Hello" puts(i + d) puts(i * d) puts(45 / 2) puts(i * d / 2) puts(s * 5)
10 12 30 5 10 5 10 31.5 45.0 22 22.5 HelloHelloHelloHelloHello
メモ
- Rubyでは宣言の必要はありません。宣言と代入を同時に行うというか、代入時に宣言されるというか…。
- Rubyは弱い型の言語[11.2.1]です。そのため変数に型は決まっていないし、異なる型同士の代入も可能です。
- Integer,Float,Stringの単語は覚えておいた方が良いです。関数名に使われていたりします(例えば、後述する
to_f
は整数などを実数(Float)に変換する関数です[2.3.1]。) 。- プログラミング言語における「関数」は数学におけるそれとは一部の性質が異なるものとなっています。基礎プロ未履修者は、今は「唱えると何かしらの効果がある呪文」みたいなものだと思ってください。呪文には何かしらの入力が必要だったり必要なかったり、何かしらの値が返ってきたり何も返ってこなかったり、何なら入力した変数とかを勝手に変えたりしますが、その辺については後で解説します。
- Rubyでは、
文字列 * 整数
の演算ができ、結果は指定した整数の回数だけ元の文字列を繰り返してできる文字列になります。 - Rubyでは、大文字で始まる変数は定数というものになり、再代入*15すると警告が出ます。 面倒な人はとりあえず小文字から始めるようにしましょう。
- 厳密には、整数はIntegerクラス、実数はFloatクラス、文字列はStringクラスに属するオブジェクト…らしいです。この辺はオブジェクト指向の話であり、競プロをする上で必須というわけではないので、基礎プロの9章で勉強をしてから
出直してこい改めてやりましょう。 - C言語の部分も参照してみると良いでしょう[11.2.1]。
問題
サンプルプログラム
seconds = 365 * 24 * 60 * 60 puts() # 1年は何秒か puts() # 2年は何秒か puts() # 5年は何秒か puts() # 10年は何秒か
F - 1.05.実行順序と入力
この章は競プロをする上でわりと重要なので真面目にやります。
キーポイント
- プログラムは上から下へ順番に実行される
gets
で入力を受け取ることができる- スペースと改行で区切られて入力される
プログラムの実行順序
基本的にプログラムは上から下へ順番に実行されます[1.2.2]。
入力
競プロではプログラムを実行した後、ほとんどの場合、標準入力(stdin)*16というところからデータが入力されます(それを元に計算なり何なりして答えを出力し、それが正解と一致していればOK、という流れです。)。手元の環境で実行する場合は、基本的にターミナルのことと同じだと思ってよいでしょう。たぶん。
入力を受け取るために、Rubyではgets
という関数を使います。これは「標準入力から1行読み取って、その文字列を返す」関数です。
そう、文字列なのです。このままでは計算ができません*17。
そこで整数に変換するto_i
という関数を使います[5.2.7]。
s = gets # 文字列を受け取る a = s.to_i # 整数に変換 puts(a * 10)
5
50
さっきのプログラムは以下のようにも書けます。むしろこちらの書き方の方が良いでしょう。
a = gets .to_i
puts(a * 10)
こんな感じの「関数合成」的な書き方を今後もしょっちゅうやっていくので一応覚えておいてください。*18
整数以外のデータの入力
文字列の場合はそのまま、実数の場合はto_f
を使用します[2.3.1]。
text = gets # 文字列そのまま d = gets.to_f # 文字列を受け取って実数に変換 puts(text, d)
hello 1.5
hello 1.5
空白区切りの入力
競プロでは、複数のデータが空白区切りで入力されるというのがよくあります(むしろ1つだけの方が珍しいです。簡単な問題では普通ですが)。このときの受け取り方を今から説明しますが、それには配列の知識が少し必要です。基礎プロ未履修者で「えっなにそれは(困惑)」という人はちょっと飛ばして結論だけ読んでも構いません。あるいは、基礎プロの教科書では4章、APG4bではN - 1.13で説明しているので、そちらを先に読むのも良いでしょう。
空白で分割する
split()
は、文字列を指定した文字で区切ってできる配列を返す関数です。
これを使って空白で分割します。
a = gets.split(" ") # 空白(" ")で分割 puts(a.to_s) # 説明のため文字列にして[4.4.2]出力
1 2 3
["1", "2", "3"]
これで文字列の配列になりました。あとはそれぞれの文字列を整数に変換するだけです。
…しかし、いちいちx = a[0].to_i, y = a[1].to_i, ...
というふうにするのは結構めんどくさいですし、それに後々「長さNの配列を受け取る」といった場面が出てくる以上、この方法では対応しきれません。(for文(後述)とかを使うという手もありますが…)
整数に変換
map
は配列と関数を受け取り、配列の各値に対しそれぞれに関数を適用してできる配列を返す関数です。…といってもよくわからないと思うので数式で説明します。を関数とするとき、
という感じになる、ということです*19。
これを使って配列のそれぞれの文字列を整数に変換します。
a = gets.split(" ") # 空白(" ")で分割 b = a.map do |x| x.to_i end puts(b.to_s) # 説明のため文字列にして出力
1 2 3
[1, 2, 3]
無事に整数になりました。…しかし、do |x| x.to_i end
の部分はいったいどういう意味なのでしょうか?
これはまぁ、「入力をx
とするとき、x.to_i
を返す関数」を表すと考えてください*20。x
はただの一時的な変数なので、例えば|y| y.to_i
としても結果は同じですし、あるいは|x| x.to_f
とすれば実数にすることもできます。なんなら|x| (x.to_i) * 2
とすれば2倍の整数になったりします。
実は以下のように書くこともできます。
b = a.map(&:to_i)
…何なんすかねこれ*21
結論
x,y,z = gets.split(" ").map(&:to_i) puts(x) puts(y) puts(z)
1 2 3
1 2 3
複数行の入力
競プロでは複数行にわたって入力されるのは日常茶飯事です。gets
は1行しか読み取らないので、入力の行数だけgets
を書く必要があります。
a,b = gets.split(" ").map(&:to_i) c = gets.to_i puts(a * b * c)
2 3 4
24
これらの入力受け取り用のコードはどこかにメモっておいてすぐコピペできるようにしておくと便利です*22。
問題
サンプルプログラムいる?
G - 1.06.if文・比較演算子・論理演算子
キーポイント
- if文
if 条件式1 then 処理1 elsif 条件式2 then 処理2 else 処理3 end
- 比較演算子
演算子 | 意味 |
---|---|
x == y | xとyは等しい |
x != y | xとyは等しくない |
x > y | xはyより大きい |
x < y | xはyより小さい |
x >= y | xはy以上 |
x <= y | xはy以下 |
- 論理演算子
演算子 | 意味 | 真になる時 |
---|---|---|
!(条件式) | 条件式の結果の反転 | 条件式が偽 |
条件式1 && 条件式2 | 条件式1が真 かつ 条件式2が真 | 条件式1と条件式2のどちらも真 |
条件式1 || 条件式2 | 条件式1が真 または 条件式2が真 | 条件式1と条件式2の少なくとも片方が真 |
ノート
x,y = gets.split(" ").map(&:to_i) if x == 10 then puts("xは10") if y == 10 then puts("yも10") end elsif x < 10 then puts("xは10より小さい") elsif x > 20 then puts("xは10より小さくなくて、20より大きい") elsif x == 15 then puts("xは10より小さくなくて、20より大きくなくて、15である") else puts("xは10より小さくなくて、20より大きくもなくて、15でもない") end if !(x == y) then puts("xとyは等しくない") elsif x == 10 && y == 10 then puts"xとyは10" elsif x == 0 || y == 0 then puts("xかyは0") end puts("終了")
メモ
- [2.2.2]と内容はほぼ同じです。
- C++では
else if
ですが、Rubyではelsif
であることに注意しましょう*23。 - これはただの余談で基礎プロ範囲外ですが、場合分けのための
case
という構文が存在するので気になる人は調べてみて下さい。大量のelsif
があるときはcase
の使用を検討すると良いでしょう。
問題
サンプルプログラム
a,op,b = gets.split(" ") a = a.to_i b = b.to_i if op == "+" then puts(a + b) # ここにプログラムを追記 end
H - 1.07.条件式の結果とbool型
キーポイント
- 条件式の結果は真のとき
true
に、偽のときfalse
になる - Rubyにはbool型に相当する概念が存在しない
ノート
puts(5 < 10) puts(5 > 10) if 1 then puts "hello" end if 0 then puts "world" end if nil then puts "メッセージはでないはずだよ" end
true false hello world
メモ
true
は真、false
は偽を表します[2.4]。- 条件式の結果は
true
またはfalse
になります。 - C++とは違い、if文の条件式に
0
を入れてもif文の中の処理が実行されます。 - たいていの言語にはbool型が存在しますが、Rubyには存在しません*24。
nil
は「何もないことを示す」値です[2.1.1]。if文の条件式にnil
を入れるとif文の中の処理は実行されません。
問題
プログラム
# 変数a, b, cにtrueまたはfalseを代入してAtCoderと出力されるようにする a = # true または false b = # true または false c = # true または false # ここから先は変更しないこと if a then print("At") else print("Yo") end if !(a) && b then print("Bo") elsif !(b) && c then print("Co") end if a && b && c then puts("foo!") elsif true && false then puts("yeah!") elsif !(a) || c then puts("der") end
I - 1.08.変数のスコープ
キーポイント
do end
で囲まれた部分をブロックという- 変数が使える範囲のことをスコープという
- 変数のスコープは「変数が宣言されてからそのブロックが終わるまで」
ノート
x = 5 if x == 5 then y = 10 puts(x + y) end puts(x) puts(y) # エラーは出ない loop do # 無限ループをする(基礎プロ範囲外) z = 10 puts(x + z) break # ループから抜ける(後述) end puts(x) #puts(z) # undefined local variable or method `z'
メモ
do end
で囲まれた部分をブロックといいます[2.3.2] (複数の入力を受け取るときのmap
で使っていたやつです。)。- ブロック内で宣言された変数はブロックの外では使えません。
- if文にはブロックが使われていないので、C++とは異なりエラーは出ません。……は?????????
- ちなみに、[12.4.1]にはC言語版のスコープの話が載っています。そちらも読んでみてください。
問題
A君が書いたプログラム
p = gets.to_i # パターン1 if p == 1 then price = gets.to_i end # パターン2 if p == 2 then text = gets.chomp # chompは改行を取り除く(基礎プロ範囲外) price = gets.to_i end n = gets.to_i puts(text + "!") # 文字列は+で連結できる[4.4.2] puts(price * n)
J - 1.09.複合代入演算子
キーポイント
ノート
x = 5 x += 1 + 2 puts(x) a = 5 a -= 2 puts(a) b = 3 b *= 1 + 2 puts(b) c = 4 c /= 2 puts(c) d = 5 d %= 2 puts(d)
8 3 9 2 1
メモ
- 「xをx + 1にする」よりも「xに1を足す」の方が直観的でわかりやすいでしょう。そのようなことを行えるのが複合代入演算子です。基礎プロの教科書ではRubyの範囲には説明がなく、登場するのはC言語になってからです[11.2.5]。
- 変数に1加えるインクリメントや変数から1引くデクリメントの機能はRubyには存在しません。
問題
サンプルプログラム
x,a,b = gets.split(" ").map(&:to_i) # 1.の出力 x += 1 puts(x) # ここにプログラムを追記
K - 1.10.while文
キーポイント
- while文を使うと繰り返し処理ができる
- 条件式が真のとき処理を繰り返す
ノート
i = 1 while i <= 5 do puts(i) i += 1 end
1 2 3 4 5
メモ
- [2.2.3]と内容はほぼ同じです。
問題
サンプルプログラム
a,b = gets.split(" ").map(&:to_i) # ここにプログラムを追記
L - 1.11.for文・break・continue
キーポイント
- for文は繰り返し処理でよくあるパターンをwhile文より短く書くための構文
- Rubyには
times
やstep
もある break
を使うとループを途中で抜けられるnext
を使うと後の処理を飛ばして次のループへ行ける
ノート
j = 0 while j < 3 do puts("Hello while: #{j}") # こうすると変数を埋め込める[2.1.1] j += 1 end for i in 0..3-1 do puts("Hello for: #{i}") end 3. times do |i| puts("Hello times: #{i}") end 0.step(3-1) do |i| puts("Hello step: #{i}") end puts() ############################## 10. times do |i| if i == 3 then puts("とばす") next elsif i == 7 then puts("ぬける") break end puts(i) end
Hello while: 0 Hello while: 1 Hello while: 2 Hello for: 0 Hello for: 1 Hello for: 2 Hello times: 0 Hello times: 1 Hello times: 2 Hello step: 0 Hello step: 1 Hello step: 2 0 1 2 とばす 4 5 6 ぬける
メモ
for
とtimes
は[2.3.2]に、step
は[3.1.6]に書いてあります。for i in 0..n do
とするとに、for i in 0...n do
(.
が3つ)とするとになります。基礎プロ範囲外なのでここでは.
が2つのものだけを使っています。break
をするとループを途中で抜けることができます[11.2.6] *25。next
をするとその後の処理を飛ばして、次のループに進みます[5.1.6]。C++を含む多くの言語では、continue
という名前になっています。- 実はRubyには、ループを回すときはwhileが一番速いという性質があるそうです。ぎりぎりでTLE*26になったときはwhile文に書き換えると間に合うかもしれません(まぁ、たいていの場合は遅いアルゴリズム(問題文からそのまま実装する、など)だからなので、まずはアルゴリズムの改良を考えましょう。)。
問題
サンプルプログラム
n = gets.to_i
a = gets.to_i
# ここにプログラムを追記
ヒント: /
の仕様
M - 1.12.文字列と文字
キーポイント
- Rubyでは文字列も文字も
String
型で扱う 文字列変数.length
で文字列の長さを取得できる文字列変数[i]
でi文字目にアクセスできる
ノート
s = "Hello" t = ", World!" puts(s + t) puts(s.length) puts(s[0]) puts(s[4]) puts(s[10] == nil) puts(t[-2]) u = "LOOOOL" count = 0 for i in 0..u.length - 1 do if u[i] == "O" then count += 1 end end puts(count)
Hello, World! 5 H o true d 4
メモ
- 文字列の存在自体は基礎プロでも触れられていますが、文字列に対しての関数は記述されていません。たぶん。
- しいて言うなら、
" "
の文字列内で#{ }
と記述すると、その部分が括弧の中の計算結果に置き換えられる[2.1.1]、くらいでしょうか。
- しいて言うなら、
文字列変数.length
で文字列の長さを取得できます(文字列変数.size
でも同じです)。文字列変数[i]
でi文字目にアクセスできます。0から始まることに注意してください*27。- 範囲外の文字にアクセスした場合、
nil
が返ってきます。 -i
を入れると、末尾から数えてi番目の文字にアクセスできます。
- 範囲外の文字にアクセスした場合、
- 他にも便利な関数が結構存在します。詳しくは公式のドキュメントを参照してください。class String (Ruby 3.2 リファレンスマニュアル)
each_char
とか結構便利そう
問題
サンプルプログラム
s = gets
# ここにプログラムを追記
N - 1.13.配列
キーポイント
- 配列は様々なデータの列を扱うことができる機能
Array.new(長さ, 初期値)
で配列を宣言できる
ノート
# 文字列との比較 str = "abcd" puts(str[0]) puts(str.size) arr = [25, 100, 64] puts(arr[0]) puts(arr.length) # 宣言方法 a1 = Array.new() a2 = Array.new(10,0) a3 = Array.new(10) puts(a1.to_s) puts(a2.to_s) puts(a3.to_s) # 配列の受け取り方 # 1行の場合 a = gets.split(" ").map(&:to_i) puts(a.to_s) # n行の場合 n = gets.to_i b = [] n.times do b.push(gets.to_i) end puts(b.to_s) b.pop puts(b.to_s)
3 1 4 1 5 5 9 2 6 5 3
a 4 25 3 [] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [nil, nil, nil, nil, nil, nil, nil, nil, nil, nil] [3, 1, 4, 1, 5] [9, 2, 6, 5, 3] [9, 2, 6, 5]
メモ
- 配列については[3.3]にだいたい書いてあります。宣言方法などもそちらを参照してください。
- 配列を宣言するときはできるだけ初期値を決めておきましょう。思わぬエラーが起こる可能性があります。
- Rubyでは配列は
Array
です。vectorではありません*28。 配列変数.push(値)
は配列末尾に値を追加し、逆に配列変数.pop
は末尾の値を取り除いて返します[4.3.3]。- 複数の入力を受け取るときに使った
gets.split(" ").map(&:to_i)
は実は配列です。1個の変数で受け取ると配列をそのままその変数に代入し、n個の変数だと配列の最初のn個が順に代入されます。a,b = gets.split(" ").map(&:to_i)
で3 1 4 1 5
と入力するとa == 3, b == 1
になり、残りの値は消えます(今知った)。
- 添字が0から始まったり[3.3.3]、範囲外の要素にアクセスすると
nil
が返ってきたり[3.3.3]、-i
を入れると末尾から数えてi番目の文字にアクセスできたりするのは文字列と同じです。むしろ文字列が配列と同じ、なのかもしれませんが*29。 - クソデカ配列を作るのは、やめようね!(n敗)
問題
サンプルプログラム
n = gets.to_i
ヒント:絶対値は.abs
で計算できます(例:(-3).abs -> 3
)。
O - 1.14.STLの関数
キーポイント
- メソッドを使うとプログラムのまとまった機能を簡単に使うことができる
- Rubyには組み込みライブラリという、様々なメソッドが入ってるものがありデフォルトで使える
- Rubyのメソッドは、ほとんどの場合メッセージ送信記法で使う
ノート
puts([10,5].min) puts([10,5].max) # swap a = 10 b = 5 a,b = b,a puts(a,b) arr1 = [1, 5, 3] arr1.reverse! puts(arr1.to_s) arr2 = [2, 5, 2, 1] arr2.sort! puts(arr2.to_s)
5 10 5 10 [3, 5, 1] [1, 2, 2, 5]
メモ
- これまでさんざん「関数」と呼んできましたが、Rubyでは正式にはメソッドと呼びます。でもめんどいのでここでは全部「関数」という一般的な名前にしています。
- 組み込みライブラリは様々な関数を提供します。特別な準備なく使用できます*30。
- メッセージ送信記法とは、
変数.メソッド名(引数)
みたいな形式のことです[9.2.2]。これはオブジェクト指向寄りの記法なのですが、なんとRubyでは整数も実数も文字列も配列もありとあらゆるすべてのものがオブジェクトであるという思い切った仕様になっているためにほとんどのメソッドがメッセージ送信記法になっています。受け入れましょう。 - Rubyでは、
max
、min
は配列に対してしか実装されていないっぽいです。めんどい。 - Rubyでは関数名の最後が
!
になっているものは、引数を破壊的に変更します*31。引数が勝手に変わったり、逆に変えようと思ったのに変わってなかったり、というミスに気をつけましょう。
a = [2, 5, 2, 1] b = a.sort puts(b.to_s) puts(a.to_s) # aは変わらない puts() c = a.sort! puts(c.to_s) puts(a.to_s) # aも変わっている
[1, 2, 2, 5] [2, 5, 2, 1] [1, 2, 2, 5] [1, 2, 2, 5]
- 関数については次項でもやります。
- 組み込みライブラリの詳細は公式のドキュメントを参照してください。library _builtin (Ruby 3.2 リファレンスマニュアル)
問題
サンプルプログラム
a,b,c = gets.split(" ").map(&:to_i)
P - 1.15.関数
キーポイント
- 関数を作成することを関数を定義するという
def 関数名(引数1の名前, 引数2の名前, ...) 処理 end
- 関数の返り値はreturn文を使って
return 返り値
で指定する - 関数の返り値が無い場合は、return文は
return
とだけ書くか、そもそも書かない - 関数の引数が不要な場合は定義と呼び出しで()だけを書く
- 処理がreturn文の行に到達した時点で関数の処理は終了する
- 引数に渡された値は基本的にコピーされる
ノート
def my_min(x,y) if x < y then return x else return y end end answer = my_min(10, 5) puts(answer) def hello(text) puts("Hello, " + text) end hello("Tom") hello("Ruby") def input x = gets.to_i return x end num = input() puts(num + 5) def add5(x) x += 5 puts(x) end y = 10 add5(y) puts(y)
10
5 Hello, Tom Hello, Ruby 15 15 10
メモ
- Rubyの関数についての説明は[1.2.2]に書いてあります。Rubyには変数に型がないので関数にも型はありません。
- なので、返り値の指定忘れもクソもありませんし、なんなら「この場合は整数、この場合は文字列を返す」なんてこともできます。
- ふつうの引数はコピーされます。が、配列を引数にした場合は配列の破壊的変更が起こり得ます。[3.3.4]を参照してください。
- 関数は宣言した行より後でしか呼び出せません。
- 関数のオーバーロード的なことってRubyでできるのかな…?クラスが異なればいけるか…?
数学の関数との違いについて
プログラミング言語の「関数」は、数学の「関数」とは違って、以下の2つの性質を持つことがあります。
- 同じ値を入力しても結果が同じであるとは限らない
- 他の変数やコンピュータ―自身など、外部に何かしらの変化をもたらすことがある
$global = 0 def f(x) return x * 2 end def g(x) $global += x puts("now: #{$global}") return $global end
上において、関数fは引数を2倍にして返すだけなので、数学の「関数」と何ら変わりません。
一方、関数gは数学の「関数」とは異なり、広域変数[4.3.2]global
に引数を加え、現在のglobal
の値を画面に出力し、そしてglobal
を返しています。これでは同じ値を入力しても結果が同じにならない可能性があります。
関数fのように「同じ入力に対し結果が常に同じで、かつ外部に何の変化も起こさない」性質を参照透過性と言います。逆に、関数gみたいに広域変数を変更したり、入力を受け取ったり出力したりするなどの変化を副作用と言います。…的な話が[4.3.2]に載っています。
Q:出力はともかく、入力も副作用なんですか?
A:だって常に同じ入力とは限らないし、何ならプログラムやコンピューターに何かしらの変化を起こす入力がされるかもしれないじゃんか*32
副作用を多用するとどこで何やっているのかわかりにくくなり、バグ修正とかがクッソめんどくさくなります。気を付けてください*33。
問題
A君が書いたプログラム
# 1人のテストの点数を表すリストから合計点を計算して返す関数 # 引数 scores: scores[i]にi番目のテストの点数が入っている # 返り値: 1人のテストの合計点 def sum(scores) # ここにプログラムを追記 end # 3人の合計点からプレゼントの予算を計算して出力する関数 # 引数 sum_a: A君のテストの合計点 # 引数 sum_b: B君のテストの合計点 # 引数 sum_c: C君のテストの合計点 # 返り値: なし def output(sum_a, sum_b, sum_c) # ここにプログラムを追記 end # ------------------- # ここから先は変更しない # ------------------- # 1行の整数が空白区切りになった入力を受け取って配列に入れて返す関数 # 引数: なし # 返り値: 受け取った入力の配列 def input arr = gets.split(" ").map(&:to_i) return arr end # 科目数Nを受け取る(受け取るだけ) n = gets.to_i # それぞれのテストの点数を受け取る a = input() b = input() c = input() # それぞれの合計点を計算 sum_A = sum(a); sum_B = sum(b); sum_C = sum(c) # プレゼントの予算を出力 output(sum_A, sum_B, sum_C)
1章終了
これで1章の範囲はすべて終わりです。お疲れさまでした。ぶっちゃけ基礎プロの範囲からやや逸脱してしまった感はありますが、これでだいたい競プロを始める準備はできたと思います。
期末試験:AtCoder Beginners Selectionを解いてみてください(全10問)(解説はググればでてくるのでここでは載せません)
そのほかの基礎プロの内容について
APG4b2章以降の内容のうち、基礎プロでも触れているものを紹介します。ぜひやってみてください。
- R - 2.01.ループの書き方と範囲for文 : 配列の
each
[3.3.3]や文字列のeach_char
はC++における範囲for文と同等の機能を持ちます。 - S - 2.02.多重ループ : [5.2.6]で触れられています。
- T - 2.03.多次元配列 : [5.2.1]で触れられています。
- U - 2.04.参照 : [3.3.1]で触れられています。
- V - 2.05.再帰関数 : [4.4]で触れられています。
- W - 2.06.計算量 : [8.2]で触れられています。
- AB - 3.04.構造体 : C言語の[14.2]で触れられています。また、Rubyでは構造体はありませんが、クラスというものがだいたい似たようなことをやっており、そちらは[9.2]で触れられています。
- AC - 3.05.ビット演算 : [7.3.2]で触れられています。
また、競プロでもしばしば出題される二分探索法(binary search method)というアルゴリズム*34や、動的計画法(Dynamic Programming)というアルゴリズム*35、ときどき使うことになるハッシュ表(Hash Table)というデータ構造*36について、それぞれ[11.3.2]、[12.3]、[14.3.4]で解説されています。
APG4bの後は…
ABCは基本的に毎週土曜か日曜のどっちかで開催されているので、とにかく参加しましょう。AtCoderにはレーティングがあり、これはコンテストで速く正解したり高得点を取ったりすることで上昇していきます*37。数をこなすことが上達への一番の近道です*38。
…とはいえ、ABCの時間以外でも競プロを練習したいときもあると思います。過去のABCの問題を解くこともできますが、あまりにも多すぎるので何をどれだけやればいいのかわからないでしょう*39。そこで以下の2つを紹介します。
競プロ典型90問は文字通り競プロにおける典型的なアルゴリズムの問題を90問集めた問題集です。
ただ初心者には難しい問題も多く含まれているため、まずは難易度★2の問題からやってみるのが良いでしょう。
また、アルゴ式というサービスは競プロで役立つ様々なアルゴリズムの練習問題を提供しています(AtCoderとは関係ありません)。
数学で例えるなら、競プロは多くが文章題などの応用問題であるのに対し、このアルゴ式では文章題を解くための基礎的な計算力を身に着ける問題ができるような感じです。「この問題はこのアルゴリズムを使えば解けるのか…練習したいな…」といった時にアルゴ式を利用すると良いでしょう。
終わりに
クッッッッッッッッッソ疲れた…Ⅲ類機シスのやることじゃねぇだろこれ…。
本家のC++でのあれこれをRubyではどう書くのか調べたり教科書のどこに記述されているかペラペラしたりで結構大変でした。
結論:標準入出力さえやれば基礎プロの知識で十分なんとかなる
さて、これで基礎プロ履修者ならすぐさま競プロを始められるようになったというわけだ…
もう「できない」なんて言い訳はさせませんよ…
オタク!競プロをやれ!
追記(2022/12/28)
競プロで上達したいならこの本がおすすめです。
競プロ系の書籍は多数存在しますが、とりあえずこの本を買っておけばだいたいの問題はカバーできると思います。
ちなみに自分は買ったけどまだ読んでません。
問題の解答例
- EX1
puts("こんにちは") puts("AtCoder")
- EX2
print("いつも") puts(2525) puts("AtCoderくん")
- EX3
puts( (100 * (100 + 1)) / 2 )
- EX4
seconds = 365 * 24 * 60 * 60 puts(seconds) # 1年は何秒か puts(seconds * 2) # 2年は何秒か puts(seconds * 5) # 5年は何秒か puts(seconds * 10) # 10年は何秒か
- EX5
a,b = gets.split(" ").map(&:to_i) puts(a + b)
- EX6
a,op,b = gets.split(" ") a = a.to_i b = b.to_i if op == "+" then puts(a + b) elsif op == "-" then puts(a - b) elsif op == "*" then puts(a * b) elsif op == "/" && b != 0 then puts(a / b) else puts("error") end
- EX7
# 変数a, b, cにtrueまたはfalseを代入してAtCoderと出力されるようにする a = true b = false c = true # ここから先は変更しないこと # (以下略)
- EX8
p = gets.to_i # パターン2 if p == 2 then text = gets.chomp puts(text + "!") end price = gets.to_i n = gets.to_i puts(price * n)
- EX9
x,a,b = gets.split(" ").map(&:to_i) # 1.の出力 x += 1 puts(x) # 2. x *= a + b puts(x) # 3. x *= x puts(x) # 4. x -= 1 puts(x)
- EX10
a,b = gets.split(" ").map(&:to_i) print("A:") i = 0 while i < a do print("]") i += 1 end puts() print("B:") i = 0 while i < b do print("]") i += 1 end puts()
- EX11
n = gets.to_i a = gets.to_i n.times do |i| op,b = gets.split(" ") b = b.to_i if op == "+" then a += b puts("#{i+1}:#{a}") elsif op == "-" then a -= b puts("#{i+1}:#{a}") elsif op == "*" then a *= b puts("#{i+1}:#{a}") elsif op == "/" then if b == 0 then puts("error") break elsif a < 0 then # 負のときの処理 a *= -1 a /= b a *= -1 puts("#{i+1}:#{a}") else a /= b puts("#{i+1}:#{a}") end end end
- EX12
s = gets.chomp ans = 1 for i in 0..s.length - 1 do a = s[i] if a == "+" then ans += 1 elsif a == "-" then ans -= 1 end end puts(ans)
- EX13
n = gets.to_i a = gets.split(" ").map(&:to_i) # 合計 s = 0 a.each do |x| s += x end # 平均 ave = s / n a.each do |x| puts((x - ave).abs) end
- EX14
a,b,c = gets.split(" ").map(&:to_i) max = [a,b,c].max min = [a,b,c].min puts(max - min)
- EX15
# 1人のテストの点数を表すリストから合計点を計算して返す関数 # 引数 scores: scores[i]にi番目のテストの点数が入っている # 返り値: 1人のテストの合計点 def sum(scores) s = 0 scores.each do |x| s += x end return s end # 3人の合計点からプレゼントの予算を計算して出力する関数 # 引数 sum_a: A君のテストの合計点 # 引数 sum_b: B君のテストの合計点 # 引数 sum_c: C君のテストの合計点 # 返り値: なし def output(sum_a, sum_b, sum_c) puts(sum_a * sum_b * sum_c) end # ------------------- # ここから先は変更しない # ------------------- # (以下略)
脚注
*1:具体的にはHaskellやJulia、Nimと戯れておりました…Ⅲ類の、よりによって機シスで…
*2:高校生のときにBASICをほんの少しかじったことがある程度でした。
*3:現在の僕が解けるのはD問題までです。コンテストごとに問題の難易度にブレがあるので、たいていはC問題が解けるか解けないかで時間切れになります。
*4:競プロをやっている人のこと。
*5:まぁ基礎プロの授業においてそこは本題ではないからなのだと思いますが。
*6:基礎プロよりも前、1年前期にやる授業。
*7:「高級アセンブリ言語」「自分の脚を簡単に撃ち抜ける言語」などと呼ばれています。お察しください。
*8:C言語の純粋強化版といったところの言語。様々な理由から競プロでよく使われている言語の一つであり、実質「公用語」みたいなものである。なお、「脚を撃ち抜くのは難しいが、撃ったら一撃で脚が吹き飛ぶ言語」なもよう。ちなみに基礎プロでC言語の環境構築ができたならC++も使えるようになる(「gcc ファイル名」のところを「g++ ファイル名」にするだけ。拡張子は.ccか.cppが主流)。
*9:AtCoderでのRubyのバージョンは現時点で2.7.1で少し古いですが、基礎プロ側の指示に従って最新版を普通にダウンロードしてください。とりあえずAPG4bを自分でやってみた範囲では特に問題はありませんでした。
*10:あと実際にやってみたらものすごく面倒だったというのもある。
*11:厳密には、標準出力(stdout)というところに出力します。手元の環境で実行する場合は、基本的にターミナルのことと同じだと思ってよいです。
*12:一部の言語では、ある部分のコメントを消すと正常に動かなくなる、といった現象が発生する…らしいです。
*13:3週間後にはもう記憶から抜けてるだろうからね
*15:一度値を決めた後にその値を変更すること。多くの言語では再代入できない変数を宣言することができます。一見不便に思えますが、変なところで勝手に値が変更されるのを防ぐ効果があります。「不変変数」や「イミュータブル変数」などで調べてみてください。
*16:standard inputの略
*17:たぶんこれが一番初心者がつまずきやすいポイントだと思います。私も別の言語で同様の現象に悩まされ、気づくのに結構時間がかかりました。というかダイレクトに受け取れるC++が珍しい方なのでは…。
*18:いやちょっと待てや普通関数と言ったら「hoge(x)みたいなやつやろがい何や「x.hoge」って…と思うかもしれませんが、慣れてください。それに、「to_i(gets)」よりも「gets .to_i」の方が「getsしてto_iする」みたいに自然に読めるので何をやっているのかわかりやすいし…
*19:このクッソ便利な関数は、元々は 関数型プログラミング言語[1.1.3]の方面で生み出されたものです。クッソ便利なので、最近のマルチパラダイムな(つまり手続き型でも関数型でもオブジェクト指向型でもいろいろできる)言語ではたいてい採用されています。
*20:「無名関数」とか「ラムダ式」とかで検索するとちょっと理解しやすくなるかもしれません。
*21:基礎の範囲を逸脱するのは自明なので解説はしません。
*22:エディタによっては補完機能があり、これを使うともっと楽になります。VSCodeなら「VSCode ユーザースニペット」とかで調べてみてください。
*23:他の言語では「elseif」だったり「elif」だったりもします。言語を変えたりするときは気をつけましょう。
*24:これはRubyの設計思想によるもの…だそうです。もっと知りたい人は自分で調べてください。
*25:教科書のRubyの範囲にも載っているはずなのですが、C言語の部分でしか見つけられませんでした…。見つけた方は教えてくださいな
*26:Time Limit Exceeded = 時間かかりすぎ
*27:特に「s[s.length]」みたいなミスをやらかしがちです(n敗)。気をつけましょう…
*28:少し調べたところ行列を扱うmatrixというライブラリにVectorという名前のクラスが存在するようです。もちろん基礎プロ範囲外です。
*29:プログラミング言語における文字/文字列の実装は、C++などの「文字型も文字列型も存在する」、Rubyなどの「文字型が存在せず長さ1の文字列で代用する」の他に、Haskellなどが採用する「文字列は文字の配列(の別名)である」という方式もあります。この方式だと配列のための関数をそっくりそのまま文字列に流用できるというメリットがあります。
*30:一部のライブラリは使うためにちょっとした準備が必要だったりします。基礎プロでは使っていないので解説はしません。
*31:「!」のついていない関数全てが破壊的に変更しないとは言っていない
*32:「時間だ、答えを聞こう」「「バルス!」」…冗談はさておき、「SQLインジェクション」っていうのがあってですね…。
*33:副作用をほぼ全く許容しない言語として純粋関数型言語Haskellがあります。関数型言語は(文や命令ではなく)関数を組み合わせることで様々な処理を行うプログラミング言語なのですが、その中でも参照透過性をもった関数のみを使い副作用を極力避けるようになっているのが純粋関数型言語です。(代表的な関数型言語としては他にScalaやF#などがあります。)またC/C++を置き換える目的で作られたRustは関数型言語の影響を受けているらしく、「そもそも自分の脚を撃ち抜けない」ようなとても安全な言語となっています。ただ、関数型言語はバグを起こさないように文法が非常に厳格なものとなっているせいで書きにくいこと、そもそも競プロが手続き型言語による実装をを前提にしていることなどから、あまり競プロ向きではありません…。でもHaskellは一度くらいやっておいた方が良いと思うよ。マジで。
*34:教科書では区間2分法という名前で紹介されていますが、競プロではこちらの名前が一般的です。
*35:実は全然ダイナミックでもプログラミングでもなかったりする。この名前になったのはちょっとした事情があったから…らしい。
*36:言語によっては連想配列や辞書と呼ばれていることもあります。
*37:レーティングには「色」があり、最初は灰色から始まり、その上は茶色、緑色、水色…で最上位が赤色です。まずは灰色脱出を目指しましょう。茶色になれば「最低限の実戦能力がある」みたいな扱いになります。
*38:参加回数が少ない人は、レーティングが低めに計算されるようになっているそうです。その意味でも参加回数を増やすのは重要です。
*39:自分は利用していませんが、AtCoder Problemsというサイトを利用すれば過去問の練習がしやすくなります。ここでは解説しません。