みんなのプロコン2018 決勝 A - Uncommon

• 問題

問題概要

自然数N,M と 数列 {a_i} (0 <= i < N) が与えられる.
各 j = 1, ... ,M について, jと互いに素なa_iの要素の数を求めよ.
1 <= N,M,a_i <= 10⁵

解法

各jについて, 互いに素でない <-> 共通因数を持つ a_i の数を考えることにしよう.
j = 5 のように j が素数であれば,その倍数を数えるだけで良い. これは倍数全列挙をすれば高速に求めることができる.

(関連問題)として, 各 j について a_i のうちで j の倍数となっているもの,すなわち j を約数として持っているものを求めることにする.
倍数全列挙は, Xまでの j = 1,.., Yの倍数を全列挙していくアルゴリズムで
各jに対してXまでの倍数の数は X/j で抑えられるから, O(X * (1/1 + 1/2 + .. + 1/Y) ) = O(XlogY) だけかかる.
* 類題 ARC068 E
X = max(a_i, M), Y = M とすればよく, この場合だと O(max(a_i,M) logM) 程度になる.
これを使って , factor[ k ] := (k を倍数として持つ数の集合) = (k の約数の集合) を埋めることができて
例えば factor[ 12 ] = { 1, 2, 3, 4, 6, 12 } となる.
各 j について, cnt[ j ] := ( a_i のうち, j を約数として持つものの要素数 ) と定義して,
各 a_i について, 各 factor[ a_i ] の要素 x について cnt[x] をインクリメントしていけば cnt[ j ]を求めることができ, (関連問題) が解けた.
factor[ a_i ] の要素が最大でいくつあるかということだが,公式解説と同様の考察をすると,
9! = 3 * 10⁵ から, 最大でも8個になる(公式だとfactorを素数に限定しているのでより小さい)
よって(関連問題)は O(NlogM + 8*N) で十分. (正しい書き方ではないが簡便のため)

元の問題について考える.
上のアルゴリズムを少し変えて,倍数全列挙で各 j が素数の時のみfactorに自身の倍数を足していく,とすれば
各 k に対して prime_factor[ k ] := ( k を倍数として持つ素数の集合) = ( k の素因数の集合) が求められそうだ.
素数の時, というのはエラトステネスの篩のように考えると, prime_factor が空である時なのでこれは簡単にわかる.
つまり, prime_factor[ 12 ] = { 1, 2, 3 }
かつ, prime_factor の数も同様に6個以下になる.

ここで {a_i} のうちで j と互いに素でないものはprime_factor[ j ] と 関連問題で求めた cnt[x] を使えば,包除原理で求めることができる.
例えば12であれば (2または3の倍数) = cnt[2] + cnt[3] - cnt[6] となる.
包除原理の実装は, lambdaを使って再帰的に実装しても良さそうだが,
単純に s := (prime_factor のうちどれを選ぶかの mask )
として, s の立っているbitの数で+か-を選んで足していくのが楽そう.
prime_factor の要素数は6以下なので, 2⁶程度の定数倍にしかならない.

ここまでをまとめると,
factor=> cnt => prime_factor => 包除原理で j と互いに素でないものを求める
となるが, このfactorは余計で prime_factorだけ求めておき,
prime_factor のうちのいくつかを組み合わせてかけた数についてのみ, cnt[ j ]テーブルを埋めれば十分である.
これは (2かつ3の倍数の数) = cnt[ 6 ] は必要であって, cnt[ 12 ] は包除原理で必要ないからである.
よって prime_factor => cnt => 包除原理 として, この問題が解けた.

メモ

難しかった. でも包除原理の実装やら良問.

コード

ARC 098 E - Range Minimum Queries

• 問題

問題概要

サイズNの数列からサイズKのsubarrayを選び,subarrayのminを取り除く試行をQ回行う.
取り除いたminのうちの max - min をminimizeするように試行を行った時のminを求めよ.
1 <= N <= 2000, 1 <= a_i <= 10⁹

解法

思考箇条書き

