paizaラーニング 「長テーブルのうなぎ屋」の考え方【初級】 (Python)

この記事はネタバレを含みます。
まずは自分で挑戦してみましょう

問題へのリンク：長テーブルのうなぎ屋

この問題は「paizaラーニング」問題集の問題のため、解説･解答の公開が許されています。
スキルチェックの問題は内容に関わる一切が公開を禁止されています。
気をつけましょう。

この記事で作成するコードは不完全です。
あくまで「考え方」と「考えをコードにする」ことが目的です。
「処理の最適化」までは考えないものとしています。

目次

0. 読み方
1. 問題理解
2. やること
3. 処理組み立て
4. 構築
5. 動作確認
6. おわりに

0. 読み方

　深く考えず書いたら「3. 処理組み立て」がえらく長くなりました。
　そのため前書きとして一つご忠告します。
　基礎的なことはわかってる！　という方は「3. 処理組み立て」は飛ばしていいと思います。かなーり基礎的なことから触れています。
　レベルとして目安は「2. やること」を読んで、もう頭にソースコードがふわふわと浮かんでくるなら「3. 処理組み立て」は読んでも面白くないと思います。
　2 → 4と読んで、「なんだこれ？」となったら、その項目だけ3の該当箇所を読めばいいと思います。（飛ばして読んだ場合「おさらい」の中身がメインになると思います）。
　また、そもそもとしてこの記事のターゲットは「わからなかった人」としています。わかってる人は最後のコードだけさらっと見て、筆者を鼻で笑う程度にしてください。
　また、ページ内ジャンプを実装するため、ナンバリングがぐちゃぐちゃになりました。申し訳ない。

1. 問題理解

　プログラムを作るのに「うなぎ屋」だの「江戸っ子」だのは必要ないです。何が必要かを判断し、単純な形にできるところは単純にして考えます。

　　最終的に必要な情報 ＝ 椅子に座っているお客さんの人数

　では椅子に座っている人数はどうすれば分かるか？
　国語･算数の問題です、文章から以下のことが読み取れます。
　　①椅子はN個、ひとつのテーブルの周りに置かれている
　　②客はグループ毎に案内される
　　③グループは案内された場所に時計回りに順番に座る
　　④座ろうとした場所に先客がいたら、その人は座れない
　　⑤グループで1人でも座れなかったら、グループ全員が即帰る

　こんなところでしょうか。
　で、難しいのは”テーブルの周りに置かれている”ところでしょうか。円形で周りをグルグル回る処理とは…よく分かりません。
　なので、こう考えてください。1からNの椅子は四角いテーブルの1辺に1列で並んでいると。
　そうすると、朧気ながら見えてくるはずです、配列という文字が…

　簡略化した考えでも「隣である」ことは、「そのように認識していれば」変わっていません。
　プログラミングでは「こう考えれば同じこと」という発想が大事です。

※あ、図が反時計回りになってる...ゴメンゴ(　´_ゝ｀)

2. やること

　paizaの問題に限って言えば、やることは大きく3つです。
　　1.入力を受け取る
　　2.処理をする
　　3.出力する
　時にはそれぞれが重なったり1つにまとまったりしますが、本筋は変わりません。
　この3つを問題に合わせて細分化していきます。

　まず入力を受け取ります。入力では以下のものが来ることがわかています。

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

　2行目以降は何行来るのかはこの時点ではわからないので、最初に1行目のn, mだけを受け取ります。
　やること1：n, m を受け取る

　次は、まだ入力が残っているので、それを受け取らないといけません。
　mを受け取ったのでこれで何行来るのか把握できました。繰り返し処理で各グループの人数・座る位置を受け取ります。
　やること2：m回の繰り返しを行う
　やること3：繰り返しの中でa_i, b_i を受け取る

　さてこれで全部の入力を受け取りました。では処理を考えます。
　グループの数はmですので、これもまた繰り返しを使います。
　やること4：m回の繰り返しを行う

　そして座席に着席できるかチェックして、全員が座れるなら座ってもらい、座れない人がいたら特に何もしません（勝手に帰るだけ）。
　ここでポイントとして、座ってもらえたらそれを記録していかないといけません。次のグループでのチェックができないためです。
　やること5-0：事前に着席結果を記録するものを作る
　やること5-1：全員が座れるかチェック
　やること5-2：座れたら着席済みの席を記録

