読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

AtCoder Regular Contest 067: F - Yakiniku Restaurants

http://arc067.contest.atcoder.jp/tasks/arc067_d

AtCoder Grand Contest 005: D. ~K Perm Counting

http://agc005.contest.atcoder.jp/tasks/agc005_d

AtCoder Grand Contest 005: C. Tree Restoring

http://agc005.contest.atcoder.jp/tasks/agc005_c

AtCoder Grand Contest 005: B. Minimum Sum

http://agc005.contest.atcoder.jp/tasks/agc005_b

AtCoder Grand Contest 002: D - Stamp Rally

http://agc002.contest.atcoder.jp/tasks/agc002_d

AtCoder Grand Contest 001: C. Shorten Diameter

http://agc001.contest.atcoder.jp/tasks/agc001_c

AtCoder Grand Contest 001: B. Mysterious Light

http://agc001.contest.atcoder.jp/tasks/agc001_b

AtCoder Beginner Contest #038

http://abc038.contest.atcoder.jp/ 解説動画、ニコニコ動画だとシークバー使えなくて見るのが面倒(一般会員の感想)。

AtCoder Regular Contest 050 C - LCM 111

C: LCM 111 - AtCoder Regular Contest 050 | AtCoder

AtCoder Regular Contest 050 B - 花束

二分探索解と三分探索解の両方を解説する。 B: 花束 - AtCoder Regular Contest 050 | AtCoder

Typical DP Contest J - ボール

よくある期待値の問題。 tdpc.contest.atcoder.jp 解法 oxoooxox の状態からすべて倒すまでに投げるボールの個数の期待値を $E[10111010]$ と表すことにする。つまり bitDP をする。 パターン 1:投げた先 3 マスがすべてが埋まっている v ooo このときの期…

Typical DP Contest C - トーナメント

アルゴリズムが難しいというより計算量解析が難しい。 tdpc.contest.atcoder.jp 解法 セグ木っぽく区間に番号を割り振る。こうすると左の子と右の子のインデックスを求めるのが簡単になる。 考えるべきは次の DP。 dp[ i ][ j ] := 区間 i でプレイヤー j が…

Typical DP Contest D - サイコロ

tdpc.contest.atcoder.jp 解法 積の倍数判定の場合は、gcd(a0 a1 ... an-1,D)=D なら a0 a1 ... an-1 は D の倍数という判定法が使える。 これを使うと dp[ 振ったサイコロの個数 ][ gcd(サイコロの目の積,D) ] := 確率 ができる。状態数は D の約数のうち素…

第2回 ドワンゴからの挑戦状 予選 D - 庭園

dwango2016-prelims.contest.atcoder.jp

第2回 ドワンゴからの挑戦状 予選 C - メンテナンス明け

dwango2016-prelims.contest.atcoder.jp

AtCoder Regular Contest 031 C - N!÷K番目の単語

問題 arc047.contest.atcoder.jp

AtCoder Beginner Contest 031 D - 語呂合わせ

問題文 http://abc031.contest.atcoder.jp/tasks/abc031_d 解法 サンプル1の入力を考えてみる。