溜め込んだ振り返りをまとめて放出してます。

AtCoder Beginner Contest 262 - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoderAtCoder Inc.
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 - World Cup

A - World Cup

やってみよう！

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

test_dataA = [ {"in": [2022], "out": 2022}, {"in": [2023], "out": 2026}, {"in": [3000], "out": 3002}, ] def A(Y): pass test_all(A)

自由欄

try

解説の通りに場合分けすればよいです。

def A(Y): d, m = divmod(Y, 4) if m == 0: return Y+2 elif m == 1: return Y+1 elif m == 2: return Y elif m == 3: return Y+3 test_all(A)

結果：提出 #3366228

try2

ところで、登場する数字が0, 1, 2, 3だけで順番も規則性がありそうなので、場合分けせずにコーディングしたくなります。
コンテスト中は控えましたが、例えば以下。

def A(Y): return Y + [2, 1, 0, 3][Y % 4] test_all(A)

結果：提出

try3

上の例も実質場合分けです。どうにか周期性を活かしたい。たとえば以下。

def A(Y): return Y + 3 - (Y + 1) % 4 test_all(A)

結果：提出 #33711196

他の人の回答

自分の頭で思いつのはこれくらいなので、他の人の回答を見てみます。
例えば、この記事を書いている時点でPythonによる最も短い回答はこんな感じ。
参照：提出 #33680595

def A(Y): return (Y+1&~3)+2 test_all(A)

意味が分からん😇
以下ちょっとした解説

4の倍数で切り捨て(&~3)

ビット演算で「4の倍数で切り捨てる」には、例えば1byteだと11111100(=0xFC)との論理積を取ればいいです。

print(f'{62 & 0xFC=}') print(f'{63 & 0xFC=}') print(f'{64 & 0xFC=}') print(f'{65 & 0xFC=}')

今回の問題では $2000 \le Y \le 3000$ なので12bitあれば足ります。

hex(0b111111111100) print(f'{2022 & 0xFFC=}') print(f'{2023 & 0xFFC=}') print(f'{3000 & 0xFFC=}')

ところで、0xFFCは5文字です。とても長いですね(?)。
あとバイト長とかを考えるのが面倒くさかったりします。

それらを同時に解決するのが(Pythonの)2の補数表現です。

2の補数ってなんだったっけ

Cなどの静的型付け言語を学び始めの頃、「オーバーフローに気をつけましょう」みたいなことを教わると思います。(それは学び始めに限らず要所要所で遭遇する厄介な問題だったりします。)

そして以下のようにオーバーフローさせて遊んだりしたと思います。

import numpy as np a = 2**7 print(f'{a} ±2') for i in range(a-2, a+3, 1): print(f'{i}: {np.int8(i):4}') print() a = -a print(f'{a} ±2') for i in range(a-2, a+3, 1): print(f'{i}: {np.int8(i):4}')

ここで、負の値の表現方法が2の補数です。

print(" 127: ", np.binary_repr(np.int8(127), width=8)) print("-127: ", np.binary_repr(np.int8(-127), width=8))

どういうことかと言うと、

2の補数とは、ある自然数を2進数（2進法）で表現した時に、足し合わせるとちょうど桁が一つ増える最小の数のこと。
2の補数とは - 意味をわかりやすく - IT用語辞典 e-Words

ということで、上の例で示した01111111に対して10000001がそのような数になっていることがわかります。
それはいいとして。
01111111が127なのは分かる。けど、なんで10000001が-127なのさ？と疑問が湧きます。

実際、10000001は129でしょうが！

0b10000001

そこらへんが静的型付けに所以するわけですが、「“符号付き”なら最初の1ビットが符号を表す」と決めた訳です。

a = 0b10000001 print("符号なし：", np.uint8(a)) print("符号付き：", np.int8(a))

「最初の1ビットが符号なら、127(01111111)のマイナスは11111111で表現すればよくない？」と思いますが、2の補数は「足し合わせるとちょうど桁が一つ増える」ので、つまりオーバーフローして0になるのです。

a = 0b01111111 b = 0b10000001 np.int8(a + b)

