PythonでJOI難易度4を埋める

はじめに

Python(PyPy)を使って、JOI難易度4の問題を解きます。問題と難易度はこのサイトを参照しています。

F - 通学経路

考えたこと
場合の数で習う

みたいな図をlistで実装して解きました。

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

def solver(s,t,cons):
    m = [[0] * s for _ in range(t)] #上で説明したlist
    for i in range(s): #横の端は1で固定
        for con in cons:
            if con[0] == i + 1 and con[1] == 1: #工事中の交差点が端にあった場合の処理
                break
        else:
            m[0][i] = 1
            continue
        break

    for i in range(t): #同様に縦も
        for con in cons:
            if con[0] == 1 and con[1] == i + 1:
                break
        else:
            m[i][0] = 1
            continue
        break

    for i in range(1,t):
        for j in range(1,s):
            flag = False
            for con in cons:
                if con[0] == j + 1 and con[1] == i + 1: #終了地点
                    flag = True
                    break
            if flag:
                continue
            m[i][j] = m[i][j-1] + m[i-1][j]
    return m[-1][-1] #ゴールに書いてある数字が答え
print(solver(a,b,c))

flagの配置がとても汚い

A - 最大の和

考えたこと
毎回sumする時間はないので、累積和を使う。

n, k = map(int,input().split())
a = [int(input()) for _ in range(n)]

sums = [0]
for i in range(n):
    sums.append(sums[-1]+a[i])

ans = sums[k]
for i in range(k,n+1):
    ans = max(sums[i]-sums[i-k],ans)
print(ans)

C - カードゲーム

考えたこと
ゲーム系の問題は苦手です。シミュレーションしました。

n = int(input())
taro = [int(input()) for _ in range(n)]

taro.sort()
hana = []
for i in range(1,2*n+1): #重複はないので、taroが持っていないカードはhanaが持っている
    if i not in taro:
        hana.append(i)

m = taro.pop(0)
for _ in range(2*n):
    for i in range(len(hana)): #出せるカードの最小値を調べる
        if hana[i] > m:
            m = hana.pop(i)
            break
    else:
        m = 0
    for i in range(len(taro)): #出せるカードの最小値を調べる
        if taro[i] > m:
            m = taro.pop(i)
            break
    else:
        m = 0
    if len(hana) == 0 or len(taro) == 0: #どちらかが0になったら終了
        break

print(len(hana)) #最後の枚数
print(len(taro)) #最後の枚数

C - パーティー

考えたこと
自分と$n$人の友達の距離(何人の友達を経由するか)をまとめたlistを作り2以下の人数をカウント

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

d = [0] * n
for i in range(m): #友達(距離1)を調べる
    if f[i][0] == 1:
        d[f[i][1]-1] = 1

for i in range(m): #友達の友達(距離2)を調べる
    if d[f[i][0]-1] == 1:
        if d[f[i][1]-1] == 0:
            d[f[i][1]-1] = 2 #友達の友達は距離2
    elif d[f[i][1]-1] == 1:
        if d[f[i][0]-1] == 0:
            d[f[i][0]-1] = 2 #友達の友達は距離2

ans = d.count(1) + d.count(2) - 1

print(max(0,ans))

C - タイル (Tile)

考えたこと
左右上下のどの縁からの距離が近いを計算して、それを3で割った余りで処理します。
色は一番近い縁から順に塗られていくので、それぞれのマスで場合分けする必要があります。

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

for i in range(k):
    x1 = ab[i][0]-1
    x2 = n - ab[i][0]
    y1 = ab[i][1]-1
    y2 = n - ab[i][1]
    m = min(x1,x2,y1,y2) % 3
    if m == 0:
        print(1)
    if m == 1:
        print(2)
    if m == 2:
        print(3)

C - 看板 (Signboard)

考えたこと
対象の文字を数えてありえる組み合わせを全パターン調べようとすると面倒なので、先に距離を決めてシミュレーションします。

n = int(input())
s = input()
plate = [input() for _ in range(n)]

ans = 0
for i in range(n):
    p = plate[i]
    start =[]
    check = False

    for k in range(len(p)):
        if p[k] == s[0]: #スタート地点を調べる
            start.append(k)

    for k in range(1,len(p)+1): #文字間の距離
        if check:
            break
        for j in start: #前で調べた最初の文字を選ぶ
            flag = 0
            c = 0 #cを増やしていくことによって、距離の等倍を表現
            while j + k * c < len(p) and c < len(s): #j(最初の文字)からc文字目までの距離
                if p[j+k*c] != s[c]:
                    break
                else:
                    c += 1
                    flag += 1
            if flag == len(s): #目的の文字が作成可能ならansに+1
                ans += 1
                check = True
                break

print(ans)

flagが汚い

C - 超都観光 (Super Metropolis)

考えたこと
初期値を(1,1)と誤読してました。初期値は(x1,y1)です。北東か南西に進むときだけ斜めに進むルートがあるので場合分けが必要で、それ以外は普通にgridの最短経路です。
鬼の場合分けしました()

• 縦または横移動のみの場合は、どちらかの座標の差は0になるのでmaxを取ります
• 北東に進むとき場合は、計算すると分りますがそれぞれの座標の差のmaxを取ればいいことが分ります。これは南西も同様です
• その他の場合は、斜めの道が使えないのでそれぞれの座標の差の絶対値の和を取ります

w, h, n = map(int,input().split())
spots = [list(map(int,input().split())) for _ in range(n)]

def search_route(s,g):
    if s[0] == g[0] or s[1] == g[1]: #縦または横移動のみ
        return max(abs(g[1] - s[1]), abs(g[0] - s[0]))

    elif s[0] < g[0] and s[1] < g[1]: #北東に進む
        return max(g[0] - s[0], g[1] - s[1])

    elif s[0] > g[0] and s[1] > g[1]: #南西に進む
        return max(s[0] - g[0], s[1] - g[1])

    else: #それ以外
        return abs(s[0] - g[0]) + abs(s[1] - g[1])

ans = 0
for i in range(n-1):
    ans += search_route(spots[i],spots[i+1])
print(ans)

A - ポスター (Poster)

考えたこと
ポスターを回転する操作を固定してそれぞれの場合を考えます。回転は$0°,90°,180°,270°$のいずれかです。あとは、目的のポスターと色の異なるマスを数えるだけです。

気分でinputを変えていますが普通のinputでも大丈夫です

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np #回転するという操作はnumpyを使います

n = int(readline())
s = np.array([list(readline().rstrip().decode()) for _ in range(n)])
t = [readline().rstrip().decode() for _ in range(n)]

ans = float('inf')
for i in range(4):
    check = np.rot90(s,i) #回転
    c = min(4-i,i)
    for j in range(n):
        for k in range(n):
            if check[j][k] != t[j][k]:
                c += 1
    ans = min(ans,c)
print(ans)

まとめ

汚いコードが多いので修正して、最終的にはC++で書く予定です。難易度4くらいが今の自分の適正レベルな気がしますが、さらなるレベルアップを目指して精進していきます。ではまた~