Codeforces Round #703 (Div. 2) 参加記
A(500) C1(750) E(2250) の3完。良問が多い回だった。
A - Shifting Stacks (500点)
英文読解の問題。
前の要素を自身より後ろの任意の場所に移動させられるという条件で、狭義単調増加を作れるかという問題。
B - Eastern Exhibition (1000点)
本番中にこれが解けないのはだめ。
いつも通り x, y を独立に考える。
すると数直線上にある1点を取って、他点との差の絶対値の和を最小にする問題になる。(中央値の性質の有名問題)ここまでこれば奇数なら中央値、偶数なら2つの中央値の間の任意の整数値が1方向の取り得る座標の値だとわかる。
C1 - Guessing the Greatest (easy version) (750点)
平方分割。
まず区間全体のsecond maxのindexを取得する。次にそのindexを含むように区間を狭めてクエリを投げてみて、second maxのindexが同じなら狭めた区間に最大値が存在し、異なるのならその区間に最大値はないことがわかるので対象区間が絞れる。これを繰り返せば解が求まる。
105 < 220 なので、同じ実装でC2も通ると考えたがWAだった。(どうしてこんなことに)
E - Paired Payment (2250点)
単純にグラフを再構築してダイクストラをする。これが初期値2250点はお得。
まとめ
#include <atcoder/all>
を消し忘れて開幕CEにならないようにする。