mayoko’s diary

プロコンとかいろいろ。

2015-09-13から1日間の記事一覧

SRM 667 div2 hard:ShopPositions

今回の div2 med は div1 easy とほとんど同じっぽいですが, だとするとこの hard は med よりも簡単な気がする… 問題 TopCoder Statistics - Problem Statement 解法 dp で解きます。dp[now][preorder][prenum] = (now 番目の店を見ていて, 直前のビルは 1 …

SRM 667 div1 CatsOnTheCircle

「言われてみるとアタリマエ」みたいな問題解けないの非常に辛い。 問題 TopCoder Statistics - Problem Statement 解法 三項間漸化式を解く感じになります。まず, どのようなときに K が勝つのかを考えます。これは, 「K 以外のすべての人にボールが回った…

Japan Alumni Group Summer Camp 2015 Day 2 C - ABC Gene

問題 jag2015summer-day2.contest.atcoder.jp 解法 逆からたどっていく感じでやります。"ABC" という文字列を見つけたら, それを "A" "B" "C" のいずれかに変換する, ということを繰り返して, 最終的な文字列が "ABC" になったら勝ちです。ただし, 例えば "A…

Japan Alumni Group Summer Camp 2015 Day 2 B - 監獄

問題 jag2015summer-day2.contest.atcoder.jp 解法 二分探索をします。ok(x) = (x 以下の数のうち, N 回目の操作で選ばれる数があるか) という判定をします。この判定ができると, 結局のところ求めたい x というのは ok(x) が true になるような数の中で最小…

AtCoder Regular Contest 044 C - ビーム

問題 arc044.contest.atcoder.jp 解法 せっかくなので部分点解法も載せておきます。d[t][x][y] = (時刻 t に座標 x, y にいるときの最短距離) というようにすると, d[0][x][y] = 0 をスタートにしてダイクストラすれば答えが求まります。で, 満点解法です。…

AtCoder Regular Contest 044 D - suffix array

ARC 044 に参加しました。 B が難しかったせいか, C の部分点取るだけで結構上位にいけました。いや上位とっても解けないと意味無いですけど。 D は言われてみるとかなり簡単だったので C 捨てて考えても良かったかも。 問題 arc044.contest.atcoder.jp 解法…