振り返りです。
LINE Verda Programming Contest(AtCoder Beginner Contest 263) - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
def test_all(f):
for i, data in enumerate(eval(f'test_data{f.__name__[0]}')):
exp = data["out"]
ans = f(*data["in"])
result = "AC" if exp == ans else "WA"
print(f"{i+1} {result}: expected: {exp}, output: {ans}")
A - Full House
A - Full House
やってみよう!
A
関数を完成させて「Run」ボタンをクリックしよう!
test_dataA = [
{
"in":[[1, 2, 1, 2, 1]],
"out": "Yes"
},{
"in":[[12, 12, 11, 1, 2]],
"out": "No"
}
]
def A(n):
pass
test_all(A)
自由欄
try
こんな感じ。
def A(n):
s = set(n)
if len(s) == 2 and n.count(s.pop()) in [2, 3]:
return "Yes"
else:
return "No"
test_all(A)
結果:提出 #33856906
自由欄
解説
解説 ではソートを利用した方法が紹介されています。
なるほどなぁ~
def A(n):
n = sorted(n)
if (
n[0] == n[1] and n[2] == n[4] or
n[0] == n[2] and n[3] == n[4]
):
return "Yes"
else:
return "No"
test_all(A)
自由欄
B - Ancestor
B - Ancestor
やってみよう!
B
関数を完成させて「Run」ボタンをクリックしよう!
test_dataB = [
{
"in":[3, [1, 2]],
"out": 2
},{
"in":[10, [1, 2, 3, 4, 5, 6, 7, 8, 9]],
"out": 9
},
]
def B(N, P):
pass
test_all(B)
自由欄
try
ちょっと設問を理解するのに時間が掛かりました。
入力の形式までしっかり確認しないとですね。
def B(N, P):
P = [None, None] + P
gen = 0
now = N
while now != 1:
now = P[now]
gen += 1
return gen
test_all(B)
結果:提出 #33814353
自由欄
C - Monotonically Increasing
C - Monotonically Increasing
やってみよう!
C
関数を完成させて「Run」ボタンをクリックしよう!
test_dataC = [
{
"in":[2, 3],
"out": """1 2
1 3
2 3"""
},{
"in":[3, 5],
"out": """1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5"""
},
]
def C(N, M):
pass
test_all(C)
自由欄
try
以下でBuf
やreturn
はこの記事用です。
combinations
をプリントするだけです。
from itertools import combinations
class Buf():
def __init__(self): self.s = ""
def write(self, s): self.s += s
def C(N, M):
buf = Buf()
for com in combinations(range(1, M+1), N):
print(*com, file=buf)
return buf.s[:-1]
test_all(C)
結果:提出 #33817810
自由欄
解説
解説 をちょっと修正してジェネレーターにしたのが以下。
def gen_set(N, K, A=[]):
if len(A) == K:
yield A
return
if len(A) == 0:
start = 1
else:
start = A[-1] + 1
for i in range(start, N + 1):
yield from gen_set(N, K, A + [i])
def C(N, M):
buf = Buf()
for com in gen_set(M, N):
print(*com, file=buf)
return buf.s[:-1]
test_all(C)
結果:提出 #33939686
自由欄
D - Left Right Operation
D - Left Right Operation
やってみよう!
D
関数を完成させて「Run」ボタンをクリックしよう!
test_dataD = [
{
"in":[5, 4, 3, [5, 5, 0, 6, 3]],
"out": 14
},{
"in":[4, 10, 10, [1, 2, 3, 4]],
"out": 10
},{
"in":[10, -5, -3, [9, -6, 10, -1, 2, 10, -1, 7, -15, 5]],
"out": -58
},
]
def D(N, L, R, A):
pass
test_all(D)
自由欄
解説
今回はコンテスト終了後に自力ACできたのですが、解説 でその考え方をめちゃくちゃスマートに体現 されていたので、先にご紹介します。
正直、解説は全く理解できてませんが、コードは至ってシンプル。それがこちら。
def D(N, L, R, A):
ans = R * N
acc = 0
for i in range(N):
acc = min(acc + A[i], L * (i + 1))
ans = min(ans, acc + R * (N - 1 - i))
return ans
test_all(D)
結果:提出 #33940848
try
で、コンテスト後に自力ACしたというのがこれ。
なにやら累積和を作る前処理をしたり、それを使った値の計算であったり、複雑そうなことをしていますが、実はやってることは上の解説のコードと全く一緒です。
自力ACできて嬉しい!という感情のあとに、同じことを実現するのにこんなにも差が出るものかという徒労感で心が揺さぶられました。
とりあえず線形探索するなら累積和の前処理しなくてもいい場合がある、ってことは覚えとこうと思います。
import numpy as np
def D(N, L, R, A):
filledL = np.cumsum([0] + [L] * N)
A = A[::-1]
acc = np.cumsum([0] + A)
filledR = np.cumsum([0] + [R] * N)
# 各項の値が大きいほど、置き換え後の総和は小さくなる
# processed[0]は0で一つも置き換えない(y = 0)ことを意味する
processed = acc - filledR
# 全てLで置き換える(x = N, y = 0)
ans = filledL[N]
# 0 <= x < N
better_y = 0
for x in range(N-1, -1, -1):
i = N - x
if processed[i] > processed[better_y]:
better_y = i
ans = min(ans, filledL[x] + filledR[better_y] + acc[i] - acc[better_y])
return ans
test_all(D)
結果:提出 #33852104
自由欄
まとめ
組み合わせの生成とかをPythonのライブラリに頼ってたけど、実装できるようになりたいなぁ(願望)
自由欄