naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉ARC 091 E - LISDL (700)

今夜もE問題に挑戦

考察

  • A+B-1 > N のときは無理
  • A≧Bとする(A<Bのケースは逆に作ってN+1から引く)
  • A×Bの四辺形の底(=45度傾けてる)から1; 2,3; 4,5,6; と埋めていって、上の行から印字するプラン
    • これだとA×B≧Nである限り行けそうな(本当にこれでうまく行くのか)
    • とりあえずサンプルケースは通るけど

→WA(1)
https://beta.atcoder.jp/contests/arc091/submissions/2741871

時間切れにつき解説読む

自分の考察は間違っていないんだけどバグりやすい。
解説解のように左から、下から上、下から上と埋めていく方がシンプルだし(それで十分なはずだし)計算量が少ない(自分の実装では300000 150001 150000とか来たらTLEになる)

とりあえず、WA実装で余りの処理が間違っていた箇所を直したものを提出
→WA(2) ; WA数は激減したものの、いくつかのTLEといくつかのWA(潰せていないコーナーケース有り)。

  • A*Bの領域の斜めスキャンで不要なところをスキップするようにして(TLE回避)

→WA(3) ; TLEは消せたけどWAが残ってる;

  • A*B<N判定がオーバーフローするのを直したり
  • スキップした先がa>=Aのときにバグってたのを直したりして

→AC
https://beta.atcoder.jp/contests/arc091/submissions/2742558
ふぅ

解説解の順番に埋めるやつも通した
→AC
https://beta.atcoder.jp/contests/arc091/submissions/2742600
まあ若干速い

教訓

正しく実装すれば答えは出る(がもっとシンプルに実装できる方針がきっとある)