問題 atcoder.jp 解法 まずT,S,Z型は使えません. また，O型はそれ単体で横の長さが2の長方形になので必ず求めたい長方形に含めることができます. 結局I,J,L型の組み合わせを考えればいいです.同じ型を２つ組み合わせることで横の長さが4の長方形ができます.(…

問題 beta.atcoder.jp 解放 DPを使いましょう。 dp[i][j] を上からicm目まで横棒を引いたとき左からj本目の縦棒に行くあみだくじの数とします。 こうするとdp[H][K]が答えになります。 最初は1本目の縦棒にいるのでdp[0][1] = 1です。 正しいあみだくじの条…

問題 C - /\/\/\/ 解法 偶数番目の要素からなる数列をeven、奇数番目の要素からなる数列をoddとすればそれぞれの数列での最頻値even_1、odd_1に書き換えれば良さそうなことに気がつく。しかし問題の制約からeven_1 ≠ odd_1でないといけない。そこで、それぞ…

問題 C - 二人のアルピニスト / Two Alpinists 解法 まずのとき答えはになる。そうでないときを考える。のときである事がわかる。このとき、でないと条件に矛盾する。同じようにのときであり、このときでないと条件に矛盾する。かつのとき山の高さはであれば…

問題 C - Chocolate Bar 解法 分割の方法は4パターンある(解説pdf)。4パターンそれぞれを全探索して調べる。1つの長方形を決めると残りの2つは余っている長方形を均等に分けるのが良い。 結局の時間計算量で解ける。 #include <iostream> using namespace std; typedef</iostream>…