naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Beginner Contest 118

2/16(土) 21:00-22:40
Dから順に解いて4完34位

D - Match Matching (400)

DはDPのD

  • dp[n] = { 桁数, 9の個数, 8の個数, 7の個数, ..., 1の個数 }

にしたらdp[n+k] = max(dp[n+k], dp[n]を改変したやつ) で進める
(同じマッチの本数ならできるだけ大きな数字を使うので1〜9すべてをなめる必要はない)
AC 18:39

追記

dp[i] が無効な値 (-1, -1, -1, ...) の場合にもチェックして飛ばすべきところを飛ばさずに dp[n+k] に送ってしまう実装をしていたので、これはhack可能である。
以下のケース(出自はてんぷらさんだったかな)

33 3
1 4 8

81111111111111 が出てほしいところを 111111111111111 を出していた。(テストケースが弱くて助かった)
1行書き足して再提出
AC

教訓

ABCのテストケースは鉄壁ではない

C - Monsters Battle Royale (300)

最大公約数だよね
(以前だったら最初のやつをまず持って2つ目以降と順次gcdを取っていったんだけど、まず0を持って1つ目からgcdを取るというのを覚えた)
AC 21:42

B - Foods Loved by Everyone (200)

集計するだけ
(M番目を計算に入れてなくてサンプルケース合わない!とか焦ってた)
AC 26:38

A - B+/-A (100)

B%A==0かどうかで判定
AC 28:24