Tenka1 Programmer Contest：D - Crossing
問題
解法
図を書いてみると，1 ~ N の数字を三角形状に並べられるものがよいと気づくので，N が三角数であれば Yes，そうでなければ No となる．
どのように部分列を構成するかというと，
N = 15 の場合では，三角形の三辺を囲い，その後頂点の位置にある数字以外の辺上の数字と囲まれた中の数字を使いながら部分列を作るといい（図を見た方が分かりやすい）．O(N)．
解答
N = 1 のときは三角形をなさないので，コーナーケースになる．
square869120Contest #4：C - Calendar 2
問題
解法
lcm(7, m) のマスは 0 のマスと塗られているかどうかは同じになるので，lcm(7, m) - 1 のマスまでマス目を塗るシミュレーションをすれば十分．縦 lcm(7, m) / 7 マス，横 7 マスの表を S と置く．S の下に新しく S をつけ足していくことを考える．この時，白いマスの連結個数は S の個数を k と置くと
a + d (k - 1)
で表される（故に等差で増えていく）．a は S 単独の白いマスの連結個数であり， d は S を上下に２つ繋げたものの白いマスの連結個数から S 単独の白いマスの連結個数を引けば求まる．それぞれ DFS をすれば求まる．k は n / ( (lcm(7, m) / 7) )．O(m)．
解答
解法がすぐに考え付いて，一発 AC 出来たのでよかった．
square869120Contest #5：C - Two Parentheses
問題
解法
A, B の "(" , ")" の数がそれぞれ |S| / 4 になっていればよい．S を先頭から見ていくとき，S を真ん中で半分にして考える．
前半分のとき，
- S_i == "(" で A の "(" が不足しているとき：A += "("
- S_i == "(" で A の "(" が不足していないとき：B += "("
- S_i == ")" で B の ")" が不足しているとき：B += ")"
- S_i == ")" で B の ")" が不足していないとき：A += ")"
A の "(" が不足していないときに A += "(" する，または，B の ")" が不足していないときに B += ")" すると A, B は「正しい括弧列」ではなくなる．なので，前者なら B += "("，後者なら A += ")" することによって回避できる．
後半分の時
- S_i == "(" で A の "(" が不足しているとき：A += "("
- S_i == "(" で B の "(" が不足しているとき：B += "("
- S_i == "(" でどちらも "(" が不足していないとき：終了
- S_i == ")" で B の ")" が不足しているとき：B += ")"
- S_i == ")" で A の ")" が不足しているとき：B += ")"
- S_i == ")" でどちらも ")" が不足していないとき：終了
前半分と同様の理由でこのような処理になる．どちらも不足していないのにまだ括弧があるときは， "(" または ")" の個数がそもそも正しくないので「正しい括弧列」は作れない．
このように貪欲をして，B の括弧を反転させて，A, B 両方が「正しい括弧列」であれば "Yes"，そうでなければ "No" を出力すればよい．O(Q|S|)．
解答
最初は怪しかった貪欲が意外と通ってしまった．
