【paiza問題集 解説】
paizaの森練習問題コンテスト過去問題セット11

a, b = map(int, input().split())
print(a + b)

さんすうのおじかんです。🤗

f = [1, 1]
for i in range(2, 10):
    f.append(f[i-1] + f[i-2])

print(*f, sep='\n')

こちらの解説 をご覧ください。

n = int(input())

result = 'No'
if n > 1 and (n == 2 or n % 2 == 1):
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            break
    else:
        result = 'Yes'

print(result)

• 1 は素数ではない
• 2 は素数
• 4 以上の偶数は 2 で割り切れる為、素数ではない

3 以上の奇数のみ素数が含まれます。プログラム例の 文では、

• 2 以上は素数の可能性あり
• 2 は素数
• 奇数は素数の可能性あり

なので、この条件に合った数のみ、素数かどうかを調べます。逆に 2 以外の偶数と 1 の時はスルーして No を出力します。

• 2 の場合

文は、3 から開始します。2 は何もせずそのまま 文を正常終了します。よって else が実行され、result は Yes となります。




• 3 〜 7 の奇数の場合

3 〜 $\sqrt{n}$ の間を調べるのですが、

$\sqrt{3}=1.7320508$
$\sqrt{5}=2.2360679$
$\sqrt{7}=2.6457513$
$\sqrt{9}=3$
$\sqrt{11}=3.316624$

このようにループが開始する range(3, 3+1) となるには n が 9 以上でなくてはいけません。7 までは 2 と同じ様に何もせずループをスルーして else が実行されます。 3 も 5 も 7 も都合よく素数ですね。😆




• 9 以上の場合

if n > 1 and (n == 2 or n % 2 == 1):
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            break
    else:
        result = 'Yes'

ループは 3 から 2 ずつステップしていきます。要するに奇数しか調べません。ループ中、n が i で割り切れたら素数ではないことになるので直ちに break し、最後まで割り切ることができなかったら else が実行されます。




あとは結果を画面に出力すれば完了です。

overtime = 0
for _ in range(30):
    m = int(input())
    
    overtime += m - 8

print(overtime)

x, y = map(int, input().split())
x = abs(x)
y = abs(y)
x_move = False
y_move = False

if x > y:
    x_move = True
else:
    y_move = True

cnt = 0
while x != 0 or y != 0:
    x = max(0, x - x_move)
    y = max(0, y - y_move)
    cnt += 1

    x_move = not x_move
    y_move = not y_move
    
print(cnt)

実際にロボットを動かして歩数を数えてみましょう。

x, y = map(int, input().split())
x = abs(x)
y = abs(y)

目的地の座標の絶対値をとります。これは (0, 0) を中心としてマイナス１歩もプラス１歩も同じ１歩なので、

●●●●●●●
●●●●●●●
●●●●●●●
●●●㊥●●●
●●●●●●●
●●●●●●●
●●●●●●●　同じ３歩

すべて座標位置を正数にし、この赤い範囲の領域を使って数えていきます。

x_move = False
y_move = False

if x > y:
    x_move = True
else:
    y_move = True

同じ動きが取れないということで、次に動く方向を x と y で交代しながら、または移動して止まってを繰り返しながら進んでいきます。x もしくは y 方向に「移動する」時は True、「移動しない」時は Falseとします。一歩動いたら向き変えるプログラムを後に行います。

x と y の先にどちらから一歩目を踏み出すか。これは x と y の数値が大きいほうから移動を開始します。

(x, y) = (2, 3) の時

㊥●●●
●●●●
●●●●
●●●●




y ファースト

㊥●●●
１２●●
●３４●
●●５●

x ファースト

㊥１●●
●２３●
●●45●
●●６●




(x, y) = (3, 1) の時

x ファースト

㊥１●●
●２34５

y ファースト

㊥●●●
１2345６




• x == y の時はどちらから踏み出しても同じ歩数になります。

