溜め込んだ振り返りをまとめて放出してます。
A - World Cup
やってみよう!
A
関数を完成させて「Run」ボタンをクリックしよう!(テストデータ省略)
自由欄
try
解説の通りに場合分けすればよいです。
結果:提出 #3366228
try2
ところで、登場する数字が0, 1, 2, 3だけで順番も規則性がありそうなので、場合分けせずにコーディングしたくなります。
コンテスト中は控えましたが、例えば以下。
結果:提出
try3
上の例も実質場合分けです。どうにか周期性を活かしたい。たとえば以下。
結果:提出 #33711196
他の人の回答
自分の頭で思いつのはこれくらいなので、他の人の回答を見てみます。
例えば、この記事を書いている時点でPythonによる最も短い回答はこんな感じ。
参照:提出 #33680595
意味が分からん😇
以下ちょっとした解説
4の倍数で切り捨て(&~3
)
ビット演算で「4の倍数で切り捨てる」には、例えば1byteだと11111100
(=0xFC
)との論理積を取ればいいです。
今回の問題では $2000 \le Y \le 3000$ なので12bitあれば足ります。
ところで、0xFFC
は5文字です。とても長いですね(?)。
あとバイト長とかを考えるのが面倒くさかったりします。
それらを同時に解決するのが(Pythonの)2の補数表現です。
2の補数ってなんだったっけ
Cなどの静的型付け言語を学び始めの頃、「オーバーフローに気をつけましょう」みたいなことを教わると思います。(それは学び始めに限らず要所要所で遭遇する厄介な問題だったりします。)
そして以下のようにオーバーフローさせて遊んだりしたと思います。
ここで、負の値の表現方法が2の補数です。
どういうことかと言うと、
2の補数とは、ある自然数を2進数(2進法)で表現した時に、足し合わせるとちょうど桁が一つ増える最小の数のこと。
2の補数とは - 意味をわかりやすく - IT用語辞典 e-Words
ということで、上の例で示した01111111
に対して10000001
がそのような数になっていることがわかります。
それはいいとして。
01111111
が127
なのは分かる。けど、なんで10000001
が-127
なのさ?と疑問が湧きます。
実際、10000001
は129
でしょうが!
そこらへんが静的型付けに所以するわけですが、「“符号付き”なら最初の1ビットが符号を表す」と決めた訳です。
「最初の1ビットが符号なら、127
(01111111
)のマイナスは11111111
で表現すればよくない?」と思いますが、2の補数は「足し合わせるとちょうど桁が一つ増える」ので、つまりオーバーフローして0
になるのです。
2の補数で表現しておけば、127 + -127 = 0
という自然な計算がそのまま実現できるわけですね。
という訳で、コンピューター上でマイナスの値を表現するためにちょうど都合が良いわけです。
ところで、なんでnumpy
使い出したの?
はい、だいぶ回り道してますがいよいよ佳境です。
「静的型付け」を表現するため、もっと言えばバイト長を明示するためにnumpy
を使って説明しました。
御存知の通り、Pythonの整数には精度の制限がありません。
「じゃあどうやって“符号付き”(最初の1ビット)を表現すんのさ?」となりますが、安心してください。ビット単位演算を行うことで、値の先頭を無限個の符号ビットで埋めたものとして結果が得られます。
どういうことか、もう一度以下の例を見てみます。
a
、b
両方とも、正の整数として無限個の0
ビットが頭についたものと考えます。
要は符号なし整数なのでa
は127、b
は129です。
ここで、a
をビット反転して1加算します。これで2の補数が求まります。
このとき、頭についた無限個の0
ビットも反転して1
になります。
するとどうなるか。
ちゃんとマイナスの値を出すことができました。
表示する範囲を広げると分かりやすいです。
なお、b
をそのままマイナスの値として扱いたい場合もビット演算で可能です。
これは以下のような処理を行っているからです。
無限個の符号ビット (...00000000000000)10000001: もとの値 (...00000000000000)11111111: 0xFF ---------------------------------------------------- (...00000000000000)01111110: 排他的論理和を取った (...11111111111111)10000001: ビット反転させた
ここでの内容は以下の記事を参照しました。
Python3での2の補数と~演算子(ビット反転)
(再)4の倍数で切り捨て(&~3
)
ようやく話を戻します。
何の話かというと、4の倍数で切り捨てたかったわけです。でも0xFFC
と5文字も打ちたくないのです。なんなら制約も考えたくないんです。
「5文字以内で...1111111111111100
って無限に表せたらいいのになぁ」
その願いを実現できます。そう、Pythonならね。
ここまで読んでくれた読者諸賢であればすんなり理解できるでしょう。3(11
)をビット反転する際、符号ビットも反転することで上のような結果となっています。
なお、以下でも同様の結果となります。
その他諸々
本来の問題に戻りましょう。直近の未来の4で割った余りが2の年を求めたいです。
単純に4の倍数で切り捨てて2を足すと、4で割って3余る年だけ過去年を求めてしまうことになります。
これは単純に1年分ずらせばいい、という訳でもとの回答になるわけですね。
あ~長かった…
自由欄
B - Triangle (Easier)
やってみよう!
B
関数を完成させて「Run」ボタンをクリックしよう!
自由欄
try
$N \le 100$なので、$_{N}C_{3}$を全探索しても余裕そうです。
という訳で力技の全探索。
結果:提出 #33670400
自由欄
try2
より無駄なくコーディングするとしたらこんな感じでしょうか。
結果:提出 #33795866
あんまり実行時間変わらんな。
自由欄
C - Min Max Pair
やってみよう!
C
関数を完成させて「Run」ボタンをクリックしよう!
自由欄
try
解説通りです。
結果:提出 #33674915
自由欄
D - I Hate Non-integer Number
やってみよう!
D
関数を完成させて「Run」ボタンをクリックしよう!
自由欄
try
さっぱり分かりませんでした。C問題までとの差よ…
コンテスト中は30分考えて諦めたのでさっそく解説を写経してみます。
結果:提出 #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
は出力を分かりやすくするためだけに使っています。
とりあえず2で割った場合(i=2
)を見てみましょう。
1周目
j=0
の実行によって、dp[1]
が確定しました。
つまり、[2]
から
- 0個選んで2で割ると、余りが0の選び方が1つ:
()
- 1個選んで2で割ると、余りが0の選び方が1つ:
(2)
を表しています。
2周目
j=1
の実行によって、dp[2]
が確定しました。
つまり、[2, 6]
から
- 0個選んで2で割ると、余りが0の選び方が1つ:
()
- 1個選んで2で割ると、余りが0の選び方が2つ:
(2), (6)
- 2個選んで2で割ると、余りが0の選び方が1つ:
(2, 6)
を表しています。
3周目
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つ選ぶ場合で考えます。
既に[1, 2, 3, 4]
までの結果が分かっているとします。
これに最後の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]
があるわけです。
try2
理解するのにかなりの時間を要しました…。DPムズい。
しかし理解してしまえばこっちのもの。
模範解答を効率化したのが以下。
k
を逆順に更新していくことで、3次元だったDP配列を2次元にすることができました。
j
毎に値をコピーする手間も省けて効率化できてるはず!
結果:提出 #34050987
大分実行時間に余裕を持ってACできました。
まとめ
振り返り甲斐のある回でした😅