　5-1について少し深堀します。
　座れるかのチェックでは何をするかというと、グループの一人一人について着席予定の椅子に人がいないか確認します。一人一人ということはこれもまた繰り返し処理です。全部が空席だった時だけ成功です。逆に言えば途中一人でも座れなかったら失敗です。
　やること5-1-1：a_i回の繰り返しを行う
　やること5-1-2：着席結果の記録から着席予定の場所に人がいるか確認する
　やること5-1-3：全員が座れる状態なら成功

　全グループの案内を繰り返し終わったら、処理は終了です。
　取っておいた記録から座った人数をカウントして出力します。
　やること6-1：記録内容から着席済みの席カウントする
　やること6-2：標準出力に表示

　以上です。
　最後にもう一度やることをおさらいしておきます。

　やること1：n, m を受け取る
　やること2：m回の繰り返しを行う
　やること3：繰り返しの中でa_i, b_i を受け取る
　やること4：m回の繰り返しを行う
　やること5-0：事前に着席結果を記録するものを作る
　やること5-1：全員が座れるかチェック
　やること5-1-1：a_i回の繰り返しを行う
　やること5-1-2：着席結果の記録から着席予定の席に人がいるか確認する
　やること5-1-3：全員が座れる状態なら成功
　やること5-2：座れたら着席済みの席を記録
　やること6-1：記録内容から着席済みの席カウントする
　やること6-2：標準出力に表示

☆★ 完璧に把握した、４に飛ぶ ★☆

3. 処理の組み立て

　やることもわかったので、ここから処理を考えていきます。
　Pythonで記載していきます。

3-1. やること1：n、mを受け取る

　n, mは1行にまとまって空白区切りの数字でやってきます。
　数字ではありますが受け取った瞬間は”文字列”として受け取っている状態のため、数値型に変換してから受け取ります。

n, m = ( int( x ) for x in input().split() )

　input() で標準入力を見て1行を持ってきます。この時は文字列です。
　split() で文字列を分割します。()の中を空にするとデフォルト値として空白で区切ってくれます。この時もまだ文字列ですが、分割したことで”文字列の配列”になっています。
　for x in 配列 で配列の中身を一つ一つ取り出してxに入れています。つまりxもまだ文字列です。
　( int(x) for ～ ) で文字列だったxを数値に変えるint()を使います。外側の()はジェネレータというものを作っています、なんか便利なやつぐらいの認識でいいです。
　n, m = ～ 変数に値を格納します。～の部分が配列など複数要素を持つ値で、左辺の変数の個数と要素の数が一致していれば、それぞれの要素を変数に入れてくれます。

3-X. 整理

　　やること2：m回の繰り返しを行う
　　やること3：繰り返しの中でa_i, b_i を受け取る
　　やること4：m回の繰り返しを行う
　　やること5：繰り返しの中でなんかいろいろ

　ここで一旦やることを振り返ってみます。「m回の繰り返し」が2回出てきますが、実はこれ、まとめることができます。
　なぜかといえば「やること5」の中で使う情報は「着席の記録」「iグループ目の人数」「iグループ目の座る位置」なので、全部を持っておく必要はないです。
　つまりは

　　やること2 & 4：m回の繰り返しを行う
　　やること3：繰り返しの中でa_i, b_i を受け取る
　　やること5：繰り返しの中でなんかいろいろ
　と読み替えることができます。
　では繰り返しを書こう・・と思いきや、もう一つ見直す部分があります。

　　やること5-0：事前に着席結果を記録するものを作る

　プログラムには「スコープ」という考えがあり、下部の処理が勝手に作ったものは上の処理・横の処理からは見えない、となっています。

※追記
Pythonでは図の場合はエラーにならないそうです。
ifやforの場合は「処理が通過していれば定義され抜けた後も保存される。通過しなかった場合は定義が発生していないので未定義でエラー。」だそうです。
Javaのつもりで書いてしまいました、申し訳ありません。

　なので繰り返しの中で共有して使いたい「着席結果を記録するモノ」を、繰り返しに入る前に作っておく必要があります。

3-2. やること5-0：事前に着席結果を記録するものを作る

　作るものは↓です。

