コドフォにデビュー
ところでレートはいつ変動するんですか？
result:oooooo-
■A. Polycarp and Sums of Subsequences
0<=a<=b<=cの時
a<=b<=c<=a+c
b<=a+b,b+c,a+b+cが成り立つので
最小のものがa,次に小さいものがb,最大のものがa+b+cとなる
■B. Missing Bigram
適当につないで最後に調整をする。
■C. Paint the Array
偶数(奇数)番目のGCDを割り切る奇数(偶数)番目の要素が存在すれば良い。
■D. Array and Operations
とりあえずソートして
サンプル１
1,1,1,1,1,2,3
1+(1/1)+(1/2)+(1/3)=2
足される要素は当然小さいものを使いたい。
floor(a/b)はa<=bなら0,1になるのでできるだけ0にしたい
後ろをa0,a1,a2,,,,,an-1,b0,b1,b2,,,,,bn-1
として組み合わせれば良い。
■E. Singers' Tour
a+3b+2c=x
2a+b+3c=y
3a+2b+c=z
のような形が与えられるのでa,b,cについて解けといっている
掃き出し法を使うと当然間に合わない。
式ごとの差分を見る
a-2b+c=y-x
a+b-2c=z-y
-2a+b+c=x-z
見通しを良くするために変形すると
a+b+c-3b= y-x
a+b+c-3c= z-y
a+b+c-3a= x-z
となるのでa+b+cがわかればa,b,cがわかるので解ける。
■F. Reverse
初期状態で一致しているときは別に処理をするとして
0をくっつけると反転する。
1をくっつけると反転させて1を頭につけることになる。
つまり
after = 1.....1before1......1
after = 1.....1reverse(before)1......1
なら作れる。
ただし初期状態が0で終わっているときに1ターン目に0をくっつけるときは場合分けが必要。
■G. Trader Problem
実装が面倒。
グラフの問題に帰着される。
サンプル１でいうと
10,12,14,15,18,30,31とあって
k=2だと
10-12-14-15,18,30-31とつながるので
10->14,15->15,30->31となり60になる。
ということをdsu使って頑張ればいい。
priority queueつかってやろうとすると流石に間に合わないので
累積和を使って上手に行えばいい。
