buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

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解の精度では読み取れない…)

https://i.gyazo.com/3b118229e116e3aad91966ccfad78250.png

*1:初期writer解を変動させないために使っていました