競プロ初めましての方へ~Paiza,Pythonを例として

はじめに

この記事は、いわゆる競プロにこれから取り組もうと考えている方に向けた記事です。筆者自身、当初は特有の考え方に戸惑ったため、競プロに初めましての方がスムーズに学習を開始できることに役立てられると幸いです。また、読者のレベル感の想定は、ある言語(特にPython)の入門を一通り何かで学んだことがあり、for文やif文、配列、変数、データ型等の基礎を知っている方が対象です。

競プロとは

そもそも競プロとは何らかの指定された問題を、計算機の力を利用したプログラミングで解こうとするものです。
・繰り返しや条件分岐などのアルゴリズム的な発想が鍛えられる
・配列などのデータ構造を活用する
・入力、処理、出力の仕様に合わせて実装する

これらの理解を深めることができます。いずれもプログラミングの根幹の考え方であり、非常に良い学びになると思います。日本で有名なサービスとしてはPaizaやAtcoderなどがあり、いずれもオンライン実行環境でゲーム感覚で楽しみながら取り組めます。また、良い成績を取れれば、就職活動で箔がつくことがありスムーズに選考に進める切符になります。さらに、エンジニアの就職活動におけるコーディングテストは、競プロと同様の考え方を問われることが多くこちらにも非常に役に立ちます。

実際に問題を見てみよう~初級編

競プロを理解するには実際に問題を見るのが早いでしょう。こちらでは例としてPaizaを取り上げます。以下のURLから実際にアカウントを作ってみると良いでしょう。

▼ホームページ
https://paiza.jp

用いる言語は、文法が分かりやすく学習コストの低いPythonがオススメです。
ここでは、練習問題として提供されているCランクのFizzBuzz問題を例に挙げます。

▼こちらのURLより問題を見ることができます。
https://paiza.jp/works/mondai/skillcheck_sample/fizz-buzz?language_uid=python3

問題

整数 N が入力として与えられます。

1からNまでの整数を1から順に表示してください。

ただし、表示しようとしている数値が、

・3の倍数かつ5の倍数のときには、"Fizz Buzz"
・3の倍数のときには、"Fizz"
・5の倍数のときには、"Buzz"

を数値の代わりに表示してください。

入力

入力は以下のフォーマットで与えられます。

N

N は1以上N以下の整数です。


入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。

出力

1からNまでの整数を1から順に表示してください。

ただし、表示しようとしている数値が、

・3の倍数かつ5の倍数のときには、"Fizz Buzz"
・3の倍数のときには、"Fizz"
・5の倍数のときには、"Buzz"

を数値の代わりに表示してください。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ N ≦ 100
・N は整数

入力例

20

出力例

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
Fizz Buzz
16
17
Fizz
19
Buzz

上記が問題の本体です。さて、どのようなコードを書けばよいのでしょうか？コードを書き始める前に頭の中でまずは、入力、処理、出力に分けて方針を考えます。

方針

①入力
今回の場合、シンプルに入力値をNという変数として受け取れば良さそうだ。

②処理(アルゴリズム)をどのように書くと良いのだろう？
ⅰ．まず、入力数字の数の分だけ、何らかの処理や出力を行うことから、For文で1~Nまでの数字を回せば良さそうだ。
ⅱ．各数字において、倍数かどうかを判定するには剰余演算子の%が使えそうだ。
倍数であるには、逆に割り算すると余りがゼロになるため。
ⅲ．条件分岐で上記の考え方に基づいて倍数かどうかを判定して出力を決めればよい。
ⅳ．ただし、3の倍数かつ5の倍数のように重複して判定されるものがあるので、If文の順序にも気を付ける必要がありそう。
※↑これらの発想が自然に出るまでには幾分か入門学習が必要かと思います。

③出力
今回の場合、各出力値は改行されて行ごとに出力されるので、上記の処理中にprint文を書くだけで済みそうだ。

上記の方針に基づいて解答を作っていきます。頭の整理と勉強のためにも、積極的にコメントアウトでメモを記入すると良いです。

解答例

# 入力を受け取る
# input()が入力されるもので、これをint型(整数型)としてNに代入
N = int(input())

# 1~Nまで各数字をif文で判定し、出力する
# 3かつ5の倍数(=つまり15の倍数)のときを最初に持ってくる必要がある。
# そうでないと、例えば15は3の倍数として判定されてしまうため。
for i in range(1, N+1):   
    if i % 15 == 0:
        print("Fizz Buzz")
    elif i % 3 == 0:
        print("Fizz")
    elif i % 5 == 0:
        print("Buzz")
    else:
        print(i)

