naoya_t@hatenablog

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

AtCoder Regular Contest 100

7/1 20:30-22:10(通常より30分早いスタート)

ARCの記念すべき第100回。
先週オフィスでMacBookを落として画面が縞々(修理待ち)なので代替機で参戦。
(問題読んでからatomをダウンロードしたりとか)

2完(oox-)210位。パフォ1994でレーティング1780→1805。1級に上がった。
f:id:n4_t:20180702000824p:plain:w500
f:id:n4_t:20180702000448p:plain

C - Linear Approximation (300)

  • abs(a_i - (b+i)) = abs(b - (a_i - i))
  • b=0で-1, b=a_i-iでの折返しで+2するimosを書き始めそうになる(1e9あるし無理)
  • ああ、これabsの和だから真ん中辺りに必ず最小値が来るやつだ。頂点数が奇数なら真ん中、偶数なら真ん中2つのどちらか(てか両方同じはずなんだけど)でOK
    • これを「典型」と思えたのは嬉しい。 (\/の重ね合わせだからね。微分を考えれば分かる話)
  • atom(エディタ)インストール済だと思ってたんだけど消えてて再ダウンロード
  • 書いて
  • 自動でビルド&チェックしてくれるスクリプトpythonで自作したやつ)が動かない。ライブラリが足りない。
  • まあいい。人力でチェックした

→AC
https://beta.atcoder.jp/contests/arc100/submissions/2768058

D - Equal Cut (600)

  • とりあえず2:2に割って(1箇所ずつ全部試して間に合う、か)
  • それぞれをできるだけ均等に1:1に割って
    • lower_boundで探した
  • 最小と最大の差を見て(その最小値が答え)

→AC
https://beta.atcoder.jp/contests/arc100/submissions/2771789

lower_boundの所は尺取りにすればさらに速い(&賢い)ね

E - Or Plus Max (700)

考察

やるべきことは見える

  • 2^N要素のpriority_queue的なものを用意
  • i=1〜2^N-1 について
    • iの立っているビットの0個以上をunsetしたものすべて、にa_iを放り込む
    • キューのi番目の上位2件の和を表示

但し、これでは間に合わないからどうにかしたい
(ここまでは良かった)

自分の実装

  • 18ビット分のpriority_queue的なものを用意
  • i=1〜2^N-1 について
    • iの立っているbitそれぞれのキューにa_i を放り込む
    • iの立っている各bitのキューから最大を持ってきて、あとa_0も見て、上位2つの和を求める
    • そこまでの最大値と比べて大きい方

→WA(1) 終了5分前に投げた
https://beta.atcoder.jp/contests/arc100/submissions/2776456

サンプルケース(と実テストケースの前半分)はこれでも通っちゃうんだよね
i=5のa_i(キュー4とキュー1に入ってる)をi=6(キュー4とキュー2を参照する)では使えないんだからそりゃWAだろう
解説には「これは、高速ゼータ変換の要領で、高速に行うことができます。」とある。

高速ゼータ変換・高速メビウス変換の辺り、先週の習得すべき手法キューに入ってるけど(PCトラブルなどもあって)さらってない。理解があやふやなので押さえておきたい。

F - Colorful Sequences (1100)

開いてない