Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

AGC016-C 「+/- Rectangle」 (700)

よく分からなかったけど通った(ア)。

概要

以下を満たす H \times W行列を存在すれば構築せよ。

  • 各要素は -10^9以上 10^9以下の整数である。
  • 全要素の総和は正である。
  •  h \times w行列を任意に切り取ったとき、その要素の総和は負である。

制約

  •  1 \leq h \leq H \leq 500
  •  1 \leq w \leq W \leq 500

解説(?)

この問題について考えたとき、まず「負の数はできるだけ部分行列間で共有させたい」となる。

そこで、以下のような2つの方法を考えた。

  1. 部分行列の一番右下だけ大きい負数にする
  2. 部分行列で共有される部分全体を負数にし、右下を大きくして無理やり総和を-1にする

文で説明するより、画像で説明した方が100倍わかりやすいだろう。

f:id:misteer:20180914002237p:plain

しかし、これら2つはどちらも10個弱のWAが出てしまう。

具体的に何がいけないのか考えていたが、ジャッジを見て「WAになったケースが1つも被っていない」ことに気づいてしまう。 これに気づけばやることは1つ、2つの解法をマージすることである。当然ながら全ケース通ってACとなった(最悪)。

ちなみに十中八九嘘解法なので実装例は貼りません。見たい方はこちらをどうぞ。

感想

  • 多分本番でも解法マージはやけくそでやったと思う。
  • 正直誰かにHackしてほしい。

追記

phwinxさんの解説を見たところ、パターンAで問題ないのだが正の要素が1では小さすぎたらしい。そこで正の要素1000に増やすと無事通った。そこが原因とは微塵も思わなかった。

ちなみにパターンBも正解なのだが、こちらは正の要素が30000と大きすぎて負の要素が -10^9を下回ったためにWA扱いになっていた。これは正の要素を3000に下げることで無事ACとなった。めでたしめでたし。

提出コード(パターンB)