Paizaの場合、上記のようにコードを書けたら、入力例が合っているかの動作確認や、自分で入力例を試せるようなテストを実行することができます。そして、ファイナルアンサーとして提出すると、任意の入力例とその出力が正解かどうかを試すために10問のテストケースが実行され、得点が与えられます。

実際に問題を解いてみよう~中級編

ここでは、練習問題として提供されているBランクの長テーブルのうなぎ屋を例に挙げます。

▼こちらのURLより問題を見ることができます。
https://paiza.jp/works/mondai/skillcheck_sample/long-table

問題

東京の下町に長テーブルで有名な老舗うなぎ屋がありました。

そのうなぎ屋にはとても大きい長テーブルがあり、テーブルの周りにn個の座席が配置されています。
座席には、時計回りに1, 2, …, nと番号が振られています。
座席はテーブルの周りに配置されているので、座席番号nの座席と1の座席は隣接しています。（下記図を参照の事）

問題続き

今、m個のグループの人達が座席に順番に座りに来ます。i番目(1≦i≦m)のグループの人数をa_i人とします。
彼らは、長テーブルに並んだ座席の内、ある連続するa_i個の座席に一斉に座ろうとします。

ただしお客さんは江戸っ子なので、それら座席のうち、いずれか一つでも既に先客に座られている座席があった場合、
一人も座らずにグループ全員で怒って帰ってしまいます。江戸っ子は気が早いんでぃ。

入力では、i番目のグループが座ろうとする連続した座席の位置は、整数b_iにより指定されます。
i番目のグループは、座席番号b_iの座席を始点として、そこから時計回りにa_i個分の座席に座ろうとします。

最後のグループが座りに来た後、無事に長テーブルの座席に着席出来ている人数を出力するプログラムを作成してください。

入力

入力はm+1行から成ります。
1行目にはn(座席数)とm(グループ数)が半角スペース区切りで入力されます。
i+1行目(1≦i≦m)には2個の整数a_i(グループの人数)とb_i(着席開始座席番号)が半角スペース区切りで入力されます。


入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。

出力

最後のグループが座りに来た後、無事に座席に着席出来ている人数を1行で出力してください。

条件

すべてのテストケースにおいて、入力される値は以下の条件を満たします。

1 ≦ n ≦ 100
1 ≦ m ≦ 100
1 ≦ a_i ≦ n
1 ≦ b_i ≦ n

入力例

6 3
3 2
1 6
2 5

出力例

4

上記が問題の本体です。Cランクの問題に比べるとかなり難易度が上がっているように見えると思います。どのようなコードを書けばよいのでしょうか？問題がやや込み入っているので、コードを書き始める前に問題文と入力例、出力の読解(=要約)から始めることにしましょう。

読解

①問題文
ⅰ．円形のテーブルの周りに椅子がある
ⅱ．グループの客が、指定の椅子からスタートして連続して座っていく
ⅲ．その中で先客が一人でも座っていた場合、グループ全員未着で帰宅する

②入力例
ⅰ．1行目はそれぞれ(座席数)と(グループ数)
ⅱ．2行見以降は、グループの数行分、(グループの人数)と(着席開始座席番号)がそれぞれ書かれている

③出力
着席できている人数を出力

上記のようにプログラムに関わる本質的な部分を抽出して整理します。さらに以下のように入力例を手元で簡単に追っていくと理解が深まる上に、実装するプログラムのイメージが湧きます。

入力例をなぞる

以下の入力例
6 3
3 2
1 6
2 5

座席数=6
グループ数=3

座席は以下のイメージ(本当は、右端と左端が繋がった円形)
座席→[空,空,空,空,空,空]

1グループ目は3人いて、座席番号2から座り始める。
→[空,満,満,満,空,空]

2グループ目は1人いて、座席番号6から座り始める。
→[空,満,満,満,空,満]

3グループ目は2人いて、座席番号5から座り始める。
しかし、6番目の椅子がすでに埋まっているので未着となる。
→[空,満,満,満,空,満]

これにて終了

つまり、着席数は「満」の数をカウントし、4人ということになる。

※もし座席番号が6を超えた場合、左端に戻って考える必要がある。
このようなときな剰余系を利用すると良さそう。7番目の座席は7%6=1として左端に戻ってくるため。

問題文を把握出来たらプログラムの実装を考えていきます。入力、処理、出力に分けて方針を考えます。

方針

①入力
今回の場合、1行目に基本情報で2行目以降は各グループ数だけ、各グループの情報という構成になっている。
このような場合、1行目とそれ以降で区別できると分かりやすい。
2行目以降は、各行ごとに複数の情報があるため、2次元配列で受け取ると良さそうだ。

