いくつかの記事を参考にしていますが、基本的に自力で解答することを目指しました。
今後に生かせるよう、汎用的で一般的な実装を行うことを心掛けました。
また、辞書的に利用できるよう、各問題に（個人的な）分類を記載しました。Ctrl + F のショートカットキーを使って、キーワードで問題を検索できます。
前回の記事
ABC100 C – *3 or /2（計算量・整数論）
- 結局2で割れる回数を数えたい。
- 10 < 2^4 だから10^9 < 2^36 よって１つのaにつき最大36回の割り算だけで済む。
def count_split(n):
cnt = 0
while n%2 == 0:
n /= 2
cnt += 1
return cnt
N = int(input())
A = list(map(int, input().split()))
ans = 0
for a in A:
ans += count_split(a)
print(ans)ABC101 C – Minimization（計算量）
- 全要素の最小値=1にするのが最短。
- 公式解説の動画が分かりやすい。
N, K = map(int, input().split())
A = list(map(int, input().split()))
g = 0
tot = 0
while N-K > tot:
g += 1
tot = g*(K-1)
print(g+1)ABC102 C – Linear Approximation（マンハッタン距離）
C – Linear Approximation (atcoder.jp)
- 可能性として10^9通りのbがあるし、目的の値を求めるのに10^5かかる。
- マンハッタン距離を知らないと無理？
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
A[i] -= (i+1)
A.sort()
# 中央値のインデックスを引数とする
# 和の計算を行う関数
def f(mid):
ret = 0
for a in A:
ret += abs(a-A[mid])
return ret
# 中央値が２つ存在するとき
if N%2 == 0:
mid_back = N//2 - 1
mid_forth = N//2
print(min(f(mid_back), f(mid_forth)))
# 中央値が１つに定まる時
else:
mid = N//2
print(f(mid))ABC103 C – Modulo Summation（整数論）
C – Modulo Summation (atcoder.jp)
N = int(input())
A = list(map(int, input().split()))
ans = 0
for a in A:
ans += (a-1)
print(ans)ABC104 C – All Green（bit全探索・論理演算）
D, G = map(int, input().split())
p = [0]*D
c = [0]*D
for i in range(D):
p[i], c[i] = map(int, input().split())
# 全完する難易度の組み合わせをビット全探索
# ビット探索の場合, bit => D番目, D-1番目, ... 2番目, 1番目 の難易度に対応することに注意
ans = 10001
for bit in range(1<<D):
tot = 0
num = 0
for i in range(D):
if (bit & (1<<i)): # 例) D=4, 1<<3 = 1000 の場合先頭の数字が判定され、bit = 1010の場合Trueとなる
tot += 100*(i+1)*p[i] + c[i]
num += p[i]
if tot >= G:
ans = min(ans, num)
else:
for i in range(D-1, -1, -1):
if (bit & (1<<i)):
continue # すでに全完していたらスキップ
for j in range(p[i]): # p[i]未満の個数を取る
# 条件を満たした時点で追加をやめる
# 次の難易度iのループからは抜け出していないので、ここでふるいにかける
# 代わりに多重からのbreakを使っても良さそう
if tot >= G:
break
tot += 100*(i+1) # 1つ追加する
num += 1
if tot >= G:
ans = min(ans, num)
print(ans)参考：
https://drken1215.hatenablog.com/entry/2018/08/05/224100
ABC105 C – Base -2 Number（整数論）
C – Base -2 Number (atcoder.jp)
- 正負に限らず、2で割り切れなければ4でも割り切れない。
- つまり、2^i で割り切れなければ2^{i + 1}でも割り切れない。
- よって、絶対値の小さい位から判定していく。
N = int(input())
ans=""
i = 1
while N != 0:
if N%(2**i) == 0:
ans += "0"
else:
ans += "1"
N -= (-2)**(i-1)
i += 1
#print(N)
ans = ans[::-1]
if ans == "":
print(0)
elif ans[0] == "0":
print(ans[1:])
else:
print(ans)ABC106 C – To Infinity（計算量）
高校時代に知ってたら面白い問題だと思った
- 1なら増えない。
- 1より大きい中で最も小さい2でさえ2^5000兆 >> 10^18である。
（logを使った概算ですぐわかる）
S = input()
K = int(input())
one_idx = 0
not_one = ""
for s in S:
if s == "1":
one_idx += 1
else:
not_one = s
break
if K <= one_idx:
print(1)
else:
print(not_one)ABC107 C – Candles（計算量）
- 連続したK点を消すのが最短。
- K点の範囲が原点をまたぐか否かで場合分けする。
- またぐ場合、正（または負）側に行ってから、原点まで戻る必要があるため、往路だけでなく、復路にかかる時間も考慮する必要がある。
N, K = map(int, input().split())
X = list(map(int, input().split()))
ans = 10**9
for i in range(N-K+1):
tail = X[i]
head = X[i+K-1]
#print("tail:", tail," head:" ,head)
# K 点の幅が原点をまたがない場合
if tail * head >= 0:
if head <= 0:
ans = min(ans, abs(tail))
elif 0 <= tail:
ans = min(ans, head)
# K 点の幅が原点をまたぐ場合
else:
ans = min(ans, 2*abs(tail) + head, abs(tail) + 2*head)
print(ans)ABC108 C – Triangular Relationship（偶奇の利用）
C – Triangular Relationship (atcoder.jp)
- 単純な全探索では計算量はO(N^3)で不可能
- a+b, b+c, c+bの満たすべき条件をa, b, cの満たすべき条件に変える
- そのためには場合分けが必要
- Kが奇数の時、a, b, cはそれぞれKの倍数
- Kが偶数の時、a, b, cはそれぞれKまたはK/2の倍数
- Kの倍数でなく、K/2の倍数であることは、Kで割ったあまりがK/2であると言い換えることができる
N, K = map(int, input().split())
num = 0
num_half = 0
if K % 2 != 0:
for n in range(1, N+1):
if n % K == 0:
num += 1
else:
for n in range(1, N+1):
if n % K == 0:
num += 1
elif n % K == K//2:
num_half += 1
print(num**3 + num_half**3)Kが偶数の時、Kの倍数であるaの総数と、K/2の倍数であるaの総数は分けて数える必要があることに注意する。
ABC109 C – Skip（ソート・最大公約数）
- 通る順序は関係ない
- よって、出発地Xを訪問地リストxに含め、ソートし、「各要素の隣の要素との間隔」の最大公約数を求めればよい。
- math.gcd()関数を使う。
# 通る順番は関係ない
#
import math
N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X) # xの要素はN+1個
x.sort()
d_pre = x[1] - x[0]
ans = d_pre
for i in range(1, N):
d_now = x[i+1] - x[i]
ans = min(math.gcd(d_now, d_pre), ans)
d_pre = d_now
print(ans)ABC110 C – String Transformation（文字列の置換）
C - String Transformation
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
- Sに含まれる同じ文字を、異なる文字で置換することはできない。（例）abbがあったとして、どちらかのbをcに置換する=もう一方のbもcに置換される。
- 異なる文字を、同じ文字に置換することはできない。（例）abcに対し、a, bをdで置換できない。
- なぜなら、(1)異なる文字を同時に変更することはできない。(2)aをdに変更すると、次にbをdに変更する際に元々aだったdがbになってしまう。からである。
以上よりSの同じ文字はそのままor他の１つの文字に変更のいづれかのみ許される。
S = input()
T = input()
# 対応関係
change = {}
# 変更先
used = set()
flag = True
for i in range(len(S)):
# 初めて出会った文字
if S[i] not in change:
if T[i] in used:
flag = False
break
change[S[i]] = T[i]
#change[T[i]] = S[i]
used.add(T[i])
else:
# 既にある対応に合わなかった場合
if change[S[i]] != T[i]:
flag = False
break
print("Yes" if flag else "No")別解
S=input()
T=input()
print('Yes' if sorted(map(S.count,set(S)))==sorted(map(T.count,set(T)))else 'No')ABC111 C – /\/\/\/（カウント・最も多い要素）
- 奇数番目グループと偶数番目グループにわける。
- それぞれのグループの中で最も多い数字を見つける。
- もし1.初めからすべて同じ数字2.あるいは入れ替えた結果全て同じ数字だった場合、どちらかのグループを別の数字に変更する必要がある。
from collections import Counter
n = int(input())
v = list(map(int, input().split()))
counter_odd = Counter()
counter_even = Counter()
for i in range(0, n, 2):
counter_odd[v[i]] += 1
for i in range(1, n, 2):
counter_even[v[i]] += 1
a = max((v, k) for k, v in counter_odd.items())[1]
a_ = max((v, k) for k, v in counter_odd.items())[0]
b = max((v, k) for k, v in counter_even.items())[1]
b_ = max((v, k) for k, v in counter_even.items())[0]
c_ = 0
d_ = 0
if a == b:
counter_odd[a] = 0
counter_even[b] = 0
# oddの方を変更する場合
c_ = max((v, k) for k, v in counter_odd.items())[0]
# evenの方を変更する場合
d_ = max((v, k) for k, v in counter_even.items())[0]
print(min(n-c_-b_, n-a_-d_))
else:
print(n-a_-b_)ABC112 C – Pyramid（ソート・一括真偽判定）
今回は、リストの代わりに、namedtupleを用いてみた。
リストLに１つの座標点の情報x, y, hをL=[x, y, h]のように格納する場合、要素の取り出しはL[0], L[1], L[2]となる。
一方、namedtuple NTを生成し、要素の格納を行った場合、NT = (x, y, h)となる。各要素の取り出しはNT.x, NT.y, NT.hのように変わる。
問題そのものの解き方について、詳しくは公式解説を参照のこと。
from collections import namedtuple
N = int(input())
NT = namedtuple('NT', 'x y h')
info = []
for _ in range(N):
x, y, h = map(int, input().split())
info.append(NT(x, y, h))
# 最も高い位置の情報はh >= 1であるはず
high = sorted(info, key=lambda x: x[2], reverse=True)[0]
for cx in range(101):
for cy in range(101):
H = high.h + abs(high.x - cx) + abs(high.y - cy)
# 他の位置の情報と矛盾しなければ、それの時の座標が解
if all([h == max(H - abs(x - cx) - abs(y - cy), 0) for x, y, h in info]):
print(cx, cy, H)namedtupleについて：
namedtupleで美しいpythonを書く！（翻訳） – Qiita
ABC113 C – ID（多次元配列の複数キーでのソート・桁の0埋め）
データの整理をするにあたり、実用的な問題だと感じた。
- P, Yの値毎にソートする。
- 足りない桁の0埋めは、”文字列”.zfill(桁数)で簡単に実装できる。
N, M = map(int, input().split())
idpy = []
for i in range(M):
P, Y = map(int, input().split())
idpy.append([i, P, Y])
idpy = sorted(idpy, key=lambda x:(x[1], x[2]))
cnt = 0
year = -1
for i in range(M):
if idpy[i][1] != year:
year = idpy[i][1]
cnt = 1
else:
cnt += 1
idpy[i][1] = str(year).zfill(6)
idpy[i][2] = str(cnt).zfill(6)
idpy.sort()
for i, year, cnt in idpy:
print(year+cnt)ABC114 C – 755（深さ優先探索・桁ずらし・Digit DP/桁DP）
- 公式解説と同じように、dfsで解いた。
- 現在の数を左に１桁ずらす操作を、10をかけることで実現。
- 文字列の末尾に3, 5, 7を付けていくやり方もある。
7, 5, 3が含まれるかどうかは文字列を使う必要があるし、Nとの大小比較には整数型が必要。よって、DFSで解く場合は、文字列<=>整数型の変換が入る。
なお、DPで解く方法もあるらしい。
N = int(input())
def dfs(n):
ret = 1 if all(str(n).count(c) > 0 for c in '753') else 0
if n <= N:
for c in [7, 5, 3]:
ret += dfs(10 * n + c)
else:
return 0
return ret
print(dfs(0))ABC115 C – Christmas Eve（ソート・単調性）
C – Christmas Eve (atcoder.jp)
- 昇順ソートし、連続するK個の両端の高さを比較していく。
N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
h.sort()
ans = 10**9
for i in range(N-K+1):
ans = min(ans, h[i+K-1]-h[i])
print(ans)ABC116 C – Grand Garden（）
- 隣り合った高さの揃った段を消せる、テトリスをイメージする。
- 左から見ていき、activeをスイッチとして、隣合っているか否かを表現。
- any()を使った。
N = int(input())
h = list(map(int, input().split()))
ans = 0
while any(i > 0 for i in h):
active = False
# 左から見ていく
for i in range(N):
# 高さが残っていた場合
if h[i] > 0:
# 左隣がactiveでない場合、スイッチを入れる
if not active:
active = True
h[i] -= 1
# 左隣がactiveな場合
else:
h[i] -= 1
# 高さが0になっていた場合
else:
# 左隣がacviveならスイッチを切る
if active:
active = False
ans += 1
# スイッチがオンのままの場合
if active:
ans += 1
print(ans)ABC117 C – Streamline（ソート）
- 最も離れている点をN個に分割。
- 各コマの担当区画を割り当てるイメージ
N, M = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
intervals = []
for i in range(M-1):
intervals.append(x[i+1] - x[i])
intervals = sorted(intervals, reverse=True)
print(sum(intervals[N-1:]))ABC118 C – Monsters Battle Royale（最大公約数）
解説 – AtCoder Beginner Contest 118
- 体力A_iは体力でもあり、攻撃力でもある。
- サンプルケースを見た限り、全要素の最大公約数っぽいことに気づく。
- ABC109のC問題とほぼ同じ解き方。
全要素の最大公約数に等しくなることは、公式解説で論理的に解説されている。ここに、解説の抜粋を記載しておく。
体力 a のモンスターと体力 b のモンスターがお互いの体力が等しくなるまで体力の低いほうが高い方を攻撃し続けるとユークリッドの互除法と同じ遷移になるため最終的な体力はお互いに a と b の最大公約数になります。
editorial.pdf (atcoder.jp)
import math
N = int(input())
A = list(map(int, input().split()))
ans = 10**9
for i in range(N-1):
ans = min(ans, math.gcd(A[i], A[i+1]))
print(ans)ABC119 C – Synthetic Kadomatsu（深さ優先探索）
C – Synthetic Kadomatsu (atcoder.jp)
有難いことに、公式解説がPythonで書かれていた！
- 合成をやってから短くする=短くしてから合成する、であるから、必要な合成すべてを先に行ってしまう。
- 各要素について、「A, B, C,のいづれかに合成される」「所属無し」の4択がある。
- 長さ0の要素に対して伸縮操作はできないことに注意
- 4進数のbit全探索orDFSで解く。
公式解説だけでは十分に理解できなかったので、詳しい解説をこちら。
N, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(N)]
INF = 10**9
# 最低コストを出力する関数
# a, b, cは3本の竹の現在の長さ
# 現在l[v]の何番目を考えているか
def dfs(v, a, b, c):
# N本目までの調査が終わった場合
if v == N:
# lの最後の要素まで探索して、全ての竹に高さがある場合
# 最初、高さ0 => 1本竹を追加する操作は、「合成」ではない。
# よってMP = 10 * 3本分の余計なコストを引く
if min(a, b, c) > 0:
return abs(A - a) + abs(B - b) + abs(C - c) - 30
# lの最後の要素まで探索して、高さ0の竹がある場合
else:
return INF
# メイン部分
ret0 = dfs(v + 1, a, b, c)
ret1 = dfs(v + 1, a + l[v], b, c) + 10
ret2 = dfs(v + 1, a, b + l[v], c) + 10
ret3 = dfs(v + 1, a, b, c + l[v]) + 10
return min(ret0, ret1, ret2, ret3)
print(dfs(0, 0, 0, 0))ABC120 C – Unification（カウント）
AtCoder Beginner Contest 120 – AtCoder
S = input()
zero = S.count("0")
one = S.count("1")
print(min(zero, one)*2)ABC121 C – Energy Drink Collector（ソート）
C – Energy Drink Collector (atcoder.jp)
- 単価でソートして、単価の安い順に購入すればよい。
- 目標のM個を超えるまで、安い単価の商品をあるだけ購入する。
- 超えた分だけ、買った中で最も単価の高い（最後に買った）商品の払い戻しをすればよい。
N, M = map(int, input().split())
a = [[0, 0] for _ in range(N)]
for i in range(N):
a[i][0], a[i][1] = map(int, input().split())
a.sort()
result = 0
cnt = 0
idx = 0
# M個を超えるまで安い店から買う
while cnt < M:
result += a[idx][0] * a[idx][1]
cnt += a[idx][1]
idx += 1
if cnt == M:
print(result)
# M個より多く買った場合、多い分払い戻し
elif cnt > M:
print(result - a[idx-1][0] * (cnt - M))ABC122 C – GeT AC（累積和）
- 左から見ていき、ACが完成したらcnt[i] = cnt[i-1]+1。
- よって、配列cntは累積和となる。
N, Q = map(int, input().split())
S = input()
cnt = [0] * N
if S[0] == "A":
tmp = "A"
else:
tmp = ""
for i in range(1, N):
if tmp == "" and S[i] == "A":
tmp += "A"
cnt[i] = cnt[i-1]
elif tmp == "A" and S[i] == "C":
cnt[i] = cnt[i-1] + 1
tmp = ""
elif tmp == "A" and S[i] == "A":
cnt[i] = cnt[i-1]
tmp = "A"
else:
cnt[i] = cnt[i-1]
tmp = ""
for _ in range(Q):
l, r = map(int, input().split())
print(cnt[r-1] - cnt[l-1])ABC123 C – Five Transportations（律速段階）
C – Five Transportations (atcoder.jp)
- 時刻４以降を考える。
- x人ごとのグループ(最後のグループはx人以下)が途切れることなくゴールする。
import math
N = int(input())
x = min([int(input()) for _ in range(5)])
print(math.ceil(N/x) + 4)ABC124 C – Coloring Colorfully（偶奇の利用）
C – Coloring Colorfully (atcoder.jp)
- 最終結果は0101…or1010…の２パターンしか存在しない。
S = input()
# 0101...
odd = 0
for i in range(len(S)):
if i%2 == 0:
if S[i] == "1":
odd += 1
else:
if S[i] == "0":
odd += 1
# 1010...
even = 0
for i in range(len(S)):
if i%2 == 0:
if S[i] == "0":
even += 1
else:
if S[i] == "1":
even += 1
print(min(odd, even))ABC125 C – GCD on Blackboard（累積GCD・両端攻め）
C – GCD on Blackboard (atcoder.jp)
- 各iについて、自分(Ai)以外の最大公約数を求め、その最大値を求めればよい。
- 各Ai以外の要素の最大公約数を、O(N)より少なく求めたい。
- 左側からの累積GCDと、右側からの累積GCDを求めておく。
参考：
累積GCDでAtCoder ABC 125 C – GCD on Blackboardを解く – Muroi Log (muroiwataru.net)
from math import gcd
N = int(input())
A = list(map(int, input().split()))
# 左端からの累積gcd
L = [0] * (N + 1)
# A[i]までの最大公約数を求める
# 各ループでの計算量はO(logA_1)なので全体でO(NlogA_1)
for i in range(1, N+1):
L[i] = gcd(L[i-1], A[i-1])
# 右端からの累積gcd
R = [0] * (N + 1)
for i in range(N-1, -1, -1):
R[i] = gcd(A[i], R[i+1])
ans = 0
for i in range(N):
ans = max(ans, gcd(L[i], R[i+1]))
print(ans)ABC126 C – Dice and Coin（確率）
C – Dice and Coin (atcoder.jp)
- はじめに i の目が出たとき、得点が K 以上になるために、Mi 回コインの表を出し続ける必要があると考える。
- 各 i に対して、Miをループ処理で求めることができる。
- 一方、i * 2 ^ M >= K すなわち M >= log2(K / i)を満たすような最小の M を計算して求めることができる。
- 今回は後者を採用したが、log2(K / i) が負の値をとりうる一方で、M > 0である必要があることに注意する必要がある。
import math
N, K = map(int, input().split())
tot = 0
# 初めに出た値が i のときK以上となる確率
for i in range(1, N + 1):
m = math.ceil(math.log2(K / i))
tot += (0.5) ** max(0, m)
#print(m)
print(tot / N)ABC127 C – Prison（共通区間）
- 共通区間を求める問題として解釈できる。
- 区間[l_0, r_0], [l_1, r_1] の共通区間は、[max(l_0, l_1)], min(l_0, l_1)]によって求まる。
N, M = map(int, input().split())
l_ = 0
r_ = 10**6
for i in range(M):
l, r = map(int, input().split())
l_ = max(l_, l)
r_ = min(r_, r)
if r_ - l_ >= 0:
print(r_ - l_ + 1)
else:
print(0)ABC128 C – Switches（ビット全探索）
全探索できそうだけど、問題文を頭で整理しがたい問題だった。
- 各電球とつながっているスイッチのリストla_swを受け取る。
- la_swを各スイッチとつながっている電球のリストsw_laに変換。
- スイッチの押し状況で全探索をする。
- xorで、各ランプの点灯状況を更新していく。
N, M = map(int, input().split())
# 各電球とつながっているスイッチのリスト
la_sw = [list(map(int, input().split()))[1:] for _ in range(M)]
sw_la = [[] for _ in range(N)]
# スイッチごとに、繋がっている電球のリストを作成
for la, sw_list in enumerate(la_sw):
for sw in sw_list:
sw_la[sw-1].append(la)
# 全部点灯している状態を10進数で保存
# ビット探索の関係上、順番が逆になる（ランプ 1 が下の桁になる）
lit_cond = int(''.join(input()[::-1].split()), 2)
# 考えうる全てのスイッチの押し状況についてビット全探索
result = 0
for st in range(2 ** N):
lamp_status = 0
# スイッチ毎に ON になっているかどうかを確認し、
# ON なら lamp_status を変化させる
for i in range(N):
# スイッチは ON ？
# 各状況において、１つずつのスイッチを適用
if st>>i & 1:
for la in sw_la[i]:
# xor 演算は ^
lamp_status = lamp_status ^ (1<<la)
# 全部点灯している状態の場合
if lamp_status == lit_cond:
result += 1
print(result)参考：
AtCoder Beginner Contest 128 C – Switches をPython3で解く | みゃおと鳴いたnet (miaoued.net)
ABC129 C – Typical Stairs（動的計画法）
AtCoder Beginner Contest 129 – AtCoder
- dp[i] = i段目の階段にたどり着く方法の数。
- aに含まれる階段について、dp[i] = 0とする。
- if文の箇所は、if not i in a でもいいが、計算量を削減できる方法を取った。
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0] * (N + 1)
dp[0] = 1
dp[1] = (1 if 1 not in a else 0)
j = (0 if 1 not in a else 1)
for i in range(2, N + 1):
if j < M and a[j] == i:
dp[i] = 0
j += 1
else:
dp[i] += dp[i - 1]
dp[i] += dp[i - 2]
print(dp[N] % (10 ** 9 + 7))ABC130 C – Rectangle Cutting（分類無し）
C – Rectangle Cutting (atcoder.jp)
- 結局、答えは長方形の面積の丁度半分になる。
- (x, y)が長方形の中心と一致するときのみ、複数の分割方法が存在する。
W, H, x, y = map(int, input().split())
if x == W/2 and y == H/2:
n = 1
else:
n = 0
print(W * H / 2, n)ABC131 C – Anti-Division（最小公倍数・最大公約数）
C – Anti-Division (atcoder.jp)
- BまでのC, D, lcm(C, D)の倍数の個数と、(A-1)までのC, D, lcm(C, D)の倍数の個数を計算しておくことで、O(1)で答えを求めることができる。
- Python3.9 以前ではmathモジュールにlcm（最小公倍数）関数がないため、最大公約数を求めるgcm関数を用いて、lcm関数を自分で実装する必要がある。
import math
def lcm(x, y):
return (x * y) // math.gcd(x, y)
A, B, C, D = map(int, input().split())
l = B - A + 1
c_b = B//C
c_a = (A - 1)//C
d_b = B//D
d_a = (A - 1)//D
cd_b = B // lcm(C, D)
cd_a = (A - 1) // lcm(C, D)
print(l - ((c_b - c_a) + (d_b - d_a) - (cd_b - cd_a)))ABC132 C – Divide the Problems（分類無し）
C – Divide the Problems (atcoder.jp)
N = int(input())
d = sorted(list(map(int, input().split())))
print(d[N//2] - d[N//2-1])ABC133 C – Remainder Minimization 2019（整数論）
C – Divide the Problems (atcoder.jp)
2019 で割った余りが同じであるような 2 数 a, b について、(a×c) mod 2019
editorial.pdf (atcoder.jp)
と (b × c) mod 2019 は必ず同じ値になります。
（例えば、a = 2020, b = 4039の場合）
- L <= i < j <= R を満たすi, jのループにおいて、i + 2019*n, j + 2019*m（n, mは自然数）を試す必要はない。
- なぜなら、modの世界ではi + 2019*n, j + 2019*mはそれぞれi, jと同等であるから。
- 公式解説の通り、R = min(R, L + 2019)とすることで、探索範囲を狭めることができる。
L, R = map(int, input().split())
R = min(R, L + 2019)
ans = 2019
for i in range(L, R + 1):
for j in range(i + 1, R + 1):
ans = min(ans, i*j % 2019)
print(ans)ABC134 C – Exception Handling（両端攻め）
C – Exception Handling (atcoder.jp)
- 左から i (0 <= i <= N -2)番目までの最大値を求める。
- 右から i (0 <= i <= N -2)番目までの最大値を求める。
上の２つを使って、
A_i_max = l[i-1] + r[N-2+1]
のように、左からi (0 <= i <= N -1)番目の数を取り除いた時の最大値を求める。
# 134
N = int(input())
A = [int(input()) for _ in range(N)]
# 左から i 番目までの最大値
l = [0] * (N - 1)
# 右から i 番目までの最大値
r = [0] * (N - 1)
ma = A[0]
l[0] = A[0]
for i in range(1, N - 1):
ma = max(ma, A[i])
l[i] = ma
ma = A[-1]
r[0] = A[-1]
for i in range(2, N):
ma = max(ma, A[-i])
r[i-1] = ma
for i in range(N):
if i == 0:
print(r[N - 2])
elif 0 < i < N -1:
print(max(l[i - 1], r[N-2-i]))
else:
print(l[i-1])ABC135 C – City Savers（min・max・場合分け）
- 勇者iの倒せるモンスターの数Biが、街iにいるモンスターの数Aiに対して多いか少ないかで場合分けをする。
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
for i in range(N):
# モンスターを過剰に倒せるとき
if B[i] >= A[i]:
ad = min(B[i] - A[i], A[i + 1])
ans += A[i] + ad
A[i + 1] = max(0, A[i + 1] - ad)
# モンスターを倒し残すとき
else:
ans += B[i]
print(ans)ABC136 C – Build Stairs（場合分け）
公式解説では
右のマスから順に操作を選ぶと、できるだけ高くしておいた方が後で選択肢が増えるので、
• 何もしなくて良いなら何もしない
• そうでなくて、右のマスよりもちょうど 1 高いなら 1 低くする
• そうでないならどう頑張ってもダメなので答えは No
を右から順に行う。
と述べている。しかし、A[::-1]でリストを反転させ、左から操作を行うことで、
現在のマスが、次のマスより低いとき、次のマスを１低くするのが最善。
となる。
N = int(input())
A = list(map(int, input().split()))[::-1]
for i in range(N - 1):
if A[i] < A[i + 1]:
A[i + 1] -= 1
flag = True
for i in range(N - 1):
if A[i] < A[i + 1]:
flag = False
print("Yes" if flag else "No")ABC137 C – Green Bin（組み合わせ・ソート・カウント）
- 文字列に含まれるアルファベットの一致は、辞書順にソートした文字列が一致するかどうかを見ればわかる。
- 同じ文字同士をまとめるもの、ソートで可能。
- Counterの対象となるのは、数値や文字列を要素とするリストであり、リストを要素とするリストを引数に代入するとエラーが起きる。
- 組み合わせの総数を求める際、combination関数はmathモジュールにないので、自作する必要がある。
from collections import Counter
import math
def comb(n, r):
return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
A = sorted(["".join(sorted(input())) for _ in range(N)])
ctr = Counter(A)
ans = 0
for value in ctr.values():
if value >= 2:
ans += comb(value, 2)
print(ans)ABC138 C – Alchemist（ソート）
- 1回合成するごとに、元の具材の価値は半分になる。
- よって、価値の低いものから順に合成していけばよい。
N = int(input())
v = sorted(list(map(int, input().split())))
result = 0
for i in range(N - 1):
result = (v[i] + v[i + 1]) / 2
v[i + 1] = result
print(result)ABC139 C – Lower（最長減少部分列）
- 典型的な最長増加部分列を求める問題。
- 比較部分で「>=」「<=」の向きを変えるだけで、最長増加部分列を求めることもできる。
N = int(input())
H = list(map(int, input().split()))
dp = [0] * (N + 1)
dp[1] = 1
# 1つ手前の要素
h = H[0]
for i in range(2, N + 1):
# 現在見ている要素
tmp = H[i - 1]
if h >= tmp :
dp[i] = dp[i - 1] + 1
else:
dp[i] = 1
h = tmp
print(max(dp) - 1)詳しくは以下の記事をご覧ください。
【動的計画法】最長部分増加列を典型問題でマスターしよう（Python） | くまと梨 (kunassy.com)
ABC140 C – Maximal Value（min）
C – Maximal Value (atcoder.jp)
- B_0に対し、A_0, A_1を最大にする候補はA_0, A_1 = B_0
- B_1に対し、A_1, A_2を最大にする候補はA_1 = min(A_0 = B_0, B_1), A_2 = B_1
- B_i に対し、A_i, A_{i + 1}を最大にする候補はA_i = min(A_i, B_i), A_{I + 1} = B_i
といった順で値を決めていけばよい。
N = int(input())
B = list(map(int, input().split()))
A = [-1] * (N)
A[0] = B[0]
A[1] = B[0]
for i in range(1, N - 1):
A[i] = min(A[i], B[i])
A[i + 1] = B[i]
print(sum(A))ABC141 C – Attack Survival（分類無し）
C – Attack Survival (atcoder.jp)
- Ai 以外を-1するとO(N^2)。
- 相対的な関係を保持すればよいので、Ai のみ+1、最後に全要素を-Qとすればよい。
N, K, Q = map(int, input().split())
P = [K] * N
for _ in range(Q):
a = int(input())
P[a - 1] += 1
for p in P:
if p - Q > 0:
print("Yes")
else:
print("No")ABC142 C – Go to School（ソート）
- 教室にいる生徒数は単調増加する。
- A_iと出席番号をセットに、A_iの大きさ順でソートする。
N = int(input())
A = list(map(int, input().split()))
AA = []
for i in range(N):
AA.append([A[i], i + 1])
AA.sort()
AAA = [i[1] for i in AA]
print(*AAA)ABC143 C – Slimes（文字列の分割）
自分の提出 – AtCoder Beginner Contest 143
- 隣り合う文字が異なる箇所の数を数える。
- 何個に分割できるか、なので、最後に+1。
N = int(input())
S = input()
ans = 0
for i in range(N - 1):
if S[i] != S[i + 1]:
ans += 1
print(ans + 1)ABC144 C – Walk on Multiplication Table（整数論）
C – Walk on Multiplication Table (atcoder.jp)
- i * j = N となる(i, j) のペアを探すのは\(O(\sqrt{N})\)で可能。
- ペアは10^6個にも満たないので、それぞれに対して移動回数を求め、最小回数を更新していく。
import math
N = int(input())
pairs = []
for i in range(1, int(math.sqrt(N)) + 1):
if N % i == 0:
pairs.append([i, N // i])
ans = 10**12
for p in pairs:
ans = min(ans, p[0] + p[1] - 2)
print(ans) ABC145 C – Average Length（順列全探索）
C – Average Length (atcoder.jp)
全順列の出力方法
from itertools import permutations
N = int(input())
pairs = permutations([i for i in range(N)])
for i in pairs:
print(i)
# N = 5
>>
(0, 1, 2, 3, 4)
(0, 1, 2, 4, 3)
(0, 1, 3, 2, 4)
(0, 1, 3, 4, 2)
(0, 1, 4, 2, 3)
...- 訪れる町の順番を、全順列として列挙する。
- 各順列に対し、移動距離を求めていく。
from itertools import permutations
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
pairs = list(permutations([i for i in range(N)]))
summ = 0
# 全ペアについて調べる
for pair in pairs:
tot = 0
# ペアのj番目とj+1番目の間の距離を求めていく
for j in range(N - 1):
tot += ((xy[pair[j]][0] - xy[pair[j + 1]][0]) ** 2 + (xy[pair[j]][1] - xy[pair[j + 1]][1]) ** 2) ** .5
summ += tot
print(summ / len(pairs))ABC146 C – Buy an Integer（二分探索）
- 整数Nの大きさに対し、価格も単調に増加する。
- 単調性のある問題なので、二分探索法が使える。
- 二分探索のコンセプトは難しくないが、範囲の取り方や最終的な出力がややこしい。
A, B, X = (map(int, input().split()))
def binary_search(n, k):
# 探索範囲
left = 0
right = n
# 探索範囲を狭めていく
# leftはk以下の右端
# rightはkより大きくなる左端
while left + 1 < right:
# 探索範囲の中央
mid = (left + right)//2
#print(left, right)
# 中心の値は基準値以下か
if A * mid + B * len(str(mid)) <= k:
# a[0] ~ a[mid] は k 以下なので調べる必要が無い
left = mid
else:
right = mid
return left
ma = 10 ** 9 + 1
print(binary_search(ma, X))ABC147 C – HonestOrUnkind2（有向グラフ・ビット全探索）
C – HonestOrUnkind2 (atcoder.jp)
非常に勉強になった問題。
公式解説が分かりやすいが、C++での実装例なので、Pythonでの実装を完成させるのに苦労した。
- ２次元リストに、各人の証言を格納する。
- 各人に対し、1（正直者である）・０（不親切な人）の２つの状態が考えられるが、最大でN=15人しかいないため、ビット全探索が可能。
- 全ての状態について、ひとまずその状態が存在すると仮定する。（後で矛盾しないかも確かめるのでご安心を）
- ビットが１の人は、もしかしたら不親切な人かもしれないが、今回は「最大で何人の正直者が存在しうるか」を問われているので、親切な人であると仮定する。
- ある状態 st では、正直者である人の証言だけは正しくなければならない。よって、正直者と仮定された（st >> i & 1）すべての人 i について、彼らの証言と、仮定した状態が一致するかを確かめていく。
- 仮定した状態が、証言と矛盾していなければ、正直者の数を数える。
- 正直者の数の最大値を更新する。
N = int(input())
# 有向グラフ
# g[i][j]は、i番目の人によるj番目の人に対する証言
g = [[-1] * N for _ in range(N)]
for i in range(N):
A = int(input())
for j in range(A):
x, y = map(int, input().split())
g[i][x - 1] = y
ans = 0
# ビット全探索
# 全ての状態iを試していく
for st in range(1 << N):
flag = True
for i in range(N):
# 状態 st が正しいと仮定すると
# bitが1の人の証言は間違ってはいけない
# bitが0の人の証言は間違っていても良い
if (st >> i) & 1:
for j in range(N):
if g[i][j] == -1:
continue
if g[i][j] != (st >> j & 1):
flag = False
# 仮定した状態が、各人の証言と矛盾しない場合
if flag:
# 2進数で表した状態の内、bitが1の数を数える
ans = max(ans, bin(st).count("1"))
print(ans)ABC148 C – Snack（最小公倍数）
- 本当に、最小公倍数を求めるだけ。
- Python3.8では、最小公倍数を求める関数は自作する必要がある。
import math
A, B = map(int, input().split())
# 最小公倍数を求める関数
def lcm(a, b):
y = a * b // math.gcd(a, b)
return y
print(lcm(A, B))ABC149 C – Next Prime（素数）
X = int(input())
# X以上の数を試していく
for i in range(X,2*X):
# i より小さい数 j で割り切れるか
# j は 2 からi ** 0.5 だけ試せばよい
for j in range(2,int(i**.5)+1):
if i%j==0:
break
else:
print(i)
break次の記事
コメント