mayoko’s diary

プロコンとかいろいろ。

2016-05-01から1日間の記事一覧

AtCoder Regular Contest 052 D - 9

問題 arc052.contest.atcoder.jp 解法 K の値に応じて場合分けします。K が小さい場合は, 桁dp で解けます。よくある dp[桁][あまりの差][smallFlag] ってやつです。K が大きい場合は, 各桁の和がせいぜい 100 であることを利用します。すると, 解の候補は i…

AtCoder Regular Contest 052 C - 高橋くんと不思議な道

問題 arc052.contest.atcoder.jp 解法 まず自明な解法として, d[v][b] = (頂点 v までに, b 回タイプ B の道を通る場合の最短距離)というのがあります。b は N より大きかったらどこかの頂点を複数回通っていることになるので, 頂点の個数は O(N^2) でダイク…

GCJ Round 1B Problem C. Technobabble

GCJ

この問題とは関係ないですが windows でそれっぽくプログラミングができるようになりました。 問題 Dashboard - Round 1B 2016 - Google Code Jam前半, 後半に分かれたワードの組が N 個与えられる。 あるワードの組 (s, t) について, 「すでに s と同じ文字…