ABC146
A
曜日を格納した配列を作っておいて、入力と一致したら対応する値を出力すればよいです。
Submission #8612614 - AtCoder Beginner Contest 146
B
各文字ごとに丁寧にN回インクリメントすればよいです。
Submission #8612571 - AtCoder Beginner Contest 146
C
を固定します。このとき、
桁の整数であって、値が
以下である整数を買うことができます。そのような整数のうち、最大のものが答えの候補です。
は1から10まで試せばよいので間に合います。(19まで試したしまったけど...。)
Submission #8612542 - AtCoder Beginner Contest 146
D
まずの値がいくつになるかを考えます。次数が
の頂点があったとき、その頂点に関する条件を満たすためには
でなければなりません。つまり、次数の最大値が
の下界です。逆に
が次数の最大値であるような辺の塗り方が作れることを示します。根を1つ決めてdfsしながら順に塗っていきます。頂点
に来たとき、
の親
との間にある辺の色を覚えておきます(根の場合は適当に関係ない値にしておく)。この色以外を使って
の子との辺を塗らないといけませんが、
の子の数は
以下であり、
色使っていいのでそれらを好きに塗ればよいです。あとは実装力勝負でしょう。
Submission #8612498 - AtCoder Beginner Contest 146
E
難しいと思いました。区間の和を
、その長さを
とすると、ある自然数
があって、
が成り立つということが条件です。
を移項すると
で、
が
で割り切れればよいです。ここで
が成り立つので、新たな数列を
で定義します。すると、この問題は、「数列
について、その総和が
で割り切れるもののうち、長さが
未満である連続部分列の数を求めよ」と言い換えられます。これは
の累積和
をとると、
のとき、
が
なので、
から
の和の
は0です。従って、
が同じ
をまとめておいて、あとはその差が
未満である組の数を数えればよいです。
Submission #8621948 - AtCoder Beginner Contest 146
F
最短の回数を求めるには、:
までの最短回数、というdpが思い浮かびます。愚直にやると
ですが、遷移をこれはセグ木で高速化できます。ところが、今回は辞書順最小の移動手順を求められているので、
を小さい方から埋めると困ってしまいます。しかし、
を大きいほうから埋めるとどうでしょうか？
まで埋まった状態から、辞書順最小の移動手順を求めます。今0にいるときに、条件を満たすような位置は「
」を満たすような最小の
です。これはセグ木を用いた二分探索によって見つけることができます。この操作を
にたどり着くまで繰り返せばよいです。全体で
かけてもいいですし、「セグ木上の二分探索」によって
の計算量を達成することも可能です。
