主食は米

主に競プロ備忘録

DDCC 2019 予選 D - チップ・ストーリー ~黄金編~ (700)

解法

全力で必要条件を列挙していく.
Nのk進数表記が下の桁から n_0, n_1, n_2, .. であったとすると,
N = n_0 + n_1 r1 + + n_2 r2 + ..
a_k = n_0 + n_1 + n_2 + ..
N - a_k = n_1 (r - 1) + n_2 (r2 - 1) + n_3 (r3 - 1) で, rx - 1 は r-1 で割り切れるので N = a_k (mod k-1) となる.

よって拡張Euclidの互除法を用いてmod lcm(2,3,..,30) の元でこれを求めてやり,
明らかに lcm(2,..,30) > 1e12 なので この解が条件を満たしてやるかを確かめてやれば良い.
拡張Euclidの互除法については下を参照.

qiita.com

メモ

思いつかなかったけど,n進数の各桁の和で割と一般的に使えそうな気がした.
後CRT(中国人剰余定理)はそもそも知らなかったので...

コード

数列操作に関するメモ

とりあえず考えること

  • 要素/総和のmod/パリティに注目する
  • 操作回数を求めることができるか(特に総和を用いて)

  • 逆操作が可能か

  • 操作が単純な操作に分解できるか

  • 階差数列を考える

  • 操作の縮約ができないか/周期を持たないか

  • 上の典型的な場合として,単純な一連の操作を考える(最初から順番に操作していくなど)
  • 数列を自分で用意することができる場合は,数列も単純なものを用意する({1,2,..}, {n,n,...})

例題 (順次追加)

D - Decrease (Contestant ver.)

操作できる数に制約がある. 単純な数列で単純な一連の操作を考えると縮約ができる

ARC 086 D - Non-decreasing (600) - 主食は米
単純な操作を考えよう

AGC 010 B - Boxes - 主食は米

総和に注目する -> 逆操作を考える -> 階差数列を見る -> 逆操作を分解する

SoundHound Programming Contest 2018 Masters Tournament Open B - Neutralize(400)

解法

  • K個以上の区間は消せる
  • Greedyは厳しそう
  • dp[i] := (最後に[i,i+K) を消したときのmax ) とすると..?
  • dp[i+1] = max_{ j, [i,i+K) と [j,j+K) の区間が被っている } ( dp[j] + sum_b [j+K, i+K) ) と,
  • dp[i+1] = max_{ j, [j,j+K) の区間は [i,i+K) と被らない } ( dp[j] + sum_b[i,i+K) ) の漸化式が立つ
  • 愚直O(N2), 累積和+区間和とRMQのSeg木でO(NlogN)だが400点なのでさすがに...

  • 上の置き方は最後に消した場所を持っていて,まとめ方が良くなさそう

  • どの範囲が0か,ではなく末尾が0かだけを持っておこう
  • dp[i][j] := ( b[0,i) についての max, j は末尾が0かどうか ) とおく
  • dp[i+1][1] = max(dp[i-K+1][0] , dp[i][1] )
  • [i-K+1, i+1) を消す時,その範囲の j==0 の場合の更新はないものになる and 1個前が0の時はその数は好きに0にできるため
  • dp[i+1][0] = max(dp[i][0], dp[i][1]) + b[i] という漸化式が立つ

メモ

飛び地で更新する?系のDPに弱い

コード

Tenka1 Programmer Contest 2018 C - Align

解法

1,..,N の順列を p1,..,pN として, 最大化したい関数は
|A_p1 - A_p2| + .. + |A_pN-1 - A_pN| になる.

目的関数の絶対値を外したい気持ちになるので,そのためには数列の順序付けが必要になる.
それを念頭に起きつつ最適解の必要条件を列挙してみる.
すると A_p1,.., A_pN が単調増加/減少になっていてはダメで, 凸凹のような形になっている必要があることがわかる.
例えば a < b < c であれば a c b と並んでいた方がいい.簡潔な証明は解説に載っている.
これを式で書くと
A_p1 >= A_p2 <= A_p3 >= .. or A_p1 <= A_p2 >= ..
となっている.
前者の時, N=evenとすると目的関数は
(A_p1 - A_p2)+(A_p3-A_p2) + .. + (A_p{N-1} - A_pN )
= 2(A_p1 + .. + A_p{N-1}) - A_p1 - 2(A_p2 + .. + A_pN) + A_pN
となる.
よって{A} を sortしてgreedyに当てはめていけばいい.
この場合だと奇数項が昇順sortしたときの後ろ半分(ただしA_p1がその中で最小のもの),
偶数項が前半分(ただしA_pNがその中で最大のもの) になる.

コード

AGC 008 B - Contiguous Repainting (400)

解法

解説にある通り,上書きしていくような問題では操作列を逆に見ていって,そのマスで一番最初の操作で色が確定すると考えるのが良くて,そうするとそのマスに関してそれ以降の色の変化を考えなくて良くなる.

さて,逆順に見ていったときの最初(つまり元の操作で最後)の操作を固定する. これは2(N-K+1)通りある.
後は実験していって気づく必要があるが,それ以外のマスは自由に変えることができる(外側から1つずつずらして範囲を塗っていけばいい)

なので,これをループを回していけばいい. 1回の計算に数列の範囲の最大値が入っているので累積和を使って高速する.

コード

Mujin Programming Challenge 2018 C - 右折

解法

最初に右を向いていて,次に右折するパターンを考える.
各マスで上方向に累積和をとると下に何マス進めるかというのがO(NM)でわかる.
それを左方向に累積和をとっていくとその場所を始点として1マス以上進み,右に何マス進めるかというのがわかるのでこのパターンは解けた.

これを全方向実装するのはかなりめんどくさいので,迷路自体を回転してループを4回回せばいい.

メモ

公式解答は鮮やかすぎて思いつかないので...

コード

AtCoder Grand Contest 028 B - Removing Blocks (600)

解法

解説の1つの解釈として.

解説/解説放送と同じように, iをremoveした時に A_j が足されるかどうかを考える.
ただし,確率ではなくそのような順列の場合の数を数え上げることにする.

事前準備として,n個の順列のうちで
そのうちの要素 x,y (x!=y) に関して x<y が成り立っているものは n!/2 になる.
これをもう少し考えると x_1 < .. < x_k+1 のk個の不等号があるものは n!/(k+1)! になることがわかる.
(n個の場所からx_iの場所k+1個を選ぶ) * (残りのN-k-1個は自由に並べる)
= nC(k+1) * (n-k-1)! = n!/(k+1)!
と考えても良い.

これを使って,上の順列が何通りあるかを数える.
簡単のため, i < j と仮定して
x_0 = i, x_1, ... , x_k, x(k+1) = j とする. (k = j-i-1)
ここで, 求めたい順列を束縛する不等式は i の後にx_1, x_2,.., x
(k+1) が出るという条件のみを満たしていれば良いことを考えると
x_0 < ( x_1, x_2, .. , x(k+1) を好きに並べて不等号で繋いだもの ) であることがわかる.
これは, x_1,...,x
(k+1) の順番が決まればk+1個の不等号が繋がっているので N!/(k+2)! 個ずつある.
このいずれかを満たす順列(つまり順列の和集合)を求めればよく,これらは全て排反であるため
合計で n!/(k+2)! * (k+1)! = n!/(k+2) = n!/(j-i+1) 個あることがわかる.

ここからは解説と一緒で,
A_j * sum_i{ n!/abs(j-i+1) } のjに関する和が答えになる.
調和級数を事前に計算しておけばO(N)

メモ

確率として典型処理するようにしたほうがいい気もする..

コード