2の補数で表現しておけば、127 + -127 = 0という自然な計算がそのまま実現できるわけですね。
という訳で、コンピューター上でマイナスの値を表現するためにちょうど都合が良いわけです。

ところで、なんでnumpy使い出したの？

はい、だいぶ回り道してますがいよいよ佳境です。
「静的型付け」を表現するため、もっと言えばバイト長を明示するためにnumpyを使って説明しました。

御存知の通り、Pythonの整数には精度の制限がありません。
「じゃあどうやって“符号付き”(最初の1ビット)を表現すんのさ？」となりますが、安心してください。ビット単位演算を行うことで、値の先頭を無限個の符号ビットで埋めたものとして結果が得られます。

どういうことか、もう一度以下の例を見てみます。
a、b両方とも、正の整数として無限個の0ビットが頭についたものと考えます。

要は符号なし整数なのでaは127、bは129です。

a = 0b01111111 b = 0b10000001 a, b

ここで、aをビット反転して1加算します。これで2の補数が求まります。
このとき、頭についた無限個の0ビットも反転して1になります。
するとどうなるか。

_a = ~a + 1 print(f'{_a}:', np.binary_repr(_a, width=8))

ちゃんとマイナスの値を出すことができました。
表示する範囲を広げると分かりやすいです。

print(f' {b}:', np.binary_repr(b, width=16)) print(f'{_a}:', np.binary_repr(_a, width=16))

なお、bをそのままマイナスの値として扱いたい場合もビット演算で可能です。

~(b ^ 0xFF)

これは以下のような処理を行っているからです。

 無限個の符号ビット
(...00000000000000)10000001: もとの値
(...00000000000000)11111111: 0xFF
----------------------------------------------------
(...00000000000000)01111110: 排他的論理和を取った
(...11111111111111)10000001: ビット反転させた

ここでの内容は以下の記事を参照しました。
Python3での2の補数と~演算子(ビット反転)

(再)4の倍数で切り捨て(&~3)

ようやく話を戻します。
何の話かというと、4の倍数で切り捨てたかったわけです。でも0xFFCと5文字も打ちたくないのです。なんなら制約も考えたくないんです。

「5文字以内で...1111111111111100って無限に表せたらいいのになぁ」

その願いを実現できます。そう、Pythonならね。

np.binary_repr(~3, width=32)

ここまで読んでくれた読者諸賢であればすんなり理解できるでしょう。3(11)をビット反転する際、符号ビットも反転することで上のような結果となっています。
なお、以下でも同様の結果となります。

np.binary_repr(-4, width=32)

その他諸々

本来の問題に戻りましょう。直近の未来の4で割った余りが2の年を求めたいです。
単純に4の倍数で切り捨てて2を足すと、4で割って3余る年だけ過去年を求めてしまうことになります。

print((1999 & ~3) + 2) # 2002が正解 print((2000 & ~3) + 2) print((2001 & ~3) + 2) print((2002 & ~3) + 2) print((2003 & ~3) + 2) # 2006が正解 print((2004 & ~3) + 2)

これは単純に1年分ずらせばいい、という訳でもとの回答になるわけですね。
あ～長かった…

print((1999 + 1 & ~3) + 2) print((2000 + 1 & ~3) + 2) print((2001 + 1 & ~3) + 2) print((2002 + 1 & ~3) + 2) print((2003 + 1 & ~3) + 2) print((2004 + 1 & ~3) + 2)

自由欄

B - Triangle (Easier)

B - Triangle (Easier)

やってみよう！

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

test_dataB = [ { "in":[5, 6, [[1, 5], [4, 5], [2, 3], [1, 4], [3, 5], [2, 5]]], "out": 2 },{ "in":[3, 1, [[1, 2]]], "out": 0 },{ "in":[7, 10, [[1, 7], [5, 7], [2, 5], [3, 6], [4, 7], [1, 5], [2, 4], [1, 3], [1, 6], [2, 7]]], "out": 4 }, ] def B(N, M, UV): pass test_all(B)

自由欄

try

