naoya_t@hatenablog

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

diverta 2019 Programming Contest

atcoder.jp
5/11(土) 21:15-23:15
1ペナ4完で286位
終了12分前にEを提出したけれどジャッジが詰まっててそのまま終了
(結局TLEだったので4完のまま)
ジャッジ詰まりまくって結局unratedになった。(折角2000超えパフォだったので残念)

A - Consecutive Integers (100)

N-K+1
AC (pythonで) 1:27

B - RGB Boxes (200)

最初r,g,bをそれぞれ[0,R],[0,G],[0,B]の範囲で選ぶものと誤解していて
サンプルケースが合わなくて気づいた
r,gを総当たりして、辻褄の合うbがあるかを見るのでO(N^2/RG)
AC 8:48

C - AB Substrings (400)

  • 各部分文字列に含まれるABの個数を数える
  • 各部分文字列の先頭と末尾で4種類に分ける
    • ba: B.*A
    • bx: B.*[^A]
    • xa: [^B].*A
    • xx: [^B].*[^A]
  • baタイプは全部連結して(連結回数を数えた後)1つだけ残す。
  • xaとbxは1ペアでabを1つ作れる
    • xa-bxのペアが1つでもあるならbaをそこに差し込んで+1
    • xa-bxのペアが無いとき、xaかbxが1つあればbaとペアを組んで+1

AC 18:36

D - DivRem Number (500)

N=xm+xなのでN=x(m+1)

  • xは何かをmで割った余りなので[0\le x\lt m]
    • さらにN\neq 0なのでx\neq 0
    • 従って0\lt x\lt m
  • xを1から順に試す。
    • m=\frac{N}{x}-1が整数で(ということはNがxで割り切れて)、かつx\lt  mであれば。

→WA(1)
Nがxで割り切れなければcontinue; としていたのだけれど、ループの終了条件を横着したためにNが大きな素数の時に全部見るまで止まらなくてTLE…
適当な(\sqrt{N}+αの)終了条件を入れて
AC 34:49

E - XOR Partitioning (800)

()
終了12分前に提出したけれど、ジャッジが詰まっていて結果が出る前に終了

結局TLEだった
WAは出ていなかったので、考察自体は間違っていなかったのかなと(方針がいまいちだった)

F - Edge Ordering (1200)

開いてない