2020-07-11
【Python】エイシング プログラミング コンテスト 2020 解説
リアルタイムでは参加できなかったので, バチャコンで参加. 結果はぎりぎり4完. コンテストであれば1400位くらいの成績でしょうか.
Pythonでの解答・解説を載せます.
疑問点・不明点など, ページ最下部のお問合せもしくはTwitterからメッセージいただければ回答いたします.
A - Number of Multiples
全探索してもいいし, 一発で求めることも可能.
L, R, d = map(int, input().split())
print(R // d - L // d + (L % d == 0)) # Lがdの倍数のケースを考慮
B - An Odd Problem
下記の性質を利用する.
- マスの番号とマスに書かれた整数がともに奇数 マスの番号 * マス書かれた整数 が奇数
N = int(input())
A = map(int, input().split())
cnt = 0
for i, a in enumerate(A):
if ((i + 1) * a) % 2:
cnt += 1
print(cnt)
Pythonicに書くなら、リスト内包表記を使ってこんな感じか.
N = int(input())
A = map(int, input().split())
print(sum(((i + 1) * a) % 2 for i, a in enumerate(A)))
C - XYZ Triplets
の範囲で全探索する.
僕の回答では若干遠回りして計算量を減らしている.
(こんなことをしなくてもACできるのでやらないほうがよい.)
の対称性に注目して, の条件で探索する.
from math import sqrt
# x, y, zの組合せ数を算出する
# 例えば (x, y, z) = (1, 1, 3)だったら, 3通りのバリエーションが存在する.
# (1, 1, 3), (1, 3, 1), (3, 1, 1)
def check(i, j, k):
cnt = set([i, j, k])
if len(cnt) == 1:
return 1
if len(cnt) == 2:
return 3
if len(cnt) == 3:
return 6
N = int(input())
ans = [0] * N
R = int(sqrt(N))
for x in range(1, R + 1):
for y in range(x, R + 1):
for z in range(y, R + 1):
f = (x ** 2) + (y ** 2) + (z ** 2) + (x * y) + (y * z) + (z * x)
if f <= N:
ans[f - 1] += check(x, y, z)
print(*ans, sep='\n')
D - Anything Goes to Zero
ここ最近のDの中では一番難しかった.
この問題の解法は、大雑把に言えば以下の2つのパートに別れる.
- (10進表記)のとき, を求めよ.
- (10進表記)のとき, を求めよ.
で本質的には同じ関数の値を算出するにも関わらず、両者で異なるアルゴリズムが求められる. これが難しさの主な要因だろう.
まず1について.
- がとてつもなく大きいため, 単純な割り算すらできない.
- そこで, に注目して, を算出する. (は2進表示での下位番目の数 )
- の個数をとすると, となる. これはで求められる.
- この考え方を拡張して, を求めるために, , を事前に算出しておく. (累積和と似た考え方)
2について.
- 定義通りに算出すればOK.
- メモ化再帰を使うとさらに高速に.
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 6)
# 解法パート2
def dfs(n):
if memo[n] >= 0:
rst = memo[n]
else:
tmp = n
one = 0
while tmp > 0:
one += tmp & 1
tmp >>= 1
m = n % one
rst = 1 if m == 0 else 1 + dfs(m)
memo[n] = rst
return rst
N = int(input())
X = list(map(int, list(input())))
one = Counter(X)[1]
# 解法パート1の前処理.
# Xがオール0のとき, 1が一つしか含まれないとき、を場合分けする
if one > 1:
Sm = 0
mm = one - 1
tm = 1
for i in range(N - 1, -1, -1):
tm %= mm
if X[i] == 1:
Sm += tm
Sm %= mm
tm *= 2
Sp = 0
mp = one + 1
tp = 1
for i in range(N - 1, -1, -1):
tp %= mp
if X[i] == 1:
Sp += tp
Sp %= mp
tp *= 2
memo = [-1] * (2 * (10 ** 5) + 10)
memo[0] = 0
# f(Xi)を求めていく処理
# 解法パート1とパート2を順に適用する
for i in range(N):
# 解法パート1
if X[i] == 0:
m = (Sp + pow(2, N - 1 - i, mp)) % mp
elif one > 1:
m = (Sm - pow(2, N - 1 - i, mm)) % mm
else: # X[i] == 1 かつ 全体で1が一つしかない 場合 は必ず0になる
print(0)
continue
cnt = 1
# 解法パート2
cnt += dfs(m)
print(cnt)
E - Camel Train
考察の難易度は低いが, 時間内に解くとなるとかなり難しそう.
考え方は以下の通り. 想定解答とは逆の考え方(点数を極力減らさない並べ方)をした.
まず、ラクダを3つのグループに分ける. 1: , 2: , 3: .
グループ3はどこに配置しても答えは変わらないため考察不要.
以下、グループ1について考察する.
- グループ1のラクダは極力左側に配置してあげると点数が高くなる. 最大で となる可能性があるが, 実際はより右側に配置されたラクダの分、点数が だけ小さくなる.
- では、どのような場合により右側に配置されるラクダが存在するのか?
- 例えば、{のラクダが頭}の場合、どちらか1頭はより右側に配置される. { が 頭, が 頭}の場合は3頭中の1頭, { が 頭, が 頭}の場合は4頭中の2頭, etc…
- つまり, 以下のラクダが頭存在する場合, 頭は右側に配置されるのである.
- では次に、どのラクダを右側に配置するべきか?
- これは点数の減少幅がもっとも小さいラクダ、すなわち が小さいラクダを右側に配置すべきである.
- グループ2についても同様に, 極力右側に配置して, どのラクダが左側に溢れてしまうかを考える.
import sys
from heapq import heappop, heappush
T = int(input())
for t in range(T):
N = int(input())
left, right = [], [] # left: グループ1, right: グループ2
ans = 0
for i in range(N):
K, L, R = map(int, sys.stdin.readline().split())
if L > R: # グループ1
ans += L
left.append((K, L - R))
elif L < R: # グループ2
ans += R
right.append((K, R - L))
else: # グループ3
ans += L
# グループ1について計算
pool = [] # Kiより左側に配置されるラクダの集合. L-Rの小さい順に格納される.
left.sort() #Kiの順にソート
cur = 0
pos = 1 # 左からpos番目以下のラクダについて計算
while cur < len(left):
# Ki <= pos のラクダをすべてpoolに格納する
while cur < len(left) and left[cur][0] == pos:
k, d = left[cur]
heappush(pool, d)
cur += 1
# pool内のラクダがpos頭を超えている場合, 一部のラクダは右側に配置される. その分だけ答えが減る.
while len(pool) > pos:
d = heappop(pool)
ans -= d # 答えがLi-Riだけ小さくなる
pos += 1
# グループ2について計算
pool = []
pos = N
right.sort(reverse=True)
cur = 0
while cur < len(right):
while cur < len(right) and right[cur][0] == pos:
k, d = right[cur]
heappush(pool, d)
cur += 1
while len(pool) > N - pos:
d = heappop(pool)
ans -= d
pos -= 1
print(ans)
F - Two Snuke
TBA
関連記事最新記事
2021-05-09【Python】AtCoder - 30代社会人が始めて1年半で青色になりました
2021-04-12【Python】ABC198 解説
2021-03-27【Python】ABC197 解説
2021-03-20【Python】ABC196 解説
2021-03-13【Python】ABC195 パナソニックプログラミングコンテスト 解説