JOI2009本選B ピザ

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf#page=4

この問題は二分探索を用いて解くことができます。

方針

全探索を行うと計算量はO(mn)となり、満点にはなりません。そこで探索範囲を絞ります。

宅配先までは、環状線上で隣接する二店舗のうちのどちらかから配達するべきです。これは事前に店舗を位置でソートしておき、クエリ(宅配先)に対して二分探索を行うことで、計算量はO((m+n)logn)となり間に合います。

円環を扱う際は何らかの工夫をして一次元空間に落とすと良いです。今回であれば、本店が位置0だけでなく位置dにも存在するとみなすと良いでしょう。

Pythonの場合bisectを用いるのが良いでしょう。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import bisect
d = int(input())
N = int(input())
M = int(input())
shop = [0]
home = []
for n in range(N-1):
shop.append(int(input()))
for m in range(M):
home.append(int(input()))
shop.sort()
shop.append(d)
ans = 0
for h in home:
i = bisect.bisect(shop, h)
ans += min(abs(shop[i-1]-h), abs(shop[i]-h))
print (ans)

shopは必ず本店0を含んでいるため、bisect.bisectの結果はi=0にはなりえず、shop[-1]への期待しない参照は発生しません。

なおbisect.bisectではなくbisect.bisect_leftを使ったとしても、h=0の時shop[0]との距離が0となり最小値となるため、shop[-1]を参照するものの問題はありません。

記事情報

  • 投稿日:2020年5月17日
  • 最終更新日:2020年5月17日

ALDS1 4B 二分探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja

この問題は二分探索を用いて解くことができます。

方針

二分探索によりクエリの数値一つ一つが数列に含まれるかを判定していきます。

二分探索の計算量はO(logn)ですので、問題全体の計算量はO(qlogn)であり間に合います。

コード

1
2
3
4
5
6
7
8
9
10
11
12
import bisect
N = input()
INF = 10**10
S = list(map(int,input().split())) + [INF]
A = input()
T = list(map(int,input().split()))
ans = 0
for t in T:
i = bisect.bisect_left(S, t)
if (S[i] == t): # Sにtが含まれれば挿入点の値と等しい
ans += 1
print(ans)

記事情報

  • 投稿日:2020年5月17日
  • 最終更新日:2020年5月17日

JOI2015本選B ケーキの切り分け2

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2015ho/tasks/joi2015ho_b

この問題は動的計画法を用いて解くことができます。

方針

基本的に公式の解説通りです。区間DPと呼ばれる実装を行います。データが円環担っているため、データを2回並べることで一次元のデータとして扱います。

コード

maspyさんのコードをコメントを入れながら読ませていただきました。

最後のターンから考えていきます。最終的にJOIくんが得るスコアをdpとして格納していきます。dpはターン別に用意せずに使い回すのでサイズはNとなります。

最後から数えてnターン目にはn個のピースが残っています。そのパターンはiを変数としてA[i:i+n]で表せます。これに対させて、最終的にJOIくんが得るスコアをdp[i]に格納していきます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
A = np.array(read().split(),np.int64)

# 順に二回並べることで円環を区間につぶしたまま作業できる
A = np.concatenate([A,A])

# dp: 残りのピースがn個(A[i:i+n])だったとして、最終的にJOI君が得るスコア
# 小さいnから逐次的に更新していく(一次元配列を使い回す)
dp = np.zeros(N,np.int64)
for n in range(1,N+1):
dp = np.append(dp,dp[0]) # dpも円環
player = (N - n) & 1 # 最後のターンから考えるので、Nが偶数なら最後はIOI、奇数なら最後はJOI
if player == 0:
# JOI君
left = dp[1:N+1] + A[:N]
right = dp[:N] + A[n-1:N+n-1]
dp = np.maximum(left,right)
else:
# IOIちゃん
dp = np.where(A[:N] > A[n-1:N+n-1], dp[1:N+1], dp[:N])

answer = dp.max()
print(answer)

記事情報

  • 投稿日:2020年5月16日
  • 最終更新日:2020年5月16日

