やったー、緑になったよ！
C問題
- 前回あまりに難しかったから今回のCもめちゃくちゃドギマギしてしまった
- 落ち着いて見直したらW, Hは最大6だったのでサイズが小さいから全探索できる
- C++の人はビット全探索が好きだけどPythonではビット演算が軽くないから意味薄い
- 標準ライブラリitertoolsに列挙する系のイテレータが用意されてる楽チン
- カウントする処理はNumpyで掛け算すればループがネイティブ速度で動く
- itertools.productの出力がそのままベクトル扱いで行列に掛けられるので楽チン
data = (data == 35)- これでBoolの行列になる。演算時にはTrueは1、Falseは0になる 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
https://atcoder.jp/contests/abc173/submissions/14993373
D問題 python
def solve(N, AS):
buf = []
AS.sort(reverse=True)
ret = AS[0]
for i in range(N - 2):
ret += AS[1 + i // 2]
return ret
- こんな短いコードで本当にいいのか？と不安になりつつAC
- コンテスト中に実際に書いた図
- 「大きい順到着で本当に良いのかな…」
- 「グリーディでいいのかな…」
- その二つを仮定して手で順番に試したら上記のとおりになった
- 1人目のスコアは0、2人目のスコアはA1、残りは2個ずつ足す
- とりあえず提出して、WAだったらしっかり考えよう、と思ったらACだったので証明はしなかった
- 公式の解説PDFでなぜこれで良いのかの証明が書かれている
E問題
- 3通りに場合わけしてからグリーディ
- 場合わけ1、すべてを使う場合
- 選択肢はないので何も考えずに全部掛ける
- 場合わけ2、正数がなくKが奇数
- この時、負数を奇数個掛けて結果が負になることが確定する
- なので絶対値を小さくする
- 絶対値の小さい順に掛ける
- 場合わけ3、その他
- 「絶対値の大きい正の数を2つ掛ける」か「絶対値の大きい負の数を2つ掛ける」の大きい方をやる(注)
- 残り1個の場合はまだ正の数があるなら一番大きな正の数を掛ける、ないなら絶対値の小さい負の数を掛ける(注2)
- 場合わけ1、すべてを使う場合
- ACしたが、コンテスト後にこの解説を書いていて(注)の部分にミスがあることに気づいた
- 場合わけ3が「解が正になるとき」を意味するか？
- 意味するのだとすると注2の場合わけは必要ないはず
- 意味しないのだとすると絶対値が大きくなるように計算してるのはおかしい
- 場合わけせずに「一番大きな数を掛ける」としてサブミットしたらAC
- しかし手元のテストケースで正の数が残ってない旨のエラーになる
- そもそも手元でエラーになったから場合わけを追加したのだ
- 9,9,-1,-1,-1から3個取る場合9,-1,-1が正しい
- 僕のコードではグリーディに9,9を選択しまう
- これは9を1つだけ選択するのが正しい
- 次のステップで正の数が足りなくて-1,-1が選択される つまり嘘解(正しい解ではないが、それを指摘するテストケースを運営が用意していなかったことによって正解とされてしまった解) えっ、じゃあ緑になったこと喜べないのでは？
- 場合わけ3が「解が正になるとき」を意味するか？