　赤枠部分がメモできるようになっていればいいです。ここでは人がいない状態を'0'、人が座っている状態を'1'として記録することとします。（自分がわかりやすいように設定していいです。）
　図ではMax14になってますが、プログラムでは椅子の総数は n で渡されています。

chair = [0] * n

　[初期値] * 要素の数 ですべての要素に初期値を入れた状態の配列が作れます。
　ついでにもう一つ変数を用意します。最後に出すのは座っている人の合計人数で、座席の着席状態ではありません。数字だけ集計するための変数を作ります。

result = 0

3-3. やること2、4：m回の繰り返しを行う

　繰り返しを表現します。forを使うのが一般的です。

for _ in range( m ):
    #～ forの中
    #～ forの中
    #～ forの中
#～ forの外

　range(数値) で指定した数の要素数を持つ配列が入手できます。
　要素は0から始まり指定した数値の手前までの数値が入っています。
　range(3) なら [ 0, 1, 2 ] が入手できます。
　for 変数 in 配列 で配列の中身を個別に取り出せることは前述しました。ここでは変数に _ (アンダースコア)を使っています。これには特別な意味があり、「とってきた値そのものは使わないよ」と表現しています。
　for ～: と:(コロン)を付けたことにより「次からの行がforによって管理される」という表現になります。
　範囲は「次の行のインデントが保たれている間」になります。Pythonのインデントは意味づけがされているので誤ってスペース1個消しただけでエラー（もしくは予期せぬ動き）になります。気を付けましょう。

3-4. やること3：繰り返しの中でa_i、b_iを受け取る

　これは「やること1」と同じですのでさらっと。

g, s = ( int( x ) for x in input().split() )

　ここの変数g, sは繰り返し毎に新しいものを取ってくるため、繰り返しの中で定義して大丈夫です。gにa_i、sにb_iが入っています。

3-5. やること5-1：全員が座れるかチェック

　チェックを始める前に準備を入れます。
　次から繰り返しが始まりますが、一度繰り返しに入ってしまうと相互の連携が取れなくなります。
　座れるかどうかの最終結果がわかる変数を作っておきます。この値が最後までTrueだったらこのグループは座ることができます。

flg = True

3-6. やること5-1-1：a_i回の繰り返しを行う

　座席のチェックのため、グループの人数で繰り返し処理します。
　先ほども繰り返しが出ましたが、一つ異なる点があります。
　図を見て動きをイメージしてください。

　例えば座席の番号が7の場所に案内されたら、そのグループは7,8,9,...と順番に座れるかを確認します。そのためにはまず7,8,9,...の番号全部を入手しないといけません。今現在渡されているのは最初の番号7と人数だけです。
　そこで、7を基準に相対位置を考えると、図のように0,1,2,...という並びになっています。先ほどの range(数値) が有効活用できます。
　そのため、今度のforはこう書きます。

for i in range(g):

これでiに「案内位置からの相対位置」が入るようになります。

3-7. やること5-1-2：着席結果の記録から着席予定の席に人がいるか確認する

　ようやく実際に人がいるか確認していきます。
　記録処理としての登場はまだですが、確認後に着席状態を記録している変数がありました。その値がどうなっているか確認しましょう。

index = (s + i - 1) % n
if chair[index] == 1:
    #～ if判定が真だった時に入れる
    flg = False
else: # 判定が偽だった場合の処理、今回は不要
    #～ if判定が偽だった時に入れる、今回は不要
    #～ if判定が偽だった時に入れる、今回は不要
#～ ifを抜けた後

　s + i - 1で記録用に作った配列での参照場所を計算しています。
　ん？-1ってなんだ？と思いますね。実はプログラミングの世界ではイメージとずれてしまう部分があります。
　それは配列の番号が0始まりであることです。

　つまり
　　arr = [ 5, 2, 8　] という配列があったとすると
　　arr[0] => 5
　　arr[1] => 2
　　arr[2] => 8
　というように値が取れてきます。
　座席の番号は1から順番につけられているので、配列から取り出すときは番号としては1ずれるのです。
　(数値) % n は何をしているのかというと、最後の番号nから1につながるようにmod計算を入れています。
　modとは何かというと”割り算の余り”のことです。
　例えば「5 ÷ 2 = 2 余り 1」なので、「5 mod 2 = 1」となります。このmodをプログラミングでは%で表しています。
　なんでmodなんかが出てきたかというと、「余り」が「nをこえたら1から再出発」と同じ意味になるからです。