㊥●●●
●●●●
●●●●
●●●●




(x, y) = (3, 3) の時

y ファースト

㊥●●●
１２●●
●３４●
●●56７

x ファースト

㊥１●●
●２３●
●●４56
●●●７





if x > y:
    x_move = True
else:
    y_move = True

x の数のほうが大きい場合は x 方向から動きます。y の数のほうが大きい場合は y 方向から動きます。x と y の数が同じ場合はどちらから動いてもよいのですが、条件式のとおり、y から動くこととします。

cnt = 0
while x != 0 or y != 0:
    x = max(0, x - x_move)
    y = max(0, y - y_move)
    cnt += 1

    x_move = not x_move
    y_move = not y_move

目的地から (0, 0) に向かって進んでいきます。スタート地点から目的地に向かっても結果的には歩数は同じですが、(0, 0) を目的地にしたほうがちょっとだけわかりやすいので。😄




ループは x = 0, y = 0 になるまで、つまり目的地の座標 (0, 0) に到達するまでです。

移動を開始します。
x と y には、それぞれ移動後の座標が入ります。 x - x_move と y - y_move は、現在の座標から x_move, y_move を引いた数です。(0, 0) に向かってどちらもマイナス方向へ移動します。

• x 方向に移動する時
  x_move = 1 (True)
  y_move = 0 (False)

• y 方向に移動する時
  x_move = 0 (False)
  y_move = 1 (True)

これを、

x_move = not x_move
y_move = not y_move

にて向きを変えながらジグザグに進んでいきます。

５●●●
４３●●
●２１●
●●🤖●

x_move, y_move = 0, 1 ← 初期値
↓ １歩目 (2, 2)
x_move, y_move = 1, 0
↓ ２歩目 (1, 2)
x_move, y_move = 0, 1
↓ ３歩目 (1, 1)
x_move, y_move = 1, 0
↓ ４歩目 (0, 1)
x_move, y_move = 0, 1
↓ ５歩目 (0, 0)
x_move, y_move = 1, 0

(ループを抜ける)




max(0, x - x_move)
max(0, y - y_move)

これは、座標がマイナスになった時には 0 にするという意味です。要するにその位置で「静止する」ということです。ヘタに動くと遠回りになったり、二方向だけで済む移動処理が四方向になってメンドクサイので、その場に留まったほうが効率的です。

• ✅👍

５43２●
●●１🤖

• (💢ﾟдﾟ)､ﾍﾟｯ

６３２●
５４１🤖




座標 (0, 0) に到着したらループを抜け、歩数を画面に出力して完了です。

数学的に高速処理する

• paiza 解答コード例

x, y = map(int, input().split())

if x != y:
    print(max(abs(x), abs(y)) * 2 - 1)
else:
    print(abs(x) * 2)

ちょいと例をお借りして解説します。

x != y の else になる条件式は x == y です。

(x, y) = (3, 3) の時

㊥●●●
●●●●
●●●●
●●●🤖

この場合の最短ルートは２通りしかありません。

６５●●
５44３●
●３22１
●●１🤖

なので、単純に abs(x) * 2 だけで求められます。

x != y の場合は、

(x, y) = (3, 1)

５43２●
●●１🤖

max(3, 1) * 2 - 1
↓
3 * 2 - 1 = 5




(x, y) = (2, 5)

９●●
78●●
56●●
４３●
●２１
●●🤖

max(2, 5) * 2 - 1
↓
5 * 2 - 1 = 9




x != y ならば、max(abs(x), abs(y)) * 2 - 1 だけで求められるようです。ｼﾗﾝｹﾄﾞ

x, y = map(int, input().split())
x = abs(x)
y = abs(y)

cnt = max(x, y) * 2 - (x != y)

print(cnt)

x != y と x == y は「１を引く」かの違いです。

１を引く条件を１を引く所に書くとこうなります。それだけ。😓

n = int(input())
s = input()

