PAST6

■A - POSTal Code
s[3]とそれ以外で=='-' か!='-'

■B - PASTal Code
s[i * 4 + 1 ] == 'o'

■C - 携帯電話の購入
Bをsetで管理

■D - K項足し算
頭を削って、お尻を加える。

■E - 前から3番目
std::deque

■F - 安全装置
3ペナ
途中で安全装置に止められて、更に終わった瞬間にも安全装置に止められるケースを忘れていた。

■G - 一日一歩
Gにしては難しくない？
毎日毎日、到達したことのない頂点に到達できそうなら動く
使える辺の候補は、通行時間をkeyにしてpriority_queueで管理しておけば良い
priority_queueをwhileで回しながらpushをしてしまうと
一日に二歩動いてしまうのでwhileの外にvectorを保持しておき
whileを抜けたらしたらまとめてpush。

■H - カンカンマート
Gよりよっぽど簡単ですよね
同じ系統の缶詰なら安い方から買えばいいので
type0をi個、type1をm-i個を全てのiについて試せば良い。
缶切りのことも考慮した累積和を先に求めておく。

■I - 魚釣り
単純なdp
dp[i][j][k] :=(i,j)に来るまでにk匹魚を釣ったときの最大値

■J - ポイントとコストと
よく見るとただの２次方程式なので平方完成なり微分するなり。

■K - 共通クーポン
dp
少し難しい？
どの状態をまとめて持つかを考える。
購入金額をmod100でまとめ、その状態での最大値を考える
dp[i][j] := i個目まで見た、購入金額がmod100でjな購入金額の最大値。

■L - 都市計画
最小全域木
Mの制約が小さいから、全てのNと特定のMを使う2^M通り全てに対して最小全域木を行う。

■M - 等しい数
一番難しい。
嘘解放っぽいけど
{{l,r},x}で連続区間と要素を管理しておき必要な箇所のみ更新していく。
最悪ケースの計算量がこれで成立する理由がよくわからない。

■N - 活動
取る順番によって結果が変わる
しかし、不等式を作って整理するとa/bが大きいものから撮っていくのが最適だと言うことがわかる
なのでsortしてdp。

■O - 最短距離クエリ
実装が重い
M <= N+10なのでほとんど木
グラフから一部の辺を取り除いて木を作る
木の上での最短距離はLCAを使えば簡単に求まる。
問題は木に含まれない辺を経由するとき。
頂点u,vと辺の両端に含まれる頂点全てを取りだしダイクストラを行えば答えが出る。

ABC199

■A - Square Inequality
if ((a * a + b * b) < c * c)

■B - Intersection
max(0, minB - maxA + 1)

■C - IPFL
・遅い
string tmp = s0;
s0 = s1;
s1 = tmp;

・早い
s0.swap(s1);

■D - RGB Coloring 2
難しくないですか？これ。
未使用の点からdfsをし、連結グラフごとの訪問順番を決める
決めた順番に条件を満たすように頂点色を決めていく。
dfsと別に再帰関数用意しないとダメなんですね。

■E - Permutation
bitDP
立ってないbitを立てても条件を満たすなら遷移
立っているbitの数 = 処理した文字数になる

■F - Graph Smoothing
Dよりよっぽど簡単
サンプル１で考えると
3 = ((3 + 1)/2 + (3 + 5)/2)/2
3/2 = ((1 + 1)/2 + (3 + 1)/2)/2
9/2 = ((5 + 3)/2 + (5 + 5)/2)/2

1,3,5についている係数部分は入力で受け取ったものと関連しているので
行列が生えるので繰り返し二乗法

Dが難しかった。

ARC117

■A - God Sequence
基本的には
1,-1,2,-2,3,-3,,,,,,,とし
AとBの数が一致していないと和が0にならないので
最後に帳尻を合わせる。

■B - ARC Wrecker
sortして差+1の積

■C - Tricolor Pyramid
f(x,y) = -x-y(mod 3)とすればよい。
負のmodが面倒なら
f(x,y) = 2(x+y)(mod 3)としてもよい。(最後に2^(n-1)をかける必要があるが)
あとは、コンビネーションのmod3での剰余を求めればいいのですが
ここをライブラリに頼ろうとするも撃沈
3で何回割れるかと、それを無視したときのmod3での剰余を求めればいいが
普段modをaclに頼りきりのため、一部ミス。
このミスの位置を突き止めるのに大幅時間ロス。

■D - Miracle Tree
43秒間に合いませんでした。
木の直径にあたる部分以外を２回通るようなイメージでdfsすれば最小になりそう
なのでまずdfsを2回し、直径を求める。
最後に直径の一部となる経路は、後回しになるようにdfsしつつ、頂点を決めていけばいい

第二回日本最強プログラマー学生選手権

■A - Competition
(y * z - 1)/x

■B - Xor of Sequences
どうにでも

■C - Max GCD 2
区間[A,B]の間にその倍数のものが２つ以上あればいい

■D - Nowhere P
(p-1)*(p-2)^(n-1)
繰り返し二乗法

■E - Level K Palindrome
どことどこが同じになっていないといけないかを
unionfindを使って求める
最後に残るレベル０の回分は回文であってはいけないので
最善と次善を保持しておき、レベル０が回分になるようならば一つ次善にする必要がある

■F - Max Matrix
クエリを先読みし、座圧してセグ木して差分計算
セグ木は{sum,count}みたいな数で持つと良い。

