kwm_t

kwm_tのメモ

ABC258

おおやらかしの巻
■A - When?
x = 21 * 60 + k
printf("%02d:%02d", x / 60, x % 60);
■B - Number Box
Bにしては難しいしめんどう
配列外参照に注意
■C - Rotation
先頭箇所のインデックスを持つ
■D - Trophy
ステージ1をクリアする最大値を全探索
■E - Packing Potatoes
周期性。
尺取法でいいところを適当にセグ木使ったらバグった
■F - Main Street
時間あったら通せるけど。
1:大通りを使わない
2:大通りにでてともに同じ大通りにいる
3:大通りにでて更に近場の交差点に出てそこから最短距離((4*2)^2)
■G - Triangle
bitset高速化についての記憶を紛失していました。
■Ex - Odd Steps
これ簡単ですね。
AがなくてSを一気に出すことを求められているのなら行列累乗で簡単に解けます。
なので、Aのときの値を順々に求めて次のAを求めるようにすれば良い。

PAST10

■A - 3枚のカード
はい
■B - 花束
min(x/a,y/b)
■C - Go Further
難読
■D - ハイスコア
O(NT)
■E - 良い日付
"3000/03/03"
"2000/02/02",
"2000/02/20",
"2000/02/22"

"2111/11/11",
"2111/11/12",
"2111/11/21",
"2111/11/22",

"2111/12/11",
"2111/12/12",
"2111/12/21",
"2111/12/22"
候補はこれぐらい2,3,4文字は適当に変える
■F - 地図の塗り分け
全部試す
■G - 方程式
二分探索
■H - 連結成分
マージテク
■I - 対称変換
やるだけ
対称軸を求める
//ここまで一時間ぐらい
■J - 区間の期待値
全部異なるので楽。
Aiが最小値になる組み合わせ、最大値になる組み合わせは簡単にわかる。
■K - 旅行計画
二方向からダイクストラをする
■L - N mod M
繰り返し2乗法
c++ならlog2つついても通る
■M - ランキング
座圧してセグ木と思ったけど
クエリ先読みは癪なので
Trie木でええやろと思って投げると1969 ms
unordered_mapで1641 ms
■N - 400億マス計算
畳み込むだけなんだけど
convolutionじゃ通らないのでconvolution_llを使う必要がある
■O - 3-順列
連結成分のつなぎ方はずべて0か1と2で二部マッチングになる必要がある。

ARC143

ARCは3-4-5以外出るな
■A - Three Integers
a = w + x + y
b = w + x + z
c = w + y + zであって
w,x,y,z>=0でwを最大にしたい
a+b+cが奇数ならとりあえずwを一回してみる
max(a,b,c)=cのとき
x,y,zをa,b,c,wで表すと
x = (a+b-c-w)/2;
y = (a-b+c-w)/2;
z = (-a+b+c-w)/2;
なのでa+b-c>=0が必要でこの上でwを最大回数行う(偶数回)
■B - Counting Grids
NGマスは1つしかない事がわかる
よって答えは
全体-(NGマスの場所の候補)*(NGに関わる2n-1個の選び方)*(それらの並べ方)*(残りの並べ方)
fact[n*n]-n*n*c(n*n,2*n-1)*fact[n-1]*fact[n-1]*fact[(n-1)*(n-1)]
■C - Piles of Pebbles
こういうのとけませんねん
mod x+yで考えるのはそれはそう。
すべてがxより小さければ、先手が何もできないので後手が勝つ
上の条件を満たさないときのことを考える
x<=yとx>yで場合分けする
x<=yのとき
a>=xなもの全てにa-=xすると後手が何もできなくなるので先手の勝ち
x>yのとき
a

Codeforces Global Round 21

Dで時間使いすぎたので大冷えを覚悟したけど
意外と2013->2034
■A. NIT orz!
max(a_i|z)
■B. NIT Destroys the Universe
高々2回でできる
■C. Fishingprince Plays With Array
全部バラしておなじになるか
■D. Permutation Graph
1とnを持つ箇所を両端に持つ区間から初めて伸ばしておく
ほんまか?
■E. Placing Jinas
二項係数の斜め和
これはホッケースティック

ABC257

糞ムーブ。
DEの実装に手間取りすぎ、ペナ出しすぎ
Fを詰めきれてないのがダメ。
Gを先に読むべき
■A - A to Z String 2
はい
■B - 1D Pawn
問題のとおりにシュミレーション
■C - Robot Takahashi
雑にやるだけ
■D - Jumping Takahashi 2
二分探索をおこなう
intで収まらないことに注意
■E - Addition and Multiplication 2
桁数を決めて、それを満たすように貪欲に
■F - Teleporter Setting
超頂点を用意して後ろと前からbfs
超頂点の扱いを間違う。
■G - Prefix Concatenation
z_algorithm(ACL)
双対セグ木(区間chmin,一点取得)
■Ex - Dice Sum 2
あとで解説を読む