競技プログラミングにハマるプログラマのスレ 258 (311ﾚｽ)
上下前次1-新
259: 11/15(土)22:58 AAS
遅刻してunratedだったからGPTに解かせてたんだが、Fだけうまく解いてくれないわ
# A
与えられた 3 つの数字 A, B, C を降順にソートします。
ソート後を大きい方から順に x, y, z とすると、3 桁の整数 xyz が、A, B, C を並べ替えて作れる整数の中で最大になります。
要素数は 3 つだけなので、計算量は定数時間 O(1) です。
# B
X の各桁の数字を取り出して、昇順（小さい順）に並べます。
このとき、先頭が 0 でなければ、その並びを左から連結した数が条件を満たす最小の整数です。
先頭が 0 になってしまう場合は、列の中から最初に現れる 0 以外の数字を探し、それと先頭の 0 を入れ替えます。先頭を「最も小さい非 0」の数字にし、残りは昇順のままにすることで、先頭が 0 でない並べ替えの中で最小の整数になります。
桁数を d とすると、ソートに O(d log d) 時間がかかりますが、d は小さいので十分高速に解くことができます。
# C
D = Y − X, g = gcd(D, X), D’ = D / g とおきます。全員の重さが等しいなら D·(Bi − Bj) = X·(Aj − Ai) より、すべての i について Ai ≡ A1 (mod D’) が必要なので、これをまず確認し、1 つでも外れたら -1 です。
条件を満たすとき、子 1 を基準に D’·(Bi − B1) = X’·(A1 − Ai) (X’ = X / g) から Bi = B1 + Di (Di は前計算) と表せます。
各 i について 0 ≤ Bi ≤ Ai ⇔ -Di ≤ B1 ≤ Ai − Di なので、B1 が取り得る区間の共通部分 [L, R] を求め、L > R なら不可能なので -1 を出力します。
可能なとき、大きい飴の総数 ΣBi = N·B1 + ΣDi は B1 に対して単調増加なので、B1 = R として ΣBi を計算すればよく、計算量は O(N) です。
上下前次1-新書関写板覧索設栞歴
あと 52 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.003s