ABC173

やったー、緑になったよ！

https://gyazo.com/9c02c55f0b7706469c3858aa1e220e53

今回は5問解けました

https://gyazo.com/db2b82d6397bf11a9a0588dcaa21799a

C問題

前回あまりに難しかったから今回のCもめちゃくちゃドギマギしてしまった

落ち着いて見直したらW, Hは最大6だったのでサイズが小さいから全探索できる

C++の人はビット全探索が好きだけどPythonではビット演算が軽くないから意味薄い

標準ライブラリitertoolsに列挙する系のイテレータが用意されてる楽チン

カウントする処理はNumpyで掛け算すればループがネイティブ速度で動く

itertools.productの出力がそのままベクトル扱いで行列に掛けられるので楽チン

data = (data == 35)

これでBoolの行列になる。演算時にはTrueは1、Falseは0になる

code:python

def solve(H, W, K, data):

data = (data == 35)

ret = 0

for x in itertools.product((0, 1), repeat=W):

dX = data * x

for y in itertools.product((0, 1), repeat=H):

s = (dX.T * y).sum()

if s == K:

ret += 1

return ret

D問題

code:python

def solve(N, AS):

buf = []

AS.sort(reverse=True)

for i in range(N - 2):

return ret

こんな短いコードで本当にいいのか？と不安になりつつAC

コンテスト中に実際に書いた図

https://gyazo.com/fea759711c68351a4066d6f92db8a63e

「大きい順到着で本当に良いのかな…」

「グリーディでいいのかな…」

その二つを仮定して手で順番に試したら上記のとおりになった

1人目のスコアは0、2人目のスコアはA1、残りは2個ずつ足す

とりあえず提出して、WAだったらしっかり考えよう、と思ったらACだったので証明はしなかった

公式の解説PDFでなぜこれで良いのかの証明が書かれている

E問題

3通りに場合わけしてからグリーディ

場合わけ1、すべてを使う場合

選択肢はないので何も考えずに全部掛ける

場合わけ2、正数がなくKが奇数

この時、負数を奇数個掛けて結果が負になることが確定する

なので絶対値を小さくする

絶対値の小さい順に掛ける

場合わけ3、その他

「絶対値の大きい正の数を2つ掛ける」か「絶対値の大きい負の数を2つ掛ける」の大きい方をやる(注)

残り1個の場合はまだ正の数があるなら一番大きな正の数を掛ける、ないなら絶対値の小さい負の数を掛ける(注2)

ACしたが、コンテスト後にこの解説を書いていて(注)の部分にミスがあることに気づいた

場合わけ3が「解が正になるとき」を意味するか？

意味するのだとすると注2の場合わけは必要ないはず

意味しないのだとすると絶対値が大きくなるように計算してるのはおかしい

場合わけせずに「一番大きな数を掛ける」としてサブミットしたらAC

しかし手元のテストケースで正の数が残ってない旨のエラーになる

そもそも手元でエラーになったから場合わけを追加したのだ

9,9,-1,-1,-1から3個取る場合9,-1,-1が正しい

僕のコードではグリーディに9,9を選択しまう

これは9を1つだけ選択するのが正しい

次のステップで正の数が足りなくて-1,-1が選択される

つまり嘘解(正しい解ではないが、それを指摘するテストケースを運営が用意していなかったことによって正解とされてしまった解)

えっ、じゃあ緑になったこと喜べないのでは？