②処理(アルゴリズム)をどのように書くと良いのだろう？
ⅰ．まず、各椅子の情報を1次元配列として扱おう。各要素Falseが空きで、Trueが着席者有としよう。
ⅱ．各グループ数だけ処理を行うので、ここにfor文を適用しよう
ⅲ．座席番号と椅子情報の配列のインデックスを対応させ、そのグループが座れるかどうかを判定しよう。
ここの判定をする際、またfor文を用い椅子を調べる必要がありそうだ。(つまり2重ループ)
座れたら椅子情報の配列の要素を更新しよう。
ⅳ．配列の右端にきたら左端に戻る(=円形のテーブルの周りに椅子がある構造)ので、
椅子の数の剰余系で考えれば良さそうだ。
※↑これらの発想が自然に出るまでには幾分か学習が必要かと思います。
例えば、1次元配列で椅子の空席情報を扱う発想を浮かべるにはデータ構造の理解が必要です。
また、データが周回するような場合は剰余系を利用すると便利であることも、経験が必要になってきます。

③出力
今回の場合、椅子情報の配列の要素でTrueの数をカウントし、それを出力すれば良さそうだ。

上記の方針に基づいて解答を作っていきます。頭の整理と勉強のためにも、積極的にコメントアウトでメモを記入すると良いです。入力を受け取る際、複数行に渡っていたり、各行にスペース区切りの入力がある場合などは各言語特有の方法で入力を受け取る必要があります。Python3で入力を受け取る様々な方法は以下にまとめています。

Pyhton3の標準入出力まとめ+応用

解答例

# 1行目の座席数、グループ数をそれぞれn,mに代入
# 右辺は、スペースで区切られた入力を分割し、int型で複数の変数に代入することを意味する。
# n=6, m=3
n, m = map(int, input().split())

# 各グループ情報を格納した2次元配列
# リスト内包表記を用い、各行ごとにスペース区切りの数値を取得
# G = [[6,3],[3,2],[1,6],[2,5]]
G = [list(map(int, input().split())) for i in range(m)] 

# 入力値を受け取れているか確認するデバッグ用
# print(n,m,G)

# 椅子配列 
# [False,False,False,False,False,False]
vacant = [False] * n

# グループ数だけfor文を回す
# enumerate関数を利用することで、i=index番号、v=要素となるので便利。
# 例えば1回目のループではi=0,v=[6,3]
for i,v in enumerate(G):

    # グループ人数
    number_of_people = v[0]
    
    # 着席開始座席番号
    numer_of_start_chair = v[1]
    
    # 座れるかどうか判定するフラグ
    can_sit = True
    
    # グループ人数分、座席をチェックする
    # pythonの配列の場合、indexが0始まりなので、入力値の座席番号との整合性に注意する
    for j in range(numer_of_start_chair, numer_of_start_chair + number_of_people):
        
        # もし、該当の座席(剰余系)が一つでもTrueなら(埋まっているなら)cat_sitをFalseにして終了(=内側のループを抜け出す)
        if vacant[(j-1) % n]:
            can_sit = False
            break

    # もしcan_sit=Trueなら(=座れるなら)、座席を着席とする(要素をTrueに変える)
    if can_sit:
        for j in range(numer_of_start_chair, numer_of_start_chair + number_of_people):
            vacant[(j-1) % n] = True
    
    # 適切に更新されているか確認するデバッグ用
    # print(vacant)

# vacant中のTrueの数をカウントする
ans = 0
for v in vacant:
    
    # もしvがTrueならansをインクリメント(1足す)
    if v:
        ans += 1

# 答えを出力する
print(ans)

模範解答は、2行目以降の入力値をそのままfor文の中で受け取りながら処理を書いています。私は、入力を一旦受け取ってからそれを処理にかけたほうが、分割出来て考えやすいと感じています。

また、本問題の解法は2重ループ構造となりました。ここで、よりレベルアップするなら計算量の概念も視野に入れる必要があります。もし、このループの入れ子構造が多くあればあるほど、計算量は指数関数的に増大し悪いアルゴリズムということになるためです。

適切に入力値を受け取れているか、また適切に処理が行われているかを確認するために、デバック用のprintを使って各処理を出力してみるのも良いでしょう。ただし、提出する際はデバック出力を間違えてそのままにしないように注意が必要です。

Trueのカウントやenumerate関数、リスト内包表記など、経験値がないと発想が出てこないような方法論があります。継続して学習を積み重ねることが大事です。

今回は練習問題でしたが、スキルチェック問題に正解することができたら、その問題のランクに昇格することができます。昇格できる基準としては、テストケース全問通過(大規模データにおける時間制限や境界値に注意) & 制限時間以内に回答という二つの条件を満たす必要があります。

おわりに

将来エンジニアを目指したい方や、競プロを通して学びを深めたい方にとって有意義なきっかけとなれれば幸いです。一緒に頑張りましょう！