AOJ1193 連鎖消滅パズル

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1193&lang=jp

方針

アルゴリズムやデータ構造の知識は問われませんが、実装量が多いタイプの問題です。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
def move(board): # 空きを埋める関数
board = [list(x) for x in zip(*board)]
for i in range(len(board)):
row = board[i]
row = [i for i in row if i!=0]
n = len(board[i]) - len(row)
row.extend([0]*n)
board[i] = row
board = [list(x) for x in zip(*board)]
return board

ls_ans = []
while(1):
ans = 0
H = int(input())
if H==0:
break
board = []
for h in range(H):
C = list(map(int,input().split()))
board.append(C)
board = board[::-1]
for t in range(H):
for h in range(H):
C = board[h]
changed = set()
old_c = ''
oldold_c = ''
streak = 0
for i,c in enumerate(C):
if c == old_c and c == oldold_c:
if streak == 0:
streak += 3*c
C[i] = C[i-1] = C[i-2] = 0
else:
streak += c
C[i] = 0
else:
ans += streak
streak = 0
oldold_c = old_c
old_c = c
ans += streak
board[h] = C
board = move(board)
ls_ans.append(ans)

for ans in ls_ans:
print (ans)

記事情報

  • 投稿日:2020年5月16日
  • 最終更新日:2020年5月16日

ABC144D Water Bottle

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc144/tasks/abc144_d

方針

数式変形をして溢れる直前の傾きを求めます。ただし、水の体積が水筒の最大容量の半分を超えるかどうかで条件分岐が必要です。

溢れる直前の角度はarctanで計算します。Pythonの場合はmath.atanを用いると良いでしょう。またmath.degreesでラジアンから度数法に変換します。

コード

1
2
3
4
5
6
7
8
import math
a,b,x = map(int,input().split())
if x < a**2*b/2:
y = 2*x/(a*b)
print (math.degrees(math.atan(b/y)))
else:
y = 2*(b-x/(a**2))
print (math.degrees(math.atan(y/a)))

記事情報

  • 投稿日:2020年5月16日
  • 最終更新日:2020年5月16日

全国統一プログラミング王決定戦本戦A Abundant Resources

この記事で使うアルゴリズム

累積和

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_a

この問題は累積和を用いて解くことができます。

方針

全探索を考えます。区画の長さ・始点・終点についてループを回すことになるため計算量はO(N^3)で間に合いません。

区画の長さを変更してループを回す度に(部分和として)同一区間の和を求めているため冗長です。これを解消するために、あらかじめ累積和を求めておけば良いという発想に至ります。

コード

Pythonで累積和を計算したい場合、accumulateを利用すると良いです。

後ほど、累積和の差分を求めることになるので、あらかじめリストの先頭に0を挿入しておきます。

1
2
3
4
5
6
7
8
9
10
11
from itertools import accumulate
N = int(input())
A = [0] + list(map(int, input().split()))
csum = list(accumulate(A))

for i in range(1,N+1):
ans = 0
for j in range(N-i+1):
diff = csum[j+i] - csum[j]
ans = max(diff,ans)
print (ans)

記事情報

  • 投稿日:2020年5月16日
  • 最終更新日:2020年5月16日

三井住友信託銀行プログラミングコンテスト2019D Lucky PIN

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

この問題は全探索を用いて解くことができます。

方針

存在しうる暗証番号をK通りとして、全探索の計算量はO(NK)です。この問題では、暗証番号は3桁すなわちK=1000ですので、全探索でも十分間に合います。

コード

全探索

Pythonの場合だと実装によってはTLEとなるため、PyPyを用います。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from itertools import product
N = int(input())
S = input()
S = [int(s) for s in S]
ans = 0
for q in product(range(10),repeat=3):
i = 0
for s in S:
if s==q[i]:
if i==2:
ans += 1
break
else:
i+=1
print (ans)

別解 計算量O(N)の解法

ハッシュテーブル(setなど)を使い、prefixを保存していくことで効率よく数え上げができます。

