D - 桁和 / Digit Sum 概略 2以上のbと1以上の整数nで、nをb進数で表した時の各桁の和がsとなる最小のbをもとめよ 制約 1≤n≤10111≤n≤1011 1≤s≤10111≤s≤1011 n,sn,s はいずれも整数である 解法 制約が10^11なので全探索は間に合わない。とりあえずルートを取…

D - Two Sequences 長さNの数列 a,bが与えられる。 ai bjのN^2の全ての選び方について、ai + bjを計算しする。 それらのxorを求めよ 制約 入力は全て整数 1≤N≤200,0001≤N≤200,000 0≤ai,bi<228 解法 愚直に計算すると間に合わない。 xorは繰り上がりしないの…

B - Moderate DifferencesNこのマスがあり、左端にAが、右端にBが書かれている 隣接する全てのマスで、整数の差がC以上D以下に出来るか判定せよ3 A 10^9 B 10 ^9 0 自分の解法一マスごとに足した場合の区間と引いた場合の二通りの区間があるため、答えに近い…

D - Simple Knapsack 1≦N≦100 1 W 10^9 1 wi 10^9 w 1 vi 10^7与えられる重さが4種類しかないナップザック [i個目を選ぶ時][選んだ個数][端数の合計を足した]の3次元で解いてみた問題の芯 範囲が広くても、複数のまとまりになっていると分かる場合は、調べる…