$N \le 100$なので、$_{N}C_{3}$を全探索しても余裕そうです。

という訳で力技の全探索。

from itertools import combinations def B(N, M, UV): edge = [[] for _ in range(N+1)] for u, v in UV: edge[u].append(v) edge[v].append(u) ans = 0 for a, b, c in combinations(range(1, N+1), 3): if b in edge[a] and c in edge[b] and a in edge[c]: ans += 1 return ans test_all(B)

結果：提出 #33670400

自由欄

try2

より無駄なくコーディングするとしたらこんな感じでしょうか。

def B(N, M, UV): edges = [[] for _ in range(N + 1)] for u, v in UV: edges[u].append(v) ans = 0 for a in edges: for b in a: for c in edges[b]: if c in a: ans += 1 return ans test_all(B)

結果：提出 #33795866

あんまり実行時間変わらんな。

自由欄

C - Min Max Pair

C - Min Max Pair

やってみよう！

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

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

自由欄

try

解説通りです。

def C(N, a): a = [None] + a pat = 0 same = 0 for i in range(1, N+1): if a[i] == i: same += 1 elif a[a[i]] == i: pat += 1 return same * (same-1) // 2 + pat // 2 test_all(C)

結果：提出 #33674915

自由欄

D - I Hate Non-integer Number

D - I Hate Non-integer Number

やってみよう！

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

test_dataD = [ { "in":[3, [2, 6, 2]], "out": 6 },{ "in":[5, [5, 5, 5, 5, 5]], "out": 31 }, ] def D(N, a): pass test_all(D)

自由欄

try

さっぱり分かりませんでした。C問題までとの差よ…
コンテスト中は30分考えて諦めたのでさっそく解説を写経してみます。

def D(N, a): mod = 998244353 ans = 0 for i in range(1, N + 1): dp = [[[0] * i for _ in range(i + 1)] for _ in range(N + 1)] dp[0][0][0] = 1 for j in range(N): for k in range(i + 1): for l in range(i): dp[j + 1][k][l] += dp[j][k][l] if k != i: dp[j + 1][k + 1][(l + a[j]) % i] += dp[j][k][l] ans += dp[N][i][0] ans %= mod return ans test_all(D)

結果：提出 #33798524

時間ギリギリAC…

自由欄

解説を理解する

コードを追っても面白いぐらい理解できません😇

ここでは愚直に小さい部分に分解して理解することを試みます。

何を実現しているか

解説とコードを読んで分かったことといえば、$\textbf{i}$が割る数を表していることと、$\textbf{j}$が着目する配列の(先頭からの)項数を表している、ということです。

まぁ解説でがっつり明記されている訳ですが、

$dp[j][k][l]$ : $A$の先頭$j$項から$k$個の項を選ぶ方法であって、選んだ項の総和を$i$で割った余りが$l$となるようなものの個数

23 行目が$a_j$を選ばない場合に、24 行目が$a_j$を選ぶ場合に対応

実際のアウトプットを確認しながら、「何を実現しているか」を把握します。

ここでは以下のデバッグ用関数を用意しました。
引数としてi(割る数)を取り、jをループする度にdpを返します。

なおnumpyは出力を分かりやすくするためだけに使っています。

from pprint import * import numpy as np def D_debug(N, a, i): dp = np.zeros((N+1, i+1, i), dtype=int) dp[0][0][0] = 1 for j in range(N): print(f'{j=}') for k in range(i + 1): for l in range(i): dp[j + 1][k][l] += dp[j][k][l] if k != i: dp[j + 1][k + 1][(l + a[j]) % i] += dp[j][k][l] # print(f"{i=}, {j=}, {k=}, {l=}") # print(dp) yield dp[:j+2] test_dataD[0]["in"]

とりあえず2で割った場合(i=2)を見てみましょう。

j = D_debug(*test_dataD[0]["in"], 2)

1周目

print(next(j))

j=0の実行によって、dp[1]が確定しました。
つまり、[2]から

  • 0個選んで2で割ると、余りが0の選び方が1つ: ()
  • 1個選んで2で割ると、余りが0の選び方が1つ: (2)

