ABC281のA,(B),C,D問題を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。
この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。
また、diffは問題の難易度を表す指標です。Atcoder Problems から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。
質問やご指摘はこちらまで
Twitter : Waaa1471
作者プロフィール
Atcoder ：緑 855
22/1210 現在
目次
はじめに
A.Count Down
B.Sandwich Number
C. Circular Playlist
D.Max Multiple
はじめに
特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的考察が必要になり始めます。
しかし、公式解説ではこの部分の解説があっさりしすぎていて競技プログラミング(Atcoder)を始めたばかりの人にはわかりにくい、難しいと感じるのではないでしょうか。
またC++がわからないと、コードの書き方を勉強することが難しいです。一応、参加者全員のコードを見ること自体は可能ですが、提出コードは必ずしも教育的ではありません(ここで紹介する記事も本番で提出したものとは全く異なります)。そんなものから初学者が解説もなしになにか得ることはとても難しいと思います。実際適当に何人かのコードをみたものの、意味がわからずに終わった経験があるのではないでしょうか。
この記事がそんな方々の勉強の助けになればよいなと思っています。
A.Count Down
灰色 diff 6
考察
順番に出力
for ループで順番に値を出力しましょう。
また、降順に値を調べることでストレートに出力することも可能です。
コード
pypy3
# 昇順に調べて、出力を調整
N=int(input())
for i in range(N+1):
print(N-i)
# 降順に調べて、そのまま出力
N=int(input())
for i in range(N,-1,-1):
print(i)
補足
-
Pythonのrange関数の使い方
range(start,stop,step)で、index番号 start ～ stop-1 まで step 幅のイテラブルを作成できます。
ある倍数だけ調べる for ループ など利用することがあります。
B.Sandwich Number
灰色 diff 66
考察
死ぬほど調べて ACしました。
ここになにか書けるほど自分の中で整理できていないし、ふつうに公式解説が詳しいのでこちらを見てください。逆に、文字列の判定がうまくまとめられているおすすめの記事、サイトがあれば教えてください。お願いしまうす!
コード
pypy3
補足
なし
C. Circular Playlist
diff 131
考察
まず、「プレイリスト一周にかかる時間 < T 」の場合、1周目では T秒後を迎えません。
1曲目から順に、何かしらの処理によって「 T秒後に流れている曲か ? 」の判定を行う場合、このような目的の位置が探索しても見つからない状況は都合が悪いです。
逆に言えば、必ずその周のどこかでT秒後を迎える状況であれば都合が良いというわけです。
ここで、プレイリスト一周にかかる時間を A とすると、$ A(X-1) < T < Ax$ を満たす $\ x\ $ 周目に必ず $\ T $ 秒後を迎えるので、この周を調べることにします。
ただし、この問題では「 何周目に T 秒後を迎えるか 」は問われていません。そこで、$ T' = T - A(X-1) $ と置き換えることで、1周目に必ず目的の時間 $T'$ を迎える状況を作り出します。
この $ T'$ は $ T\ (modA) $ で表すことができます。
累積和で経過時間を求める
$X$ 曲目に $ T'$ 秒後を迎えるとすると、次の関係式が成立します。
「 $ X-1\ $曲目が終了するまでの総時間 」$≦\ T' ≦$ 「 $ X\ $ 曲目が終了するまでの総時間 」
したがってプレイリストの全曲において、その曲が終了するまでの総時間 が分かれば、初めて $T'\ $ を超えた曲が何曲目かを求めることができます。
この「 ある地点までの総和 」は 塁積和と呼ばれ、前から順に要素の和を取っていくことで作成することができます。
Pythonでは、itertools ライブラリの accumulate 関数を使って、より簡単に作成することも可能です。
二分探索で目的の位置を高速に求める
素直に累積和リストを前から順に探索して、$T'\ $ との大小関係を比較しても計算量 O(N) なので問題ないのですが、ここでは 二分探索 でより高速に 目的の $ X $ の位置を求めることにします。( 処理速度的にも、コーディング量的にも)
x=bisect.bisect_left(B,S)
Pythonではこのように、昇順にソートされたリストB において、S より小さい値がいくつ存在するか一撃で求めることができます。
経過時間の塁積和リストを $T'$ で二分探索することで、何曲目で $T' $ に到達するかは求めることができました。
あとはその曲が流れ始めてから何秒後かを求めるだけです。
ここまで利用した累積和を用いて、$T' - $ 「 $X-1 \ $曲目が流れ終わるまでの総時間 」を出力すれば OK です。
コード
pypy3
import bisect
from itertools import accumulate
N,T=[int(nt) for nt in input().split()]
A=[0]+[int(a) for a in input().split()]
#
T%=sum(A)
# 累積和リスト作成
AA=list(accumulate(A))
# リストを二分探索し、T 秒後までに終了した曲がいくつあるか求める
x=bisect.bisect_left(AA,T)
print(x,T-AA[x-1])
補足
-
mod 計算
X mod(Y) = Z は X を Y で割ったときの余りが Z であることを示します。
筆者も高校で出会ったとき、なかなか理解するのに苦労した記憶があります。この動画で勉強しましょう。これは令和のスタンダードですが、数学でわからないことがあれば、まずヨビノリで調べてください。 -
二分探索 (リスト)
二分探索とは、単調性のある区間の探索アルゴリズムです。探索対象がリストの場合のみ bisect で二分探索することが可能です。
bisect --- 配列二分法アルゴリズム
bisect.right(X,y)で y 以下の個数を求めることも可能です。 -
二分探索 (一般)
探索対象がリストでない場合は、自分で二分探索を実装します。
二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜：二分探索を勉強するのにとても参考になります (再掲載)
練習：アルゴ式に例題がいくつかあります -
塁積和
Pythonで累積和・累積積（itertools.accumulate）
itertools は他にも便利な関数がたくさんあるので、出てくるたびに覚えましょう
D.Max Multiple
緑色 1031
考察
素直に K個の和の候補を全部調べられれば うれしいですが、残念ながらこれはできません。
例えば $N=100$ , $K=50$ の場合、$10^{29}$ 通りの候補があるからです。
よくわからないので、前から探索した状態を観察します。
すると例えば、$A=[2,7,....]$ $D=5$ のとき、和は以下の様に遷移します。
実験によって、総和の余り に注目することで管理すべき状態を取捨選択できることがわかりました。これによって、計算量の問題を改善できたかもしれません。
ここまで得た情報を整理すると、
- 前から何番目まで見たか
- 選んだ数
- 総和
- 総和の余り
これらの情報で状態を定義すると、状態の遷移に忠実に全ての状態を更新させることができそうです。
状態の遷移は 動的計画法 (DP) で管理することが頻出です。また、1 , 2 , 4 の情報で 3 を管理すると考えると、3次元 dpテーブル (リスト) を作成することになりそうです。そのサイズは $ NKD $ とすれば、考えられるすべての状態を管理できることになります。
ここで、各状態は次の要素を和に含めるか含めないか遷移するので、各状態に対して 2回ずつ操作を行う可能性があります。
したがって、全体で計算量は $O(NKD)$ であるので十分高速です。
最終的に、余り0 を管理する2次元リストの右下の場所に求めるべき 最大の総和が格納されることになるので、これを出力します。
注意点
多次元リストの操作ではどの軸から操作するか、その順番が大切です。
for n in range(N):
for k in range(K+1):
for d in range(D):
if dp[d][n][k]>=0:
実装のこの部分の話です。より外側のループはその内側のループが完了して初めて進みます。この処理を可視化すると図のような順で操作が行われているということになります。
ループを入れ替えれば、当然処理順も変化します。例えば
for d in range(D):
for n in range(N):
for k in range(K+1):
if dp[d][n][k]>=0:
とすればこのように変化します。
この問題では、A[x]を 含めるか含めないか それまでに求めた全ての総和に対して操作し終えてから、A[x+1]を 含めるか含めないか の操作に移るのが正しい順番です。これを間違えないように正しい順番で実装しましょう
コード
N,K,D=[int(nkd) for nkd in input().split()]
A=[int(a) for a in input().split()]
dp=[[[-1 for _ in range(K+1)] for _ in range(N+1)] for _ in range(D)]
dp[0][0][0]=0
for n in range(N):
for k in range(K+1):
for d in range(D):
if dp[d][n][k]>=0:
# 選ばない操作
dp[d][n+1][k]=max(dp[d][n][k],dp[d][n+1][k])
# 選ぶ操作
# 既に K個の総和になっている場所は更新しない
if k<K:
dp[(d+A[n])%D][n+1][k+1]=max(dp[d][n][k]+A[n],dp[(d+A[n])%D][n+1][k+1])
if dp[0][-1][-1]>=0:
print(dp[0][-1][-1])
else:
print(-1)
補足
- 動的計画法 (DP)
アルゴ式
動的計画法がわからないという方は、教科書で理解し、1～2章で練習しましょう。
その後、適当な C,D 問題をガンガン解いて演習しましょう
これは筆者の個人的な意見ですが、DPで解けばいいとわかった状態で演習しても効果が薄いです。( DP練習 等で Hitした問題を解く行為など)
なぜなら、DP問題の多くの肝は「「 この問題が DP 問題である」ということを捉えること」にあるからです。この力は DP かどうかわからない状態で DP で解けるか検証する過程でしか養えないと思います。
DP のことは理解しているけど、この問題が分からなかったという人はぜひこの方法で演習してみてください。
終わり
来週のABCまでに、過去のABCの記事を3つ以上出すので絶対見てくれよな!