D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder またも面白い問題。 トポロジカルソートに注意しすぎた。でも N の小ささを見れば大抵 bit DP だとわかる。 dp( S ) : number of valid topological sorted array for S and the restrictions given int…

D: いろはちゃんとマス目 / Iroha and a Grid - AtCoder Beginner Contest 042 | AtCoder シンプルでいい問題。 左下の塊上一つの行を右に沿って枚挙するだけ。答えはその塊の右上のセルからその行に沿って右に行く途中加算する 始点からそこに着く方法数 * …

D: アンバランス / Unbalanced - AtCoder Beginner Contest 043 | AtCoder A real nice trick problem. Since it is only asks whether in some contiguous range one particular character appeared more than half of the length, we are to realize that …

D: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder The key is to observe that only staying in one city will maximize the profit, because if staying in two is better, we will still arrange all time on the higher-price city. We wil…

Problem - B - Codeforces I thought this was a little difficult for pB. Observe and we will find that we want to know whether there exist at least two pairs of ( a, b ) and ( a', b' ), where both a indicates y value on x1, b indicates y val…

D: 画像処理高橋君 - AtCoder Beginner Contest 039 | AtCoder Greedy で出来るだけ多く置いてみる。最後に一致するかどうかをみてみる。 const int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 }; const int dy[] = { 1, 0, -1, 0, 1, -1, 1, -1 }; const int MAXH…

D: 道路の老朽化対策について - AtCoder Beginner Contest 040 | AtCoder 最初はパッとしなっかったけど、よく考えると、年について、クエリと辺をソートすると Union Find の問題になる。 Union Find 系の特徴はやはりこういう者だなと思った。 破壊を逆か…

D: 三角形の分類 - AtCoder Beginner Contest 033 | AtCoder This was quite interesting a problem, despite the meticulousness in double precision required. First it is clear that it is impossible to simple enumerate each complete triangle, so …

typedef long long ll; typedef pair< int, int > pii; typedef vector< int > vi; typedef int T_frac; struct frac{ // actually I think T_frac = ll will overflow T_frac u, d; frac( T_frac _u, T_frac _d ){ assert( _d != 0 ); int g = __gcd( _u, _…

D: 食塩水 - AtCoder Beginner Contest 034 | AtCoder If it is possible to make p%, it will also be possible to make p - 1%. With this property, we know that we can try binary search on the percentage. For a fixed percentage x, we can calcula…

C: 経路 - AtCoder Beginner Contest 034 | AtCoder 前はDPにこだわりすぎてとけなかった。でもよく考えると実は H + W - 2 の選択から H - 1 ( あるいは W - 1 ) 個を選ぶだけの事。factorial と mod_inv で終わり。 const int MOD = 1e9 + 7; int int_pow(…

D: 語呂合わせ - AtCoder Beginner Contest 031 | AtCoder Since there are only 9 s, each |s| within range [ 1, 3 ], we can enumerate in 3^9. Then check whether it is valid with O( N ). Total ( 3^9 * N ). const int MAXK = 9 + 1; const int MAXN…

D: へんてこ辞書 - AtCoder Beginner Contest 030 | AtCoder Find the length before getting into the cycle, and the length of the cycle. Then get K in mod len_cycle, O( N ). const int MAXN = 1e5 + 2; int N, A; string K; int B[ MAXN ]; void sol…