競技プログラミングにハマるプログラマのスレ 258 (311ﾚｽ)
上
下
前
次
1-
新
259
: 11/15(土)22:58
AA×
[
240
|
320
|480|
600
|
100%
|
JPG
|
べ
|
ﾚｽ栞
|
ﾚｽ消
]
259: [sage] 2025/11/15(土) 22:58:43.86 遅刻して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) です。 http://medaka.5ch.net/test/read.cgi/prog/1763044828/259
遅刻してだったからに解かせてたんだがだけうまく解いてくれないわ 与えられた つの数字 を降順にソートします ソート後を大きい方から順に とすると 桁の整数 が を並べ替えて作れる整数の中で最大になります 要素数は つだけなので計算量は定数時間 です の各桁の数字を取り出して昇順小さい順に並べます このとき先頭が でなければその並びを左から連結した数が条件を満たす最小の整数です 先頭が になってしまう場合は列の中から最初に現れる 以外の数字を探しそれと先頭の を入れ替えます先頭を最も小さい非 の数字にし残りは昇順のままにすることで先頭が でない並べ替えの中で最小の整数になります 桁数を とするとソートに 時間がかかりますが は小さいので十分高速に解くことができます とおきます全員の重さが等しいなら よりすべての について が必要なのでこれをまず確認し つでも外れたら です 条件を満たすとき子 を基準に から は前計算 と表せます 各 について なので が取り得る区間の共通部分 を求め なら不可能なので を出力します 可能なとき大きい飴の総数 は に対して単調増加なので として を計算すればよく計算量は です
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 52 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
ぬこの手
ぬこTOP
0.040s