を表しています。

2周目

print(next(j))

j=1の実行によって、dp[2]が確定しました。
つまり、[2, 6]から

  • 0個選んで2で割ると、余りが0の選び方が1つ: ()
  • 1個選んで2で割ると、余りが0の選び方が2つ: (2), (6)
  • 2個選んで2で割ると、余りが0の選び方が1つ: (2, 6)

を表しています。

3周目

print(next(j))

j=2の実行によって、dp[3]が確定しました。
つまり、[2, 6, 2]から

  • 0個選んで2で割ると、余りが0の選び方が1つ: ()
  • 1個選んで2で割ると、余りが0の選び方が3つ: (2), (6), (2)
  • 2個選んで2で割ると、余りが0の選び方が3つ: (2, 6), (2, 2), (6, 2)

を表しています。

この結果から、dp[3][2][0]が「2つ選んだ平均が整数(2で割って余りが0)」の組み合わせの数となります。

何を実現しているかのかが大体分かってきました。
改めてdpの構造の説明を引用します。

$dp[j][k][l]$ : $A$の先頭$j$項から$k$個の項を選ぶ方法であって、選んだ項の総和を$i$で割った余りが$l$となるようなものの個数

$l$から考えてみると、$i$で割った余りのパターンは0からi-1のi個なので、dp[j][k]の配列長もiとなります。
$k$は組み合わせる項数で、今回は平均が知りたいため0からiのi+1パターンがdp[j]の配列長となります。
$j$は上の説明の通り$A$の先頭から何項見るかを表していて、0も含めてdp[j]の配列長はN+1となります。

このように、割る数(i)毎にdpを作成して、最終的に「選んだ項の平均値が整数である組み合わせの数」を求めているのですね。

どのように実現しているか

何を実現しているかは分かりました。
しかし、肝心の実装部分の考え方がまだ分かりません。

コードを見ると、dp[j-1]の情報だけからdp[j]が確定されているのが分かります。

[1, 2, 3, 4, 5]という数列から3つ選ぶ場合で考えます。

j = D_debug(5, list(range(1, 6)), 3) for _ in range(5): dp = next(j)

既に[1, 2, 3, 4]までの結果が分かっているとします。

print(dp[-2])

これに最後の5を加えるとどうなるか。

まず5を一つだけ選ぶ場合…は一旦飛ばして、5を含めて2つ選ぶ場合を考えます。

1つ選んで余りが0のパターンが1つあるので、5を加えて3で割ると余りは2です。
⇨2つ選んで余が2のパターンに1を加えます。

1つ選んで余りが1のパターンが2つあるので、5を加えて3で割ると余りは0です。
⇨2つ選んで余が0のパターンに2を加えます。

1つ選んで余りが2のパターンが1つあるので、5を加えて3で割ると余りは1です。
⇨2つ選んで余が1のパターンに1を加えます。

こんな処理を行っているのが以下の部分というわけですね。
dp[j + 1][k + 1][(l + a[j]) % i] += dp[j][k][l]

で、5を一つだけ選ぶ場合は1つ選んで余りが2のパターンを1つ加えるだけですが、上の処理を同様に適用するためにdp[j][0]の[1, 0, 0]があるわけです。

print(dp[-1])

try2

理解するのにかなりの時間を要しました…。DPムズい。

しかし理解してしまえばこっちのもの。
模範解答を効率化したのが以下。

kを逆順に更新していくことで、3次元だったDP配列を2次元にすることができました。
j毎に値をコピーする手間も省けて効率化できてるはず！

def D(N, a): mod = 998244353 ans = 0 for i in range(1, N + 1): dp = [[0] * i for _ in range(i + 1)] dp[0][0] = 1 for j in range(N): for k in range(i-1, -1, -1): for l in range(i): dp[k + 1][(l + a[j]) % i] += dp[k][l] ans += dp[i][0] ans %= mod return ans test_all(D)

結果：提出 #34050987

大分実行時間に余裕を持ってACできました。

まとめ

振り返り甲斐のある回でした😅

自由欄