AtCoder Grand Contest 038

競技プログラミング

結果

順位   514th / 2032
パフォーマンス   1663
レーティング  1916 → 1893(-23)

　ペナルティが重たくのしかかる。再びmerom氏にレート抜き返されてしまった。

A - 01 Matrix

　さっぱりわからなくてやばかった。58分かけて8WAの後に通すことができたけどこれは致命傷。

　最終的には

  1. H行のうち、0が A個である行が i行、 W - A個である行が H - i行とする。同じように列に関しても0が B個となる列が j列として i, jを全探索する
  2. 行の数式から考えて1を立てる数と、列の数式から考えて1を立てる数が一致するi, jを見つける。
  3. 各列が必要とする1の数をstd::priority_queueに詰めていく
  4. 各行が必要とする1の数だけ上で作ったpriority_queueから取り出していき、そこへ1を書き込んで（各列が必要とする1の数を一つ減らして）priority_queueに詰め直す

　というやり方で解いた。3以降でこういうことをやらずに左上から貪欲に詰めていくと

5 5 2 2

でダメになりWAを連発したので七面倒臭いことをやらなければいけなかった。

　解説PDFを見て、これはどう思いつけば良いのかさっぱりわからない。あまりにもきついA問題だった。

　提出

B - Sorting a Segment

　これは見てすぐ端の関係だけ考えれば良さそうという感じでセグメント木を二つ持って、あとはソートしてもなにも起きない場合を考えて無理やり通した。A問題よりよっぽど簡単。

　提出

C - LCMs

　コンテスト中はさっぱりわからなかった。解説を見て、頭が良すぎる！ という印象。しかし値の上限が小さめであることには気づいて良かったな。普通に考えて解けるわけない問題なんだからそういうところに目が行かないのはちょっと感覚が悪かった。

　解説の内容をコードに翻訳するような形で通したけど、約数列挙を O(\sqrt{n})でやると余裕でTLEだし、強い人たちの会話

を見て「なるほどstd::vectorに突っ込んで行けばよいのか」と思ってやったらそれもTLEだし、直接 wを構築しているときに上手いことやるということが必要だった。こういうの本番中に解ける気がしない。

　提出