■G - Spanning Tree
unionfindをしてA[i][j] = 1の頂点をまとめること
既に閉路ができてたらNGなことなどまでは簡単に思いつく。
ここからは自由辺をどの組み合わせで選ぶのかを考える必要がある。
行列木定理という答えに直結する定理が存在するので知っていれば貼るだけ。
知らないと無理

立ち回りを間違えた。
Fを先に解くべきだったし、Eも細かいミスだけだったので解けるべき

決勝内訳
東大25
京大8
阪大4
東工大3
東北大3
慶応2
早稲田1
福井1
横浜国立大学1

ABC198

■A - Div
N - 1

■B - Palindrome with leading zeros
stringで受け取って
後ろについているだけ、前に'0'をつける(後ろを削ってもいい)
reverseしたものと比較

■C - Compass Walking
コーナーケースにはまる。
x * R >= sqrt(x * x + y * y)
となる最小のxが答え。
ただしx = 1の時は例外。

■D - Send More Money
10!は全部試しても高々しれているので試す。

■E - Unique Color
dfsやるだけ。入る、出るの度に配列なりmultisetを更新すればいい。

■F - Cube
むっず！
ポリアの数え上げ定理を履修済みとする
正四面体の回転方法は24通りある
１：向かい合う面の中心を軸に90度,180度,270度回す、3*3ケース
２：向かい合う辺の中心を軸に180度回す、6ケース
３：向かい合う頂点を軸に120度、240度回す、2*4ケース
４：何もしない1ケース

それぞれの3+1+2+1の7ケースに対してどの面がどの面に移動するかを考え
回転しても一致するような面の状態を書き出す
すると
(1,1,1,1,1,1)*1
(2,2,2)*6
(3,3)*8
(1,1,2,2)*3
(1,1,4)*6
に分類される。
あとはコンビネーションを使って数えあげる

これ(1,2,3)みたいなのがあると、数え上げパートが面倒になるはず。。。

ABC-F略解(136-140)

■136:F - Enclosed Points(2334)
とりあえず図示してみる。
問題文を言い換えて、それぞれの頂点ごとに自分が含まれるような部分集合の場合の合計を求める。
自分自身が選ばれていれば残りのN-1個の頂点はどうでもいいので2^(N-1)が加算される
次に、自分自身が選ばれていない場合を考える。
他の点は、自分より右上右下左上左下のいずれかのゾーンに含まれる
①左上から一個以上、右下から一個以上選ぶ
②左下から一個以上、右上から一個以上選ぶ
のどちらかを満たしていれば自分自身が含まれる
ただし、①＋②だと右上右下左上左下全てのゾーンから一つ以上選んでいるケースが重複しているので
引く必要がある。

右上、左上、右下、左下の各要素はセグ木を２本持って管理しておき
forを回すごとに
①右から自分を外す
②計算する
③左に自分を入れる
を繰り返せばいい。

■137:F - Polynomial Construction
f(x) = 1-(x-t)^(p-1)
とおくと
x = t にてf(x) = 1;
それ以外でf(x) = 0;
これを加える。

■138:F - Coincidence
yの最上位bitを考える。
xの最上位ビットと一致してないとき
y xor x > x > y%x
となるため最上位ビットの位置が一致している必要がある。
また、このときyをxで割った商が1になるため
y - x = y xor x
となればいいことがわかる。
このための(x,y)の組み合わせは(0,0),(1,1),(0,1)のいずれか
あとは、桁dp
通常の桁dpと比較して２変数を同時に扱う必要がある。
以下のように状態を持つ。
dp[i][j][k][l]:=上からi桁見た,
j = 1 xがLより大きいことが確定している
k = 1 yがRより小さいことが確定している
l = 1 先頭ビッドがすでに現れた。

■139:F - Engines
制約を見るとNが小さいことがわかる。
図示して考察すると、連続する範囲を選択すればいいので
ソートして、全て試せば良い。
２周分持つのが鉄則。

■140:F - Many Slimes
貪欲。
注意すべきなのは
4,3,3,3,2,1,1,1
みたいなとき
4
4,3
4,3,3,2
4,3,3,3,2,1,1,1
のような場合でも問題がなく、単純に上からとれないとだめなわけではない。

ABC-F略解(131-135)

■131:F - Must Be Rectangular!(1937)
X座標、Y座標を二部グラフの問題と解釈し、unionfindで同グループの結ばれていない辺の個数が答え
類題：D - Skate(arc112)

■132:F - Small Products(2143)
状態をまとめて計算量を減らすdp

dp[i][j] := 最後がjで条件を満たす要素数iの数列
これだとO(NK)なのでtle

12の場合
{1}
{2}
{3}
{4}
{5,6}
{7,8,9,10,11,12}のように組分けをする。

{7,8,9,10,11,12}は{1}と
{5,6}は{1}と{2}と
{4}は{1}と{2}と{3}と連結が可能。このようにすると
O(√N * K)に落ちる

■133:F - Colorful Tree (2330)
uとvの距離は
(root,u) + (root,v)-2*(root,lca)で求められる
これをベースに拡張点を訪れたタイミングでその時点で
どの色にどれだけ距離と回数を使っているかを保持しておく
i問個目のクエリの
u,v,lcaのいずれかの箇所に来たらその情報をもとにAns[i]の一部を計算する。

■134:F - Permutation Oddness(2532)
dp[i][j][k]:=i組まで見た、j組がi組内で未マッチング。奇妙さがk
と持つ、答えはdp[N][0][K]

■135:F - Strings of Eternity(2388)
Sを十分な長さだけ連結し、
Tの部分列との一致箇所を探す。
startとendを結び、を繰り返し、roopが作られるならinf
そうじゃないならsize -1 が答え