• 単純に小さい順に選んでいったとすると, sortして a_{Q-1} - a_0 となる.
• 選んだ数のうち A=max, B=min とすると,Aを固定したらBをmaximize, Bを固定したらAをminimizeする
• 区間minをmaximizeは難しい,ある値以下(or未満)を取ってはいけないとして取れる値のうちmaxを探す？
• minのmaxと言うと二分探索が思い浮かぶ,取る数を固定して二分探索?
• 一方で,区間minのminimizeは簡単,その値が入る区間を取ればいいだけ
• Bを固定して,Aをminimizeすることを考えるとある値未満は取ってはいけないとしてminを求めるのが良さそう
• ある値未満は取ってはいけないと言うのは, a をその値未満でsplitすればOK
• splitしたarrayを {s} とすれば, |s|<Kならそこからは取れない, |s|>=K なら |s|-K+1回取れる
• B = a_i としてみると,その値を確実に取って, a_iとa_i未満の値でsplitしたaから条件を満たすようにQ-1個取る?
• a_iとa_i未満の値 <- この議論はaが全て異なれば単純にa_i以下とできるが, そうでなければちょっとめんどい
• Bの範囲を固定するようにして, 単純に小さい順にQ個取ってくるようにしよう
• つまり, a_i以上の値を取らないといけないが,必ずしも取らなくても良いと言う縛り
• しかしどうせ小さい順に取ってくるので a_i は取ることになる.
• 各 a_i について, a_i 未満でsplitして小さい順に |s|-K+1個取ってきたもの全ての中から小さい順にQ個取る.
• sortのlogがシグマの中に入るのは気になるが,計算量は特に変わらない. O(N² logN)

メモ

解けたい問題,という感じ

コード

codeFlyer 2018 予選 D - ハンコ

• 問題

問題概要

NM のハンコをハンコがマスに収まるような範囲の全ての場所でHW のマスに押す.
ハンコで黒く塗られるのは何箇所か求めよ.
1 <= N,M <= 10³ ,1 <= H,W <= 10⁹

解法

まず for(ハンコを押した回数) for(ハンコの全てのマス)のループの順序を入れ替えて,
ハンコの各マスがH-N+1 * W-M+1 のマスを黒く塗ると考えよう.
こうすることで塗る領域が長方形になるので,二次元累積和を取ればO(HW+NM)では解けるようになった.
しかしこれでは間に合わない,
だが,HとWが増えても塗る長方形の領域が大きくなるだけなので二次元累積和を取るときにアクセスするマスだけを考えれば良いことがわかる.
つまり考えなければならないマスは, xであれば 0とH-N, 1とH-N+1, .., N-1とH-1 .. となる
yも同様に考えて,これらのうち重複を除き,考えなければならない座標をx_dec, y_decとする.
このindexとelementを逆にしてmapを取れば圧縮後の座標 x_enc, y_enc が求められる.
圧縮後の座標を二次元累積和で塗り,圧縮前の塗られている場所の面積を求めれば答えとなる.
( i が塗られていれば [ x_dec[i], x_dec[i+1] ) が塗られていると考える)

メモ

本番は色々なケースで試してみる
-> H,Wが大きいケースでは外縁の領域だけ考えれば良さそう
-> 外側の領域を頑張って取ってくるコードを書く
という感じで爆死だった
言われてみるといかにも累積和だし座標圧縮っぽい
面積が復元できるというところで経験値が足りなかった..

コード

codeFlyer 2018 予選 C - 徒歩圏内

• 問題

問題概要

昇順に並んでいる数列{x_i} (1<=i<=N) が与えられる.
(i, j, k) , (i < j < k) の組で,
x_j - x_i <= D
x_k - x_j <= D x_k - x_i > D
を満たす組の総数を求めよ. 3 <= N <= 10⁵

解法

補集合を考える.
x_j - x_i <= D, x_k - x_j <= D を満たす(i, j, k)の組から
x_j - x_i <= D, x_k - x_j <= D, x_k - x_i <= D を満たす(i, j, k)の組を引けばよい.
前者は j を動かして min(i)とmax(k)を二分探索で出し,
後者は i を動かして max(k)を二分探索で出し, iとkの範囲から二つ取ってくる組み合わせを足して行けば良い.

