はじめに
この記事では、AtCoder Beginer Contest 167のA~E問題を解説します。
A - Registration
https://atcoder.jp/contests/abc167/tasks/abc167_a
Python
の場合、文字列のスライスが便利です。
1 | S = input() |
B - Easy Linear Programming
https://atcoder.jp/contests/abc167/tasks/abc167_b
min
を使って、K
を減らしながらカードを取っていきます。
1 | A,B,C,K = map(int,input().split()) |
C - Skill Up
https://atcoder.jp/contests/abc167/tasks/abc167_c
bit全探索を行います。itertools.product
が便利です。
1 | from itertools import product |
D - Teleporter
https://atcoder.jp/contests/abc167/tasks/abc167_d
ループを検知すれば良いです。その際に、いつループに入ったかを後ほど利用します。(bias
)
具体的には一旦K
からbias
を引いて、ループの省略をした後に再度bias
を足します。
これは、単純に周期で割ってしまうとループに入る前の遷移を無視することになってしまうためです。
1 | N,K = map(int,input().split()) |
E - Colorful Blocks
https://atcoder.jp/contests/abc167/tasks/abc167_e
K=k
としてK
を固定して考えて、全てのK
について足し合わせれば良いです。
ペアは全部でN-1
個あるので、ペアの選び方は
1 | nCk(N-1,k) |
となります。
どのようにペアを選んでも、連続する同色ブロックをグループとみなすと、グループは全部でN-k
となります。
グループの列に色を塗っていきます。最初のグループはM
色の何でもよく、それ以降のグループは前のグループとは違うM-1
色から選ぶことになります。すなわち、グループの列に対する色の塗り方は
1 | M * (M-1)^(N-1-k) |
となります。
つまり、nCk(N-1,k) * M * (M-1)^(N-1-k)
を求めれば良いですが、いずれも巨大になるため工夫してMOD
の計算をする必要が有ります。
前者はMODの逆元
、後者はPython
のpow(a,b,MOD)
により計算できます。
解答例
1 | N,M,K = map(int,input().split()) |
失敗例
動的計画法による以下の実装はO(NK)
となり間に合いませんが、参考として載せておきます。
1 | N,M,K = map(int,input().split()) |
関連記事
過去のABC解説記事です。
- ABC166
- A-F問題を解いています。
- ABC165
- A-F問題を解いています。
- ABC164
- A-E問題を解いています。
- ABC163
- A-D問題を解いています。
- ABC162
- A-E問題を解いています。
記事情報
- 投稿日:2020年5月11日
- 最終更新日:2020年5月11日