naoya_t@hatenablog

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

AtCoder Regular Contest 082

まさかの三完
oo-o 1400pts 120th, 1465→1660 (+195)
f:id:n4_t:20170902230441p:plain:w360
今回のパフォーマンスは2347だった

このグラフだと分からないけど青の上って何?黄色?
(青→黄色→オレンジ→赤だった。400刻みなので黄色は2000から)

C - Together (300)

3つの操作のどれかをしてXになる数って X-1, X, X+1 の3つだし
それぞれの数がいくつあるか集計して、(0〜1e5の範囲で)連続する3つの数について和を取った最大。尺取り。
→AC (11'58)
https://arc082.contest.atcoder.jp/submissions/1559354

D - Derangement (400)

なんか似たような問題(これより易しいと思うんだけど)をさっきCodeChefで見たような気もしつつ
一旦飛ばしてEへ

みんなこれ結構短時間で解いてるし
もしかして難しく考え過ぎ?
左から見ていくとする
・a_i != i の場合、何もせず次へ
・a_i == i の場合、直後のやつと交換。直後のやつは i 以外の何かのはずだから、2つとも a_k != k になる
最後に1つ余っちゃう場合。最後の3つで場合分け。
(※最後の1つが交換必要な場合、単に直前のやつと交換することで解決するんだけど。直前が何であれ。)
→AC (50'09)
https://arc082.contest.atcoder.jp/submissions/1562079

E - ConvexScore (700)

このスコアって要するに2の(凸多角形が内包する点の数)乗だよね
0〜200(いや上限は197か)について2の累乗のMODを求めておいて
三角形が 200C3 個出来て、それぞれの角度を求めておく
ある1つの点を内包する凸多角形が何通りできるか求める
ってのをすべての点について求めて・・・いや1点ずつ求めた値からはどうにかなったりしないか
行き詰まってDに戻る
(解いてない)

F - Sandglass (700)

砂時計をひっくり返し続けるわけだけど
a_iがある範囲内の場合は最初からの平行移動
範囲外の場合はオーバーフローしてるから直近からの平行移動
みたいな感じで

区間 [0, X] を上げ下げして、床と天井にぶつかるたびに狭めていく。砂時計をひっくり返す時刻に、その区間が(平行移動を繰り返して)どこからどこに相当するかを求めておく。a_i がその区間の外側だった場合、床なり天井なりにぶつかっているので、その区間の移動後の上限なり下限なりに来ているはず。あとは砂時計を最後にひっくり返してから何秒経っているか。
そこまでの準備でO(K)、来たクエリのt_iから(二分探索で)直近を探すのにO(QlogK)。
計算自体のオーバーフローに気をつける(というかlong longで計算するというか)
→ AC (98:12... 残り108秒)
https://arc082.contest.atcoder.jp/submissions/1563623
余裕なくてテンプレコード消さずにsubmitしてた