※追記：10を超えていない場合はmod計算しても値が"変わらない"ことも注目です。
例）7 ÷ 10 ＝ 0 余り 7

　長くなりましたが
　index = (s + i -1) % n によって座席の記録用に作った配列の正しい位置を入手しています。わかりやすいように変数に入れておきます。
　if chair[index] == 1: で配列の記録が1と等しいかを判定しています、1はその席に人が座っている場合の数字でした。つまり「その席に人がいたらifの中に入るよ」という意味になります。
　flg = False は座ってる人がいたときのみ行われる処理です、ここで値をTrue(座れる)からFalse(座れない)に変更します。
　else: はifの条件にあわなかった場合の処理ですが、「座れるなら次の人の確認に進む」ため、何も処理しなくていいです。
　逆に「座れるからflg = Trueにしよう」なんてしてしまうと、座れなかった時の確認結果が上書きされるのでやってはいけません。

3-8. やること5-1-3：全員が座れる状態なら成功

　「やること5-1-1」で作った繰り返しが終われば、グループ全員の座れるかチェックが完了したことになります。
　for を抜けた後にflgの値を確認します。

if flg:
    # 全員が座れる時の処理

　値の確認ですが、記号==を使わなくても大丈夫です。理由はflgに使ったデータ型にあります。
　bool型といいif文の判定に使われる真偽値を表します。判定結果が真のことをTrue、偽のことをFalseという値で表しています。これは文字列や変数ではなく”値そのもの”です。
　変数flgには「判定結果そのもの」が入っているので、ifに直接読み込んでもらうことができます。

3-9. やること5-2：座れたら着席済みの席を記録

　「やること5-1-3」のifの中に着席に成功したグループの処理を書きます。
　つまり「着席結果の記録」を「新たに今チェックしたグループが座った状態」に更新ます。
　もう一度「やること5-1-1」の繰り返しと同じものを作ります。さらに「やること5-1-2」の確認処理を、今度は更新処理としてアレンジします。

for i in range(g):
    index = (s + i - 1) % n
    chair[index] = 1

　すでに確認済みのため、ただただ着席完了(=1)に更新していきます。

3-10. やること6-1：記録内容から着席済みの席をカウントする

　着席済みの人数のカウントですが、記録した変数があるのでこれを全部見渡せば人数はわかります。
　でも、めんどくさいです。嫌だやりたくない、そう感じざるを得ない。全くの無知識でこの感覚になったなら、あなたはプログラミング向いているかもしれません。
　「着席する毎に」「グループの人数＝着席した人数」がわかっているのですから、座ったタイミングでカウントアップしていけば人数がわかりますね？
　そういえばまだ使ってない変数を最初に作りましたね、ここで使います。

result += g

　+= は”インクリメント”という表現で、次の2行は同じ処理になります。
　　num = num + 3
　　num += 3
　はいわかりづらい、どういうことかといえば「現在のnum(変数)に+3を処理して”更新する”」という記号です。その変数は使いまわしたいけど値は随時更新していきたい、そういう感じです。

3-11. やること6-2：標準出力に表示

　...ついに...戦いは...終わった...。
　集計した人数を標準出力に表示します。

print(result)

　print(表示したいもの) でPython君は標準出力にんべって出してくれます。
　引数に表示したいものだけを入れると改行を追加して出してくれます。「指定してねーのに勝手に出すなや！」なんて言わないでください。

4. 構築

　終わったと思った？惜しい残念、まだ完成ではないです（ほぼ終わってますが）。
　今はやりたいことをPythonで書き並べただけです。これをちゃんと動くように組み立ててあげないといけません。
　途中で説明したようにPythonはインデントで処理範囲を判断しています。
　この記事ではここまでわざとできるだけインデントを書かないようにバラバラに説明してきました。
　これらの処理を「適切に」並べていく必要があります。

　長い説明で頭が混乱していると思いますが、もう一度おさらいしてみましょう。
　...もういい？了解です、振り返りたい人だけどうぞ。

おさらい

