クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「3-2 4 Values whose Sum is 0(POJ No.2785)」(p.147)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「3-2 4 Values whose Sum is 0(POJ No.2785)」(p.147)
のコードをPythonで書き直したものとなっています。

入力

n\\A_1\,…\,A_n\\B_1\,…\,B_n\\C_1\,…\,C_n\\D_1\,…\,D_n

入力例



6
-45 -41 -36 -36 26 -32
22 -27 53 30 -38 -54
42 56 -37 -75 -10 -6
-16 30 77 -46 62 45


解答

from bisect import bisect_left, bisect_right

# 入力
n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

CD = [0] * (n * n)    # CとDの組からの取り出し方

# CとDからの取り出し方の組を全列挙
for i in range(n):
    for j in range(n):
        CD[i * n + j] = C[i] + D[j]

CD.sort()

res = 0
for i in range(n):
    for j in range(n):
        cd = -(A[i] + B[j])
        # CとDから和がcdとなるように取り出す
        res += bisect_right(CD, cd) - bisect_left(CD, cd)

print(res)

AtCoder青色になりました!

こんにちは、クルトンです!

昨日(2021/2/13)のコンテストで再び青色になることができました!

f:id:kuruton456:20210214102401p:plain

そこでこの記事では青色になるまでにやったことを書いておこうと思います。

AtCoderを始めるまで

Pythonについての基本的な知識は知っていました。(if文やfor文、関数の書き方など)

ただアルゴリズムは一つも知らず、そもそも実行速度などは気にしたこともありませんでした。

AtCoderを始める

ここからは精進グラフとAtCoder ProblemsのDaily Effortを参照しながら書こうと思います。

f:id:kuruton456:20210214104002p:plain
精進グラフ
f:id:kuruton456:20210214104252p:plain
Daily Effort

初めてのコンテスト

僕は1回生の終わりごろ(2019年12月)にAtCoderを始めました。

初めて参加したコンテストが企業コンで、「え?1位取ったら6万円貰えんのかぁ...。何に使おうかなぁ?」とか思ったのを覚えています。

このときは1時間かけて3完だったので心が折れそうになりました。

蟻本を買う

次のコンテストでも同じような成績だったので、これではダメだと思い蟻本を買いました。

蟻本はC++で書いてあるのであまりよく分かりませんでしたが、半分ぐらいまでは頑張って読みました。

緑色で停滞する

蟻本のおかげで茶色までは行けたのですが、茶色と緑色のあたりで2か月ほど停滞していました。

そこで、4月の中旬頃からABC埋めを始めました。

ただ、正直AとBは埋めなくても良かったような気がします。(正直時間の無駄っぽいと思いながら惰性で埋めてました。達成感は得られましたが達成感だけしか得られませんでした。)

水色を上振れで抜ける

5月下旬に入水してから、ちょうど一か月くらいで入青できました。

このときはめちゃくちゃ調子に乗ってましたが、今から考えると上振れ以外の何物でもなかったと思います。

上振れを自覚しておらず精進をサボる

入青した次のコンテストでいきなり水色に戻ってしまいました。

しかし、このときはどうせすぐ戻るだろうと思っていました。

地獄の停滞期間

しかし、レートは下がる一方で10月頃には水色の中間まで落ちてしまいました。

なにかしないといけないのは分かっていましたが、レートを上げるには何をすればいいかが明確でなかったこともあり精進のやる気が起こりませんでした。(灰~茶diffを1日1問解いてStreakを継続させているだけでした)

marocasさんの入青記事を読む

11/24にmarocasさんが書かれた入青記事にどのように精進したかが詳しく書かれていたので、それを参考にして精進を始めました。


具体的には

11/29~12/28に『分野別 初中級者が解くべき過去問精選 100 問

1/12~2/6に『Educational DP Contest

を解きました。


今は『AtCoder Library Practice Contest』と『上級者が解くべき過去問精選 100 + 50 問』を解いています。

個人的にはこの精進が再入青できた一番の要因だと思っています。(なので入青できずに困ってる人は一度marocasさんの記事を読まれることをお勧めします!)

今後について

AtCoder Library Practice Contest』と『上級者が解くべき過去問精選 100 + 50 問』がとても難しい上に、蟻本がまだ半分ほど残っているのでしばらくは精進の内容に困らずに済みそうです。

いつ達成できるかは分かりませんが、このまま黄色を目指して頑張ろうと思います!

Pythonで理解する蟻本「3-2 Physics Experiment(POJ No.3684)」(p.145)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「3-2 Physics Experiment(POJ No.3684)」(p.145)
のコードをPythonで書き直したものとなっています。

入力

N\,H\,R\,T

入力例1



1 10 10 100

入力例2



2 10 10 100


解答

g = 10.0    # 重力加速度

# 入力
N, H, R, T = map(int,input().split())

y = [0] * N    # 最終的なボールの位置

# 時刻Tでのボールの位置を求める
def calc(T):
    if T < 0:
        return H
    t = (2 * H / g) ** 0.5
    k = T // t
    if k % 2 == 0:
        d = T - k * t
        return H - g * d * d / 2
    else:
        d = k * t + t - T
        return H - g * d * d / 2

for i in range(N):
    y[i] = calc(T - i)
y.sort()
print(*['{:.2f}'.format(y[i] + 2 * R * i / 100) for i in range(N)])

Pythonで理解する蟻本「3-2 Fliptile(POJ No.3279)」(p.141)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「3-2 Fliptile(POJ No.3279)」(p.141)
のコードをPythonで書き直したものとなっています。

入力

M\,N\\tile_{(1,1)}\,…\,tile_{(1, N)}\\:\\tile_{(M,1)}\,…\,tile_{(M, N)}

