abc173

NISHIO Hirokazu [Translate]
ABC173
やったー、緑になったよ！
今回は5問解けました

C問題
前回あまりに難しかったから今回のCもめちゃくちゃドギマギしてしまった
落ち着いて見直したらW, Hは最大6だったのでサイズが小さいから全探索できる
C++の人はビット全探索が好きだけどPythonではビット演算が軽くないから意味薄い
標準ライブラリitertoolsに列挙する系のイテレータが用意されてる楽チン
カウントする処理はNumpyで掛け算すればループがネイティブ速度で動く
itertools.productの出力がそのままベクトル扱いで行列に掛けられるので楽チン
 data = (data == 35) 
これでBoolの行列になる。演算時にはTrueは1、Falseは0になる
pythondef 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問題
pythondef 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)
ACしたが、コンテスト後にこの解説を書いていて(注)の部分にミスがあることに気づいた
場合わけ3が「解が正になるとき」を意味するか？
意味するのだとすると注2の場合わけは必要ないはず
意味しないのだとすると絶対値が大きくなるように計算してるのはおかしい
場合わけせずに「一番大きな数を掛ける」としてサブミットしたらAC
しかし手元のテストケースで正の数が残ってない旨のエラーになる
そもそも手元でエラーになったから場合わけを追加したのだ
9,9,-1,-1,-1から3個取る場合9,-1,-1が正しい
僕のコードではグリーディに9,9を選択しまう
これは9を1つだけ選択するのが正しい
次のステップで正の数が足りなくて-1,-1が選択される
つまり嘘解(正しい解ではないが、それを指摘するテストケースを運営が用意していなかったことによって正解とされてしまった解)
えっ、じゃあ緑になったこと喜べないのでは？

#atcoder