**やること1：n, m を受け取る** [3の説明を見る](#3-1-やること1nmを受け取る)

n, m = ( int( x ) for x in input().split() )

やること5-0：事前に着席結果を記録するものを作る
3の説明を見る

chair = [0] * n

result = 0

やること2 & 4：m回の繰り返しを行う
3の説明を見る

for _ in range( m ):
    #～ forの中
    #～ forの中
    #～ forの中
#～ forの外

やること3：繰り返しの中でa_i, b_iを受け取る
3の説明を見る

g, s = ( int( x ) for x in input().split() )

やること5-1：全員が座れるかチェック
3の説明を見る

flg = True

やること5-1-1：a_i回の繰り返しを行う
3の説明を見る

for i in range(g):

やること5-1-2：着席結果の記録から着席予定の席に人がいるか確認する
3の説明を見る

index = (s + i - 1) % n
if chair[index] == 1:
    #～ if判定が真だった時に入れる
    flg = False
else: # 判定が偽だった場合の処理、今回は不要
    #～ if判定が偽だった時に入れる、今回は不要
    #～ if判定が偽だった時に入れる、今回は不要
#～ ifを抜けた後

やること5-1-3：全員が座れる状態なら成功
3の説明を見る

if flg:
    # 全員が座れる時の処理

やること5-2：座れたら着席済みの席を記録
3の説明を見る

for i in range(g):
    index = (s + i - 1) % n
    chair[index] = 1

やること6-1： 記録内容から 着席済みの席をカウントする
3の説明を見る

result += g

やること6-2：標準出力に表示
3の説明を見る

print(result)

　はい、長かったですが今までのことをちゃんと組み上げたら終わりです。
　次が組みあがったものになります。

完成コード

# 処理実装部
def main():

## ↓もし動かすだけならここからでいい↓ ##
## これだけにするときはインデントに気を付けて ##

    # input取得
    n, m = ( int( x ) for x in input().split() )

    # 変数定義
    chair = [0] * n
    result = 0

    # グループ単位繰り返し開始
    for _ in range( m ):
        # グループ情報取得
        g, s = ( int( x ) for x in input().split() )

        # チェック結果変数
        flg = True

        # チェック開始
        for i in range( g ):
            index = ( s + i - 1 ) % n
            if chair[index] == 1:
                # 席に人がいたら更新
                flg = False

        # チェック結果確認
        if flg:
            # 座れる場合のみ処理
            for i in range( g ):
                index = ( s + i - 1 ) % n
                chair[index] = 1
            result += g

    # 結果表示
    print( result )

## これだけにするときはインデントに気を付けて ##
## ↑もし動かすだけならここまででいい↑ ##

# main処理呼出部
if __name__ == '__main__':
    main()

　以上で本当に完成です。

5. 動作確認

　では動くのを確認します。

　入力例1

　入力例2

　よさそうですね。
　ではpaizaラーニングに投げてみます。

　クリアです。

6. おわりに

　冒頭で注意書きしたように、実はこの処理は提出コードとしては質が悪いものです。
　なぜかといえば無駄があるからです。それは座れるかのチェックの際に「座れない人がいることが分かった時点で帰る」という条件を使えていないためです。
　今回の問題では別に全探査してもそれほど差は出ないですが、Aランク・Sランクでは無駄なことを処理していると時間制限に引っ掛かり、出るはずの出力結果が正解でもタイムオーバーで×になります。

とある男の敗退結果

おそらく最終的な結果はあいますが、あまりにも無駄が多く処理に時間がかかる。
言語はJavaのため1回の処理の制限時間は各5秒（各言語の制限時間 ※Time limit欄を参照）。

　ここで書いた処理はあくまで「考えたことをトレースした」処理です。
　いったんそれでも大丈夫ですが、まだゴールは先にあるということだけは、忘れないでください。

　ページ内ジャンプを実装するため、ナンバリングがぐちゃぐちゃになりました。申し訳ない。

おまけコード

これは解説しません。

# coding: UTF-8
ch = []

def main():
    global ch
    n, m = ( int( x ) for x in input().split() )
    r = 0
    ch =[False] * n

    for i in range(m):
        g, s = ( int( x ) for x in input().split() )
        if (check(n, g, s - 1)):
            r += g
    print(r)

def check(n, g, s):
    global ch
    if (g == 0):
        return True
    if (ch[s % n]):
        return False
    if (check(n, g - 1, s + 1)):
        ch[s % n] = True
        return True
    return False

if __name__ == "__main__":
    main()