2022-03-24 PAST #9 B - 穴の開いた硬貨 を解いた
PAST #9 : 第九回 アルゴリズム実技検定 B - 穴の開いた硬貨 を解いた。
問題: https://atcoder.jp/contests/past202112-open/tasks/past202112_b
N 人が A_i 円のものを B_i 円出して買う。1, 5, 10, 50, 100, 500 円の硬貨で最小枚数になるようお釣りを出す。お釣りのうち 5 円と 50 円の枚数の合計を求める。
お釣りは B_i - A_i で求められる。硬貨の枚数が貪欲法で良いかの基準はよく分かっていないのだけど 1 円を 5 枚出すよりも 5 円を 1 枚出すほうが良い……のような関係が 1 と 5, 5 と 10, 10 と 50, 50 と 100, 100 と 500 の間にそれぞれ成り立っているのでおそらく金額の大きい硬貨から貪欲に割っていけば良い。お釣りで使用したすべての硬貨の枚数をそれぞれ数えたあとに 5 円と 50 円の枚数の和を出力する。
N <= 10^5 で硬貨の種類は 6 種類なので間に合う。
提出: https://atcoder.jp/contests/past202112-open/submissions/30386397 解説: https://atcoder.jp/contests/past202112-open/editorial
アルゴリズムと数学 演習問題集 057 - Domino Tiling の部分点 2 分を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_aw
逃げ続けるのも良くないのでひとまず部分点 2 (K = 2) のケースを解いた。
2 * N マスの長方形に 1 * 2 または 2 * 1 のタイルを敷き詰める。敷き詰め方は何通りあるか。 N <= 10^18 なので単純に数えるわけにはいかない。……とはいえ前から順に考えてみる。
N = 0
(何も置かない)
1 通り。
N = 1
|
|
1 通り。
N = 2
||
||
or
--
--
の 2 通り。
N = 3
|||
|||
or
|--
|--
or
--|
--|
の 3 通り。
伸びる横幅に注目すると縦に置いて 1 伸びるか横に置いて 2 伸びるかしかない。 1 伸びるということは 1 つ前の横幅における通り数と同じになる。 2 伸びるということは 2 つ前の横幅における通り数と同じになる。つまり i 番目 (i > 2) の通り数は i - 1 の通り数と i - 2 の通り数の和になる。 i = 0 のときは 1 で i = 1 のときは 1 だ。
これはフィボナッチ数列の第 N 項を求めるのと同じことだ。これは 054 - Fibonacci Hard (mod 1000000000) (2022-02-24) と同じ方法で行列に対して繰り返し二乗法を適用することで高速に求められる。注意が必要なのは 054 とは mod の値が異なること。これでぼくは 2 WA を出した。
最初の部分点が得られた。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30386055
今日のコミット。