メモ

解けなかった..
条件がややこしくて高速に求められなかったら補集合を考えよう.

コード

AGC 025 B - RGB Coloring

• 問題

問題概要

ブロックに0,A,B,A+Bのいずれかの得点をつけることができる
合計Kの得点をつける塗り方をmod 998244353で求めよ.
1 <= N,A,B <= 310⁵, 0 <= K <= 1810¹⁰

解法

単純にDPを立てると,状態がO(NK)とかになってしまうので間に合わない.
ここで問題特有の3つ目の得点がA+Bであると言うことに注目してみよう.
A+Bをつけると言うのを,AとBのどちらの得点もつけると考えることができる.
すなわちAとBの得点を独立につけることができると言うことである.

以上のことから,aA+bB=K(1<=a,b<=N) を満たすaを全探索し,
nCa * nCb を足して行くことで O(N)で解ける.

メモ

f(N,K) = f(N-1,K) + f(N-1,K-A) + f(N-1,K-B) + f(N-1,K-A-B) で答えを求められることがわかってそれをなんとか高速化しようとしたら終わってしまった.
問題特有の要素に注目するの大事.

コード

ARC 097 E - Sorted and Sorted

• 問題

問題概要

1~Nの数字が書かれた白のボールと黒のボールがN個ずつ,合計2N個ある. 白と黒それぞれに注目した時,どちらも順番通りに並んでいるようにするには最低何回のswapが必要か.
1 <= N <= 2*10³

解法

考察段階から箇条書き

• 最終状態が決まるとそのswap回数は求められそうな気がする
• 最終状態は愚直に全探索すると(2N)!個
• 条件を満たすような最終状態を考える.
  • N=2とすると, W1W2B1B2 W1B1W2B2 W1B1B2W2 B1B2W1W2 B1W1B2W2 B1W1W2B2 の6個
  • 最初はW1かB1で,W(i),B(j)の後にはW(i+1)かB(j+1)しか来ない.
  • と言うことは状態数はO(2^2N)であることがわかる
  • O(2^N)はDPできそう
• 上の考察から dp[i][j] := (W(i),B(j)まで並べた時のswap回数) と言うDPは自然に立つ.
• するとW(i), B(j) まで並べた時, W(i+1)を持ってくるためのswap回数が必要になる(Bも同様)
• このコスト,costw[i][j] を考える
  • (先頭i+j個 .. W(i),B(j)までの数) (それ以外で元々W(i+1)より左にあった数) W(i+1) (それ以外)
  • それ以外と言うのはW(i+2),B(j+1)以上の数のことである.
  • つまり,W(i+2),B(j+1)以上でW(i+1)より左にある数を数えれば良い
  • posw(k) := (W(i+1)以上でk番目にある数の個数), posbも同様に置いて,sum(kはw(i+1)より右)(posw(k)) + sum(kはW(i+1)より右)(posb(k)) が高速に求めたい.
  • これはBinaryIndexTreeを使って,後ろからW(N),W(N-1),..と位置を追加していけば一回あたりO(logN)で可能 c.f.反転数の求め方
  • よってcostw, costbはO(N² logN)で埋められる
• DP
  • 遷移 dp[i][j] = max(dp[i-1][j] + costw[i-1][j] , dp[i][j-1] + costb[i][j-1] ) (i-1<0またはj-1<0の時はその項はなし)
  • 初期化 dp[0][0] = 0
  • 答えは dp[N][N]

メモ

考察段階から丁寧に追っていくと割と自然は発想が多いし,勉強になった.
できなかったことは,最終状態から考えていくとこと,小さい数から考察していくこと

コード

累乗の中にmodを入れる操作

a^b = a^{b mod p-1} (mod p) が成り立つ.

proof.

フェルマーの小定理より a^p-1 = 1 (mod p)なので,mod pにおいて
a^b
= a^( (p-1)(floor(b/(p-1)) +(b mod (p-1)))
= ( (a^p-1)^{floor(b/(p-1))}) * a^{b mod (p-1)}
= a^{b mod (p-1)}