mayoko’s diary

プロコンとかいろいろ。

2016-03-13から1日間の記事一覧

Codeforces Round #345 (Div. 1) C. Table Compression

問題 codeforces.com 解法 大小関係系は, 「a b に有向辺を貼る」ということをやるのがよくあります。これもそのタイプです。すべての数が異なっていたとすると, a_ij (i, k) に辺を貼る a_ij (k, j) に辺を貼る というようにしてグラフを作ります。で, この…

Codeforces Round #345 (Div. 1) B. Image Preview

この回かなり簡単だったみたいですね…(普段だと僕は B から苦戦しているはず) 問題 codeforces.com 解法 まず考察です。 写真の見かたを考えると, 「0 より右側の写真を見に行って, 次に左側(n-1, n-2, ... のことです)を見に行って, また右に…」とやるのは…

Codeforces Round #345 (Div. 1) A. Watchmen

問題 codeforces.com 解法 マンハッタン距離とユークリッド距離が一致するのは, 「x 座標または y 座標が一致する時」です。X[x] = (x 座標が x の点の数), Y[y] = (y 座標が y の点の数) を数えておけば, 基本的には C[X[x]][2], C[Y[y]][2] の和が答えにな…

Codeforces Round #344 (Div. 2) D. Messenger

問題 codeforces.com 解法 T の i ブロック目を T[i] と書きます(例えば T[i] = 4-a だったら実際には T[i] = "aaaa")。で, T の l ブロック目から r ブロック目をつなげたものを T[l..r] と書きます。文字列 T の区間 [l..r] に文字列 S があるための条件は…

AtCoder Beginner Contest 034 D - 食塩水

問題 abc034.contest.atcoder.jp 解法 ヒントに書いてあるとおり, 食塩水の濃度 x について二分探索します。濃度が x 以上になるかどうかは以下のようにしてわかります。食塩水全体の質量を S, 食塩の量を T とすると, 条件は T/S >= x i.e. T - x*S >= 0 と…