ABC261の振り返り(A, B, C, D)

テスト関数定義↓

# 縮小表示 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 - Intersection

やってみよう！

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

test_dataA = [ {"in": [0, 3, 1, 5], "out": 2}, {"in": [0, 1, 4, 5], "out": 0}, {"in": [0, 3, 3, 7], "out": 0}, {"in": [0, 8, 3, 7], "out": 4}, # 一方が他方に含まれる場合 ] def A(L1, R1, L2, R2): pass test_all(A)

自由欄

try

なんか、A問題の割にむずくないですか…

問題の趣旨は2直線の重複範囲を求めよ、ということなんですが、場合分けが面倒です。
とりあえず始点にだけ着目して、先に始まる線をfirst、もう一方をsecondとします。

すると、firstの終点とsecondとの関係は以下の3パターンに分けられます。

firstの終点がsecondの始点より小さい

first : |---|
second:         |------|

firstの終点がsecondの始点より大きく、終点より小さい

first : |-----------|
second:         |------|

firstの終点がsecondの終点より大きい

first : |-------------------|
second:         |------|

3つの場合それぞれで回答すればよい、という訳で以下。

def A(L1, R1, L2, R2): first, second = (L1, R1), (L2, R2) if L1 > L2: first, second = second, first if first[1] < second[0]: return 0 if first[1] <= second[1]: return first[1] - second[0] second[1] second[0]< py-cell> test_all(A)

結果：AC　提出 #33490865 - AtCoder Beginner Contest 261

自由欄

解説を見る

結論から言えば、答えは $max(0,min(r1,r2)−max(l1,l2))$ で求める事ができ、これを知っていれば早いと思います。

解説 - AtCoder Beginner Contest 261

まじか。

def A(L1, R1, L2, R2): return max(0, min(R1, R2) - max(L1, L2)) test_all(A)

結果：AC　提出 #33490904 - AtCoder Beginner Contest 261

まじだった…

自由欄

try2

上の解法がスマートすぎて、なんだかむしゃくしゃして以下のような回答を考えました。
うん、きちゃない🤮

def A(L1, R1, L2, R2): return max(0, len(set(range(L1, R1 + 1)) & set(range(L2, R2 + 1))) - 1) test_all(A)

結果：提出 #33491253 - AtCoder Beginner Contest 261

自由欄

B - Tournament Result

やってみよう！

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

test_dataB = [ {"in": [4, ["-WWW", "L-DD", "LD-W", "LDW-"]], "out": "incorrect"}, {"in": [2, ["-D", "D-"]], "out": "correct"}, ] def B(N, A): pass test_all(B)

自由欄

try

これは設問通り実装すればいいですな。
setの妥当な使い道です笑

def B(N, A): pat = [set(["W", "L"]), set("D")] for i in range(N): for j in range(i + 1, N): if set([A[i][j], A[j][i]]) not in pat: return "incorrect" return "correct" test_all(B)

結果：提出 #33491823 - AtCoder Beginner Contest 261

自由欄

C - NewFolder(1)

やってみよう！

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

test_dataC = [ { "in": [5, ["newfile", "newfile", "newfolder", "newfile", "newfolder"]], "out": """newfile newfile(1) newfolder newfile(2) newfolder(1)""", }, { "in": [11, ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a"]], "out": """a a(1) a(2) a(3) a(4) a(5) a(6) a(7) a(8) a(9) a(10)""", }, ] def C(N, S): pass test_all(C)

自由欄

try

時間にシビアな問題です。

普通に考えたらdictに入れていけばいいんでしょうけど、それでいいのか…？
もっと高速化しなければいけないのでは！？

という訳で二分探索するようにしてみました。

from bisect import bisect_left as bisect def C(N, S): St = ["{"] C = [None] ret = [] for s in S: idx = bisect(St, s) if s == St[idx]: C[idx] += 1 ret.append(f"{s}({C[idx]})") else: St.insert(idx, s) C.insert(idx, 0) ret.append(f"{s}") return "\n".join(ret) test_all(C)

結果：TLE... 提出 #33466247 - AtCoder Beginner Contest 261

自由欄

try2

やっぱりdictなのか！？
でもin演算子は二分探索より早いのか！？！？

という訳でtry ~ exceptで実装

def C(N, S): St = {} ret = [] for s in S: try: St[s] += 1 ret.append(f"{s}({St[s]})") except Exception: St[s] = 0 ret.append(s) return "\n".join(ret) test_all(C)

結果：AC 提出 #33468127 - AtCoder Beginner Contest 261

自由欄

try3

in演算子でも普通に早かった。

def C(N, S): St = {} ret = [] for s in S: if s in St: St[s] += 1 ret.append(f"{s}({St[s]})") else: St[s] = 0 ret.append(s) return "\n".join(ret) test_all(C)

結果：AC 提出 #33492321 - AtCoder Beginner Contest 261

自由欄

D - Flipping and Bonus

やってみよう！

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

test_dataD = [ { "in":[6, 3, [2, 7, 1, 8, 2, 8], [[2, 10], [3, 1], [5, 5]]], "out": 48 },{ "in":[3, 2, [1000000000, 1000000000, 1000000000], [[1, 1000000000], [3, 1000000000]]], "out": 5000000000 }, ] def D(N, M, X, CY): pass test_all(D)

自由欄

try

コンテスト中は30分くらい時間があったのですが、全く分かりませんでした😇

という訳でさっそく解説を見ます。
・・・なるほど、分からん！

とりあえず実装してみたのが以下。(こんな短いんか…)

def D(N, M, X, CY): ''' 解説参照 ''' X = [None] + X b = [0] * (N + 1) for c, y in CY: b[c] = y dp = [[0] * (N + 1) for _ in range(N + 1)] for i in range(1, N + 1): for j in range(1, i + 1): dp[i][j] = dp[i-1][j-1] + X[i] + b[j] dp[i][0] = max(dp[i-1][:i]) ans = 0 for i in range(N + 1): ans = max(ans, dp[N][i]) return ans test_all(D)

結果：提出 #33494080 - AtCoder Beginner Contest 261

自由欄

解説を理解する

なにも考えず写経してACを確認したところで、ちゃんと考えてみます。
dpを返すようにした下のD_debug関数で確認してみましょう。

def D_debug(N, M, X, CY): ''' 解説参照 ''' X = [None] + X b = [0] * (N + 1) for c, y in CY: b[c] = y dp = [[0] * (N + 1) for _ in range(N + 1)] for i in range(1, N + 1): for j in range(1, i + 1): dp[i][j] = dp[i-1][j-1] + X[i] + b[j] dp[i][0] = max(dp[i-1][:i]) ans = 0 for i in range(N + 1): ans = max(ans, dp[N][i]) return dp

dpは以下のようになっています。

import numpy as np from pprint import * N, M, X, CY = test_dataD[0]["in"] pp(np.array(D_debug(N, M, X, CY)))

dp[1][1]からの対角成分が、全ての試行で表が出た場合の各時点での獲得金額となっているのがわかります。

# 全ての試行で表が出た場合の各時点での獲得金額 import pandas as pd X = np.array(X) Bonus = np.zeros(len(X), dtype=int) C, Y = np.array(CY).T Bonus[C-1] = Y df = pd.DataFrame( data= [X, Bonus, (Bonus + X).cumsum()], index=["通常獲得", "ボーナス", "計(累計)"], columns=range(1, len(X) + 1)) df

もう一度ちゃんと解説を読んでみると、dp[i][j]においてjは「現在のカウンタの数値がjである」ことを表しているとのこと。

ふむふむ。これで対角成分の↘の動きはわかりました。

次に、対角成分より左下の下三角部分を見てみましょう。
この部分でも↘の動きは同様で、iの通常獲得金額とjのボーナスを累計していくことは分かるのですが、問題はその始点、つまりdp[i][0]の値です。

「現在のカウンタの数値が0である」ということは、その回の試行では裏が出たことを表しています。
ここで確認ですが、今考えているのは任意にコイントスの表裏を操作して獲得金額を最大化するといくらになるか、ということです。
そして通常獲得とボーナスの組み合わせによっては、どこかで裏を出すことでそれを達成することができる場合もあるわけです。

さて、i回目のコイントスで裏を出すことで獲得金額を最大化できるとしましょう。
その場合、i回目の獲得金額はi - 1回目までの考えられる獲得金額のうち、最大のもの設定すればよいです。
それをやっているのが12行目ということなんですね。

賢いっ！

実際、このケースでは3回目で裏を出すことで最大金額を得られます。
いや～、なんというか脱帽です。

まとめ

DPの練習しなきゃ…