naoya_t@hatenablog

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

〈AGC埋め〉AGC B問題 (006-015)

暑いのでAGC埋め。
ABC/ARC/AGCの400点までの全問*1が埋まった。
f:id:n4_t:20180717023724p:plain

AGC 006 B - Median Pyramid Easy (400)

シミュレーションしながら
(x=1 または x=2N-1 のとき"No"なのはそもそもmedianに選ばれることがない数なので分かるんだけど)
30分考えて

解説読んだ

  • 隣接する2つが同じ数だと、その上の段でもその2つが並ぶ

なるほど
なるほどすぎる
自力で思いつけなかったのが悔しい

x+2が可能な小さいxなら、xを中心に置いて
... x+1,1,x,x+2 ...
不可能なら
... x-1,2N-1,x,x-2,...
とかやれば、上の段は
... ?,x,x,?,...
になるので、順に持ち上がって、上から二段目でxは過半数を得るので最上段はx

→AC
https://beta.atcoder.jp/contests/agc006/submissions/2854158

// 解説では x≠2のとき (...,x-1,x,x+1,x-2,...), x=2のとき (...,x+1,x,x-1,x+2,...)としていた

AGC 007 B - Construct Sequences (400)

とりあえず a1,a2,...,aN を等差数列にして(a_i=a_1+k(i-1))
bN,...,b2,b1も同様に等差数列にして (b_i=b_1-k(i-1))
この時点で全てのi(1\le i\le N)について a_i+b_i=a_1+b_1 になっている
これをいい感じにずらしていきたい。

配列d を考えて、[tex:a_i+b_i=a_1+b_1+d_i=d_i+const.] とすれば [tex:a_i+b_i] は d の順に並ぶ。

p=[2,3,1]のとき a2+b+,a3+b3,a1+b1の順に昇順になってほしいので、例えば d=[3,1,2] とする。(d[p[++i]]=++j的な操作)

あとは
a_i+b_i=a_1+b_1+d_i=d_i+const.
d_ia_i,b_iに振り分ければ良い。どちらかに全部乗せてもいいし、半分ずつ乗せてもいい。等差数列の等差(ここではk) がその最大上乗せ数を上回っていれば良い。

→WA 28'17
https://beta.atcoder.jp/contests/agc007/submissions/2854209
サンプルケースで落ちてるじゃん(実装ミス)
a[i]=a1+k(i-1)+d[i] になるべきところが a[p[i]]=a1+k(i-1)+p[i]/2 になっていた。

直して
→AC 35'36
https://beta.atcoder.jp/contests/agc007/submissions/2854229
思いついたのはいいんだけどもうちょい手際よく行きたい

解説解も同様。
等差数列のk、この問題の場合あまりギリギリに詰める必要はない。

AGC 008 B - Contiguous Repainting (400)

両端は1つ刻みで色分けできるけれど、途中の長さKの区間は白か黒にしか出来ない
どこにそのKの区間を取るか、を N-K+1 通り全部試せばいい。
先に累積和(正の数だけバージョン、無差別バージョン)を求めておけば1回ずつの試行はO(1)なのでO(N)で終わる。
→AC 17'06
https://beta.atcoder.jp/contests/agc008/submissions/2857480

解説解も同様

AGC 011 B - Colorful Creatures (400)

  • とりあえずa[]を昇順ソート
  • とりあえず累積和を求めておく
  • 自分の2倍以下の物は無条件に呑み込める
  • 飲み込んだ時点でその2倍より小さい数も呑み込める
  • i=0から
    • 2a_i以下の物をupper_boundで調べて(O(logN))、そこまでの累積和を取って
    • これを可能な限り繰り返して最後の1匹まで呑み込めるか
    • 最悪ケース...2倍ずつの等比級数とかだと1つあたりO(N)、全部でO(N^2)かかるのでは?
    • それは無理
  • 大きい方から(数学的帰納法っぽく)見て行ったほうが早そう
  • 最大の物 (i=N-1) は必ず全てを呑めるはず
    • i=kでそれ以上が全て呑めるとしてi=k-1のとき…
    • \sum_{k=0}^{k-1}\le 2a_k なら i=k-1でも全てを呑める
    • この計算は累積和のおかげで O(1)
    • 飲めなくなったら終わり
    • O(N)

→AC 13'52
https://beta.atcoder.jp/contests/agc011/submissions/2857522

解説解は左から見て飲み込めない最大をtとしてN-tが答え、みたいな数え方をしているけどかえってややこしい

AGC 015 - Evilator (400)

  • 直行できなくても最悪1FかN階で乗り換えれば行けるから最大2
  • N個のフロアからすべての行き先(N-1)通り:N(N-1)、それに乗り換えが必要な数
  • 2〜N-1階について、Uならその下すべて、Dならその上すべてが直行不能
  • 足すだけ

→WA(1) 7'25
https://beta.atcoder.jp/contests/agc015/submissions/2857571
ああN(N-1)をllキャストしてない
→AC 8'55(+penalty)
https://beta.atcoder.jp/contests/agc015/submissions/2857573

解説解も同様。

int x = 100000;
long long y = x * x;

みたいな事そろそろしないようになりたいんだけど...

*1:新スコア体系以降