競技プログラミングにハマるプログラマのスレ 258 (365ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
7: 11/13(木)23:54:59.86 AAS
外部ﾘﾝｸ[html]:resemom.jp
入賞者の声として、広島大学附属福山中学校のpolaris020は「本大会を通じて、仲間との協力の大切さを改めて実感しました。互いにアイデアを出し合い、試行錯誤を重ねる中で、一人では気づけなかった視点や解法に出会うことができました。助言を交わしながら成長できた時間は、かけがえのないものです。この経験を糧に、さらなる挑戦を続けていきます。」と述べた。
画像ﾘﾝｸ
162: 11/14(金)22:01:15.86 AAS
負けイン コ
170: 11/14(金)22:43:55.86 AAS
有史以来このスレに読む必要のあることが書かれていたことはない
259: 11/15(土)22:58:43.86 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-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.020s