■A - ドリンクバー
min(a + b - c, d)
■B - 積集合
setとかで
■C - 出現回数
if
■D - 約数
約数個数計算はライブラリ化しておくべき
■E - カラフルなTシャツ
適当に
■F - 不完全順列
- 1になるのは0が一つのとき
そうじゃないときは、適当に一つずらせばいい。
■G - K番目の要素
二分探索
■H - 最短経路
n回ダイクストラ
■I - /2 and *3
ひたすら割って、小さいものにどんどんかけていく
■J - 数列の反転
何処が何回ひっくり返されたかをBITで管理
■K - ニワトリのお見合い
最小費用流を出すには早くない?
sからpにそれぞれ辺を張って
qからtにそれぞれ辺を張る
pからqへはINF-(a[i] - b[i] + c[j] - d[j])とかで良い。
これだとp流そうとしても流せないケースがあるので、p->tも追加しておく。
■L - K番目の絶対値
二分探索
基本的にGと同じ。
尺取せずにlowerboundしてるので時間1100ms。
■M - バランス
まあまあ重実装枠だと思う。
yukicoderNo.1502 Many Simple Additions
がほぼ同じなので一発で解けた。
一要素を決めるとどんどん決まっていく
ある頂点をa+xとでも置くとそのとなりは
c-(a+x) = (c-a)-xとでもなる。
隣り合う頂点のxの符号が一致しない限りはxは未決定
一致するとxが決まる。
偶奇などでxが決めれない場合は当然NG
最後までxが決まらない場合は
条件の頂点に書かれた数は0以上を満たすようにxを決めればいい。
■N - ジグザグな数列
座圧してセグ木。セグ木は二本持つ。
Kと入れ替えていい。
■O - 色分けトーナメント
これ難しいよね?
トーナメントに矛盾があれば0
あとは適当に未決定の試合数をnとして
2^(n+1)