入力例



4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1


解答

# 隣接するマスの座標
dx = [-1, 0, 0, 0, 1]
dy = [0, -1, 0, 1, 0]

# 入力
M, N = map(int,input().split())
tile = [list(map(int,input().split())) for _ in range(M)]

# (x, y)の色を調べる
def get(x, y):
    c = tile[x][y]
    for d in range(5):
        x2 = x + dx[d]
        y2 = y + dy[d]
        if 0 <= x2 < M and 0 <= y2 < N:
            c += flip[x2][y2]
    return c % 2

# 1行目を決めた場合の最小操作回数を求める
# 解が存在しないならば-1
def calc():
    # 2行目からのひっくり返し方を求める
    for i in range(1, M):
        for j in range(N):
            if get(i - 1, j) != 0:
                # (i - 1, j)が黒色なら、このマスをひっくり返すしかない
                flip[i][j] = 1
    
    # 最後の行が全部白かチェック
    for j in range(N):
        if get(M - 1, j) != 0:
            # 解なし
            return -1
    
    # 反転回数をカウント
    res = 0
    for i in range(M):
        for j in range(N):
            res += flip[i][j]
    return res

res = -1

# 1行目を辞書順で全通り試す
for i in range(1 << N):
    flip = [[0] * N for _ in range(M)]    # 作業用
    for j in range(N):
        flip[0][N - j - 1] = i >> j & 1
    num = calc()
    if num >= 0 and (res < 0 or res > num):
        res = num
        opt = [[flip[i][j] for j in range(N)] for i in range(M)]    # 最適解保存用
    
if res < 0:
    # 解なし
    print('IMPOSSIBLE')
else:
    for i in range(M):
        print(*opt[i])

Pythonで理解する蟻本「3-2 Face The Right Way(POJ No.3276)」(p.139)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「3-2 Face The Right Way(POJ No.3276)」(p.139)
のコードをPythonで書き直したものとなっています。

入力

N\\DIR_1\,…\,DIR_N

入力例



7
BBFBFBB


解答

MAX_N = 5000

# 入力
N = int(input())
DIR = [c == 'B' for c in input()]    # 牛の方向(0:F, 1:B)


# Kを固定したときの最小操作回数を求める
# 解が存在しないならば-1
def calc(K):
    f = [0] * MAX_N    # 区間[i,i+K-1]を反転させたかどうか
    res = 0
    SUM = 0    # fの和
    for i in range(N - K + 1):
        # 区間[i,i+K-1]に着目
        if (DIR[i] + SUM) % 2 != 0:
            # 先頭の牛が後ろを向いている
            res += 1
            f[i] = 1
        SUM += f[i]
        if i - K + 1 >= 0:
            SUM -= f[i - K + 1]
    
    # 残りの牛が前を向いているかをチェック
    for i in range(N - K + 1, N):
        if (DIR[i] + SUM) % 2 != 0:
            # 解なし
            return -1
        if i - K + 1 >= 0:
            SUM -= f[i - K + 1]
    return res

K = 1
M = N
for k in range(1, N + 1):
    m = calc(k)
    if m >= 0 and M > m:
        M = m
        K = k
print(K, M)

Pythonで理解する蟻本「3-2 Jessica's Reading Problems(POJ No.3320)」(p.137)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「3-2 Jessica's Reading Problems(POJ No.3320)」(p.137)
のコードをPythonで書き直したものとなっています。

入力

P\\a_1\,…\,a_P

入力例



5
1 8 8 8 1


解答

# 入力
P = int(input())
a = list(map(int,input().split()))

# 書かれている事柄の総数を計算
ALL = set(a)
n = len(ALL)

# しゃくとり法により解を求める
s = 0
t = 0
num = 0
count = {}    # 事柄→出現数の対応
res = P
while True:
    while t < P and num < n:
        if not a[t] in count:
            # 新しい事象が出現
            count[a[t]] = 0
            num += 1
        count[a[t]] += 1
        t += 1
    if num < n:
        break
    res = min(res, t - s)
    count[a[s]] -= 1
    if count[a[s]] == 0:
        # ある事柄の出現数が0になった
        num -= 1
    s += 1

print(res)

Pythonで理解する蟻本「3-2 Subsequence(POJ No.3061)」(p.135)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「3-2 Subsequence(POJ No.3061)」(p.135)
のコードをPythonで書き直したものとなっています。

入力

n\,S\\a_1\,…\,a_n

入力例1



10 15
5 1 3 5 10 7 4 9 2 8

入力例2



5 11
1 2 3 4 5


二分探索を用いた解答(O(n log n))

import sys
from bisect import bisect_left

# 入力
n, S = map(int,input().split())
a = list(map(int,input().split()))

SUM = [0] * (n + 1)

# SUMを計算する
for i in range(n):
    SUM[i + 1] = SUM[i] + a[i]

if SUM[n] < S:
    # 解が存在しない
    print(0)
    sys.exit()

res = n
s = 0
while SUM[s] + S <= SUM[n]:
    # 終端tを二分探索で求める
    t = bisect_left(SUM, SUM[s] + S)
    res = min(res, t - s)
    s += 1

print(res)

しゃくとり法を用いた解答(O(n))

# 入力
n, S = map(int,input().split())
a = list(map(int,input().split()))

res = n + 1
s = 0
t = 0
SUM = 0

while True:
    while t < n and SUM < S:
        SUM += a[t]
        t += 1
    if SUM < S:
        break
    res = min(res, t - s)
    SUM -= a[s]
    s += 1

if res > n:
    # 解が存在しない
    res = 0
print(res)