print(''.join(sorted(s)))

sorted() 関数を使ってソートすればいいだけなんです。👍
これは sorted() 関数がアルファベットに対応しているからということではなく、文字コード順にソートしているからです。

簡単に説明すると、a 〜 z の文字コードは 97 〜 122 です。この数値で昇順ソートをしています。

ですので、大文字が混ざった文字列、例えば、

s = 'paIzA'

をsorted() でソートすると、

AIapz

となります。A 〜 Z の文字コードは 65 〜 90 ですので、大文字の A 〜 Z が先になります。

n = int(input())
s = list(input())

for i in range(n-1):
    for j in range(n-1-i):
        if s[j] > s[j+1]:
            s[j], s[j+1] = s[j+1], s[j]

print(''.join(s))

文字を比較してバブルソートしています。文字は文字コードとして認識されていますので、単純に 'b'(98) > 'a'(97) の場合は True となり、'b' と 'a' の位置が交換されます。

• 例１

n, m = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(m)]

answers = [0] * n
for i in range(m):
    for j in range(n):
        answers[j] += c[i][j]

print('Yes' if m in answers else 'No')

• 例２

_, m = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(m)]

for answers in zip(*c):
    if all(answers):
        print('Yes')
        break
else:
    print('No')

• 例３

_, m = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(m)]

print('Yes' if any(all(answers) for answers in zip(*c)) else 'No')

横並びになっている列 n が問題数、行 m が生徒数です。問題にある『生徒が全員正答できた問題があるかどうか』を調べるには 列 が全て 1 になっているかどうかを調べます。ややこしいですね。😓

1 0 1
1 1 1
1 0 0

• 例１

n, m = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(m)]

answers = [0] * n
for i in range(m):
    for j in range(n):
        answers[j] += c[i][j]

print('Yes' if m in answers else 'No')

answers は、各問題の正答数です。各問題のうち、何人の生徒がその問題を正答したかをこのリストにカウントします。

i のループは、各生徒のテスト結果です。１問目から順に正解しているかをカウントしていきます。正答は 1、誤答は 0 となっていますので、この数値をそのままカウントに使います。

最終的に生徒数と同じ数値があれば全員正答している問題があるということになります。

• 例２

_, m = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(m)]

for answers in zip(*c):
    if all(answers):
        print('Yes')
        break
else:
    print('No')

転置を使っています。転置とは、行と列を入れ替えることです。

1 0 1
1 1 1
1 0 0
↓
1 1 1
0 1 0
1 1 0

転置するのは、縦並びのものを調べるより、横並びのものを調べるほうが簡単だからです。😉 その転置を行なっているのが、

zip(*c)

この関数です。二次元リストを展開して引数に与えるだけです。転置については、「２章 二次元リスト」で学習できます。




all() 関数には、転置した後の行リストを引数に与えています。要素の値は 1 と 0 だけで、それらはそのまま True と False として判定に使われます。Ｂランクなら今更かもしれませんが、このことについては「２章 bool型 True と False」の「Chatpter.4 - 『ある』か『ない』か」で学習できます。

• 例３

_, m = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(m)]

print('Yes' if any(all(answers) for answers in zip(*c)) else 'No')

内包表記に詰め込んで書きました。例２との違いは、 を any() 関数に変えたところです。

all()関数の内包表記で全員が正答した問題(True)が出現したら、any() 関数が True となり、 が True となります。

• paiza 解答コード例

n, m = map(int, input().split())
c = [[0] * n] * m
ans = [1] * n
for i in range(m):
    c[i] = list(map(int, input().split()))
    for j in range(n):
        ans[j] &= c[i][j]
        if i == m - 1:
            if ans[j] == 1:
                print("Yes")
                exit()
print("No")

動くプログラムにはなっていますが、Pythonプログラム的にはわかりにくいように感じます。😅