1
2
3
4
5
6
7
8
9
10
11
12
13
N = int(input())
S = input()

st = [set() for _ in range(3)]

for s in S:
for pre in st[1]:
st[2].add(pre+s) # 3桁目
for pre in st[0]:
st[1].add(pre+s) # 2桁目
st[0].add(s) # 1桁目

print (len(st[2]))

記事情報

  • 投稿日:2020年5月16日
  • 最終更新日:2020年5月16日

パ研杯2019 3C カラオケ

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c

この問題は全探索を用いて解くことができます。

方針

曲の組み合わせはM^2のオーダーで、生徒はN人なので全探索の計算量はO(NM^2)となります。これは、この問題の制約条件から考えて問題がない計算量です。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from itertools import combinations
N, M = map(int, input().split())
A = []
for n in range(N):
a = list(map(int, input().split()))
A.append(a)

ans = 0
for m1, m2 in combinations(range(M),2):
score = 0
for a in A:
score += max(a[m1],a[m2])
ans = max(ans, score)
print (ans)

記事情報

  • 投稿日:2020年5月15日
  • 最終更新日:2020年5月15日

ALDS1 10B 連鎖行列積

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_B&lang=ja

この問題は動的計画法を用いて解くことができます。

方針

dp[i][j]を考えます。このリストは行列積M_i, M_i+1,..., M_jを計算するコストを表します。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
INF = 10**10
N = int(input())
dp = [[INF]*N for _ in range(N)]
R = []
for n in range(N):
r, c = map(int,input().split())
R.append(r)
R.append(c)

for i in range(N):
dp[i][i] = 0 # 対角成分すなわち、行列積Miを計算するコストは0である

for l in range(1,N): # iとjの差分
for i in range(N-l):
j = i+l
for k in range(i,j):
# cost(左側行列積) + cost(右側行列積) + 行列計算のコスト
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+R[i]*R[k+1]*R[j+1]) # 初回はR[0]*R[1]*R[2]
print (dp[0][-1])

具体的な計算例

行列積M_2 M_3 M_4 M_5M_2 M_3M_4 M_5の行列積として求める際の具体的な計算は以下のようになります。

1
2
3
4
5
6
7
8
9
R: R2  R3  R4  R5  R6
M: (M2 M3)(M4 M5)

l=1
i=2
j=5
k=3

M[2][5] = min(M[2][5], M[2][3] + M[4][5] + R[2]*R[4]*R[6])

記事情報

  • 投稿日:2020年5月15日
  • 最終更新日:2020年5月15日

square869120Contest#5B - Emblem

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/s8pc-5/tasks/s8pc_5_b

方針

  • 半径が決まっていないM個の円同士の関係に着目する。この時、最も小さい円の半径の最大値最も近い二点間の距離の半分であることが分かる。
  • 半径が決まっているN個の円とM個の円の関係に着目する。この時、最も小さい円の半径の最大値は二点間の距離から半径が決まっている円の半径を引いた値を全ての組み合わせについて調べ、その最小値となることが分かる。
    以上の二つの値のうち、小さい値が解となる。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from itertools import combinations
INF = 10**10
ans = INF # 最小値を更新するのでINFで初期化
N, M = map(int,input().split())
c_n = []
c_m = []
for n in range(N):
c_n.append(list(map(int,input().split())))
for m in range(M):
c_m.append(list(map(int,input().split())))

def dist(c1,c2): # ユークリッド距離を返却する
return pow(((c1[0]-c2[0])**2 + (c1[1]-c2[1])**2),0.5)

for c1,c2 in combinations(c_m,2): # M個の円同士
ans = min(ans,dist(c1,c2)/2) # 二点間の距離の半分

for c1 in c_n: # N個の円とM個の円
ans = min(ans,c1[2]) # 半径が決まっている円もチェック対象
for c2 in c_m:
ans = min(dist(c1[:2],c2) - c1[2], ans) # 二点間の距離から半径が決まっている円の半径を引く
print (ans)

記事情報

  • 投稿日:2020年5月14日
  • 最終更新日:2020年5月14日