振り返りです。

KYOCERA Programming Contest 2022(AtCoder Beginner Contest 271) - 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 - 484558

やってみよう!

A関数を完成させて「Run」ボタンをクリックしよう!(テストデータ省略)

def A(N): pass print(A(99 )) # 63 print(A(12 )) # 0C print(A(0 )) # 00 print(A(255)) # FF

自由欄

try

フォーマット問題。
書式を全て覚えるのはムリなので、都度都度調べつつ慣れていくしかないですね。

参照)書式指定ミニ言語仕様

def A(N): return f'{N:02X}' print(A(99 )) # 63 print(A(12 )) # 0C print(A(0 )) # 00 print(A(255)) # FF

結果:#35272471

自由欄

B - Maintain Multiple Sequences

C - Manga

やってみよう!

C関数を完成させて「Run」ボタンをクリックしよう!

test_dataC = [ { "in":[6, [1, 2, 4, 6, 7, 271]], "out": 4 },{ "in":[10, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]], "out": 5 },{ "in":[1, [5]], "out": 0 },{ "in":[2, [3, 2]], "out": 1 },{ "in":[6, [1, 7, 7, 2, 4, 6, 271]], "out": 4 },{ "in":[1, [1]], "out": 1 },{ "in":[3, [1, 2, 2]], "out": 2 },{ "in":[4, [1, 1, 2, 2]], "out": 3 } ] def C(N, a): pass test_all(C)

自由欄

try(コンテスト中)

breakの場所を間違えて一度WAした後のAC

def C(N, a): a = set(a) i = 0 while True: if (i + 1) in a: N -= 1 else: N -= 2 if N < 0: break i += 1 return i test_all(C)

結果:#35307073

try(振り返り)

ループ回す回数を間違えて一度WAした後のAC。

なぜ毎度1回は間違えるんだ…!と考えたとき、ミスの場所は違っても結局は確認不足なんだと思い至りました。
サンプルでACしても、追加で境界値周辺のテストケースを作って確認することを心がけます・・・

def C(N, a): s = set(a) for i in range(1, N + 2): if i in s: N -= 1 else: N -= 2 if N < 0: break return i - 1 test_all(C)

結果:#36025002

自由欄

D - Flip and Adjust

やってみよう!

D関数を完成させて「Run」ボタンをクリックしよう!

test_dataD = [ { "in":[5, 25, [[2, 8], [9, 3], [4, 11], [5, 1], [12, 6]]], "out": "No" },{ "in":[3, 11, [[1, 4], [2, 3], [5, 7]]], "out": "Yes" },{ "in":[3, 11, [[4, 1], [3, 2], [5, 7]]], "out": "Yes" },{ "in":[4, 14, [[1, 4], [2, 3], [5, 7], [5, 8]]], "out": "Yes" },{ "in":[4, 14, [[1, 4], [2, 3], [5, 7], [8, 5]]], "out": "Yes" },{ "in":[4, 14, [[4, 1], [3, 2], [7, 5], [8, 5]]], "out": "Yes" }, ] def D(N, S, ab): pass test_all(D)

自由欄

try

「とりあえず数字の小さい方を上に向けた合計を初期値として、表と裏の差の部分和で$S-初期値$を作れればよいのでは?」という方針でググったら以下の記事を見つけました。安定のけんちょんさんです😁
典型的な DP (動的計画法) のパターンを整理 Part 1 ~ ナップサック DP 編 ~ - Qiita

上を参考にしたものの、コンテスト中はACならず。
振り返ってみると判定はOK、カードの置き方の例がダメダメだったので修正したのが以下。

def D(N, S, ab): target = S init = [] diff = [] for a, b, in ab: # a < b になるようにする if a >= b : a, b = b, a init.append(1) # 裏(T) else: init.append(0) # 表(H) target -= a diff.append(b - a) if target < 0: return "No" dp = [[0] * (target + 1) for _ in range(N + 1)] dp[0][0] = 1 for i in range(N): # print(diff[i]) for j in range(target + 1): dp[i + 1][j] |= dp[i][j] if j >= diff[i]: dp[i + 1][j] |= dp[i][j - diff[i]] # print(*dp, sep="\n") if not dp[-1][target]: print("No") return print("Yes") v = target for i, d in enumerate(diff[::-1]): if not dp[N - 1 - i][v]: init[N - 1 - i] ^= 1 v -= d print(*["T" if c else "H" for c in init], sep="") test_all(D)

結果:#36031218

try2

上の前に、自力で解いてみたのが以下。
「新たに作れる数のフラグ立てると、これまでに作れる数とごっちゃになっちゃってdpの辿り方が難しいなぁ~」ってことで19行目でコピーしてますが、上ではj >= diff[i]の場合にdp[i + 1][j] |= dp[i][j - diff[i]]とすることでそれを回避してるんですね。

う~む、なんか現時点でどちらもシックリきてないです…

def D(N, S, ab): target = S init = [] diff = [] for a, b, in ab: # a < b になるようにする if a >= b : a, b = b, a init.append(1) # 裏(T) else: init.append(0) # 表(H) target -= a diff.append(b - a) if target < 0: return "No" dp = [[1] + [0] * target] for d in diff: new = dp[-1].copy() for i in range(target): if dp[-1][i] and i + d <= target: new[i + d] = 1 dp.append(new) if not dp[-1][target]: print("No") return print("Yes") v = target for i, d in enumerate(diff[::-1]): if not dp[N - 1 - i][v]: init[N - 1 - i] ^= 1 v -= d print(*["T" if c else "H" for c in init], sep="") def D(*n): pass test_all(D)

結果:#36030811

自由欄

自由欄