リスト c は、後の入力を保管するための二次元リストを作成し、初期化します。リスト ans は、真ん中辺りにある、

ans[j] &= c[i][j]

ここで論理演算(論理積)をする為に、[1] で初期化しています。最終的にこのリストに 1 が残っていれば画面に Yes が出力されることになっています。




外側の ループ i では、各生徒のテスト結果を入力し、チェックします。
内側の ループ j では、解答の正誤を論理積で論理演算して、１つの問題に対して全員が正答しているかをチェックしてます。このループ中に、

if i == m - 1:
    if ans[j] == 1:
        print("Yes")
        exit()

もしこれが最後の生徒のテスト結果だった時、全員が正答しているかどうかの判定を行います。言い方を変えると、i の最終ループの時に ans[j] が 1、つまり全員が正答しているのを見つけたら画面に Yes を出力します。

流れを詳しく見てみましょう。

1. 入力を受け取るリストを二次元リストで作成し、初期化する。(リスト c)
2. 全員が正答しているかどうかを判定する為の論理値を全て 1 で初期化する。
3. ループ i で生徒のテスト結果を受け取る。
4. ループ j で解答の正誤をチェックする。
5. 画面に Yes または No を出力する。

1. 入力を受け取るリストを二次元リストで作成し、初期化する。(リスト c)




c = [[0] * n] * m

３番で入力をこのリストに格納します。リストでまるごと格納してしまいますので、n の数だけ作る必要はありませんし、0 で初期化しなくても [] だけ作っておけば大丈夫です。

c = [[]] * m

2. 全員が正答しているかどうかを判定する為の論理値を全て 1 で初期化する。




ans = [1] * n

n = 3 の時でこれを作ると、

ans = [1, 1, 1]

となります。後の論理演算の論理積で、全員が正答した場合には最終的にどれかに 1 が残ります。

　1 1 1 ← 初期値
＆1 0 1
-----------------
　1 0 1
＆1 1 1
-----------------
　1 0 1
＆1 0 0
-----------------
　1 0 0

3. ループ i で生徒のテスト結果を受け取る。




for i in range(m):
    c[i] = list(map(int, input().split()))

生徒１人分のテスト結果を受け取り、リストにして c[i] の要素にまるごと格納します。リストをそのまま要素に新規格納しますので、コピーの問題には影響ありません。(アドレス渡しにはならない)

リストのコピーについては「２章 リスト型」の「Chatpter.4 - ぼくたちは代入ができない」で学習できます。

本来はコピーの問題を回避するために、

c = [[]] * m

を、

c = [[] for _ in range(m)]

と書くべきなのですが、要素をリストまるごと書き換えていますので c = [[]] * m という書き方でも問題ないわけです。でも誤動作防止の観点と、単純に紛らわしいのでちゃんと下の 文を使った書き方をしたほうが良いと私は思います。😅

4. ループ j で解答の正誤をチェックする。
5. 画面に Yes または No を出力する。




for j in range(n):
    ans[j] &= c[i][j]
    if i == m - 1:
        if ans[j] == 1:
            print("Yes")
            exit()
print("No")

生徒１人のテストの正誤チェックを論理積で演算します。その結果を ans[j] に格納していきます。「2.」のところに書いた筆算のような流れで二重ループで作られていきます。

そして i の最終ループ if i == m - 1: の時に 1 となったら if ans[j] == 1: 全員が正答していることになりますので、画面に Yes を出力してプログラムを強制終了します。exit()

そのまま二重ループを抜けた場合は、全員が正答した問題は無かったということになりますので、画面に No と出力してプログラムは正常終了します。

n, m = map(int, input().split())
c = [int(input().replace(' ', ''), 2) for _ in range(m)]

ans = 2**n - 1
for i in c:
    ans &= i

print('Yes' if ans != 0 else 'No')

(*^^)っ旦~~




int() - Python 標準ライブラリ

.replace() - ２章 文字列の操作を使いこなす機能一覧