stick xor 余談
作文に関する余談など.有用な解説についてはyukicoderの解説ページを参照してください.
制約
- 元々何も考えずN=50だった
- visalizerに非操作回数表示を実装したら結構重なっていたのでN=60にした
- 長方形の面積は平均すると13くらいになる.500個与えられるので,約6500マスを反転できる・させられる.
- N=50だと2500マスなので1マス2.6回程度.
- 意外と多い気がしたのでN=60,3600マスにして1マス1.8回程度に調整した.
嘘高速化
解説2の「すべての配置パターンを試し,最良の場所に配置する」の高速化
愚直にやるとO(NL)だけれども,競プロerならO(N)にしてしまうはず
- 累積和
- スライド最小値
- など
N = 60,各セルは2状態しか持たないので,1行をint64_tで保持できる
- ビットマスク・ビットシフト等を使えば早くなりそう
実装してみたら逆に遅くなった
- 60*60のintがキャッシュに乗るため?キャッシュの具体的な感覚がつかめていないので分からない・・・
負のスコア
- 入力のセルのデータを反転させると,スコアを最小化する問題に変わる.
- yukicoderでは最大スコアを記録するので,潜伏したり*1,一度きりの最小記録を狙ったり.
ライツアウトっぽい
- すべての長方形の長さをNに固定した問題を考える.つまりL_i = Nとする.
- すると,「K回行・列の状態を反転させて点灯数を最大化せよ」といったライツアウトっぽい問題になる.
問題タイトル
- 元はstick and xorだったが公開直前になんとなくstick xorにした
実行時間制限
- Javaの方ごめんなさい
- 10ケース10秒だと平等に近づくかも.
- 実行サーバが1~2個なので,1つの提出に掛ける時間を30秒くらいにしたかった
- リジャッジの可能性もあるので.
日数
- DMで2時間~1日言ってましたごめんなさい
- 1日だったら50K点超えは無かったので助かりました・・・
さいごに
2018/06/02 追記
QRコードっぽいという話を聞いたので(writer解の精度では読み取れない…)
*1:初期writer解を変動させないために使っていました