X



競技プログラミングにハマるプログラマのスレ 258

2025/11/13(木) 23:40:28.70
競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder http://atcoder.jp/
yukicoder http://yukicoder.me/
Codeforces http://codeforces.com/
CodeChef http://codechef.com/
Project Euler http://projecteuler.net/
CLIST http://clist.by/
AtCoder Problems http://kenkoooo.com/atcoder/
AtCoder Clans http://kato-hiro.github.io/AtCoderClans/

前スレ
競技プログラミングにハマるプログラマのスレ 249
https://medaka.5ch.net/test/read.cgi/prog/1756738914/
競技プログラミングにハマるプログラマのスレ 250
https://medaka.5ch.net/test/read.cgi/prog/1757920960/
競技プログラミングにハマるプログラマのスレ 251
https://medaka.5ch.net/test/read.cgi/prog/1758762370/
競技プログラミングにハマるプログラマのスレ 252
https://medaka.5ch.net/test/read.cgi/prog/1759101636/
競技プログラミングにハマるプログラマのスレ 253
https://medaka.5ch.net/test/read.cgi/prog/1759564206/
競技プログラミングにハマるプログラマのスレ 254
https://medaka.5ch.net/test/read.cgi/prog/1760199840/
競技プログラミングにハマるプログラマのスレ 255
https://medaka.5ch.net/test/read.cgi/prog/1761018112/
競技プログラミングにハマるプログラマのスレ 256
https://medaka.5ch.net/test/read.cgi/prog/1761811641/
競技プログラミングにハマるプログラマのスレ 257
https://medaka.5ch.net/test/read.cgi/prog/1762400222/
2025/11/15(土) 12:29:11.34
赤マスさんに解かせたら典型すぎてびっくりしませんかとか言いそう
2025/11/15(土) 12:30:19.43
典型にびっくりはしないだろ
典型を解けないインコにびっくりするだけで
2025/11/15(土) 12:34:34.90
GPT一部抜粋
https://i.imgur.com/xQWbq2J.png
2025/11/15(土) 12:36:33.60
GPTに解説書かせたほうがいいな
2025/11/15(土) 12:40:01.35
糞ライターの糞解説が読めなくなるからやめろ
2025/11/15(土) 13:03:57.36
適当に作ったあと全体に時計回りか 反時計回りで動かして最初にするってことか
賢い
2025/11/15(土) 13:07:30.26
こういう方程式で1文字決め打つのは競プロでも出題される典型ですけどね
2025/11/15(土) 14:45:53.44
ジェネルシのデアトーク凄すぎる
ポテ赤くらいか
2025/11/15(土) 14:45:59.82
OD死ねよ死ぬ死ぬ詐欺きっしょいんだよさっさと死ね
2025/11/15(土) 14:58:51.54
ギュられたくない
ギュられたくない
ギュられたくない
2025/11/15(土) 16:28:05.62
サ終は来年に持ち越しか
2025/11/15(土) 17:29:27.11
ジェネルシすごい俺すごい
2025/11/15(土) 17:29:53.14
サ終前に大放出するのサ終前兆典型すぎるんだよな
お祭りってやつ
2025/11/15(土) 17:30:29.65
AGCの最終問が
AtCoder’s Last Problem
で2026年からアクセスできなくなったらアツイ
2025/11/15(土) 17:39:40.27
りんごの114514番煎じ
2025/11/15(土) 17:40:25.70
rating is just a number定期
2025/11/15(土) 17:41:21.92
ゆきこの1人勝ちというわけね
2025/11/15(土) 20:50:09.25
ABCいきますよーいきますよーいくいく
2025/11/15(土) 20:55:49.79
GPT Benchmark Contest
2025/11/15(土) 21:55:04.48
ちゃっぴーに聞いて答えが出力されるの見てたら悲しくなってきたわ
2025/11/15(土) 22:08:23.01
いいえ、実務では全然使えない><ので、競プロerであることを誇りなさい

https://x.com/chokudai/status/1986763777073922105
コードが長くなるAHCの方はAI使用バリバリOKで、実用上も、問題として出されないとロクにアルゴリズム改善してくれない+解ける/解けないの判定をしてくれないので、ほっといても絶対ダメで、改善できそうな箇所を的確に指示して正当性を確認する、みたいなのがないと実務では全然使えないです><
2025/11/15(土) 22:38:51.92
おちっこ侍
2025/11/15(土) 22:40:01.96
死ねカス
Gが400超えるわけねえだろうがよ
2025/11/15(土) 22:40:40.12
実では全然使えない>< ことを定量的に示しなさい
レッドコーダーは統計データすら読めないんですかあ?はーい
2025/11/15(土) 22:45:45.62
F 今朝スレに貼られてた問題と設定かなり似てるのウケるな
解かれなさすぎだろ
2025/11/15(土) 22:48:46.75
Gは典型と言えば典型だけどまあこの解かれ方はお察し
D解けてないクソ雑魚インコも大量ACしてるし
2025/11/15(土) 22:49:13.85
全国 -240 -140 540 1860 1080 2240 1940
JAP -400 -100 520 1740 1100 2200 1900
2025/11/15(土) 22:50:26.90
D青G青でドカ笑い
んなわけねえだろ死ね
2025/11/15(土) 22:52:31.00
G ACL使ってないインコはまあ怪しいな
2025/11/15(土) 22:53:20.39
ほなratedJAP人狼するか
2025/11/15(土) 22:54:15.45
highlighterが釣れたんだが
2025/11/15(土) 22:55:19.64
今回だけ人狼すんの絶対お前が冷えたからだろ
これまでサボってた分も合わせて漁ってどうぞ
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) です。
2025/11/15(土) 22:58:59.31
# D
初期状態の黒マス集合は 1 個の長方形 [0, X − 1] × [0, Y − 1] です。
各大嵐は、平面を直線 x = Ai(または y = Ai)で 2 つに分け、一方を上(または右)、他方を下(または左)へ平行移動させる全単射なので、黒マス集合は「互いに重ならない長方形の集合」として表現し続けられます。
1 回の大嵐で各長方形は高々 2 個に分割されるため、長方形の総数は高々 2^N(N ≤ 14)です。
最終的な長方形集合に対し、2 つの長方形がマスの辺を共有する(x 区間が重なり y 距離 1、または y 区間が重なり x 距離 1)ときに Union-Find で連結させます。
各連結成分の面積は、その成分に属する長方形の面積の総和として求まり、個数と面積を昇順に出力すればよいです。

# E
数列の順番は関係なく,値の多重集合だけを見ればよいことに気付きます。
l ≤ r のとき,max(l, min(r, a)) は a<l なら l,l≤a≤r なら a,a>r なら r なので,
答えは「a<l の個数×l」+「l≤a≤r の総和」+「a>r の個数×r」で計算できます。
0〜5×10^5 の値ごとに個数と総和を Fenwick 木 2 本で管理し,prefix 和から上式を求めます。
l>r のときは max(l, min(r, a))≡l となるため,答えは常に N×l です。
更新クエリは古い値を 1 個減らし新しい値を 1 個増やすだけなので,各操作は O(log M),全体計算量は O((N+Q)logM) となります。

# F
うんち

# G
二重和を b ごとにまとめ、H[b] = 農a c_A[a]·C(a, b) を全 b について求める。
C(a, b) = a!/(b!(a-b)!) より、H[b] = inv(b!)·農{t≥0} (c_A[b+t]·(b+t)!)·inv(t!)。
A’[a] = c_A[a]·a!、F[t] = inv(t!) とおくと、右辺は A’ と F の反転畳み込みで一括計算できる。
A’ を反転して NTT 畳み込み conv を求め、H[b] = inv(b!)·conv[V-b](V=max(A_i, B_j))。
最終答えは S = 農b c_B[b]·H[b]。
前計算 O(V)、畳み込み O(V log V)、合計 O(V log V)。
998244353 は NTT 可能な素数なので安全に実装できる。
2025/11/15(土) 22:59:56.05
アンレでもコンテスト時間のGPTは規約違反だがお前のAtCIDは
2025/11/15(土) 23:00:53.10
あれ、 農 が 農に化けた?

# G
二重和を b ごとにまとめ、H[b] = 農a c_A[a]·C(a, b) を全 b について求める。
C(a, b) = a!/(b!(a-b)!) より、H[b] = inv(b!)·農{t≥0} (c_A[b+t]·(b+t)!)·inv(t!)。
A’[a] = c_A[a]·a!、F[t] = inv(t!) とおくと、右辺は A’ と F の反転畳み込みで一括計算できる。
A’ を反転して NTT 畳み込み conv を求め、H[b] = inv(b!)·conv[V-b](V=max(A_i, B_j))。
最終答えは S = 農b c_B[b]·H[b]。
前計算 O(V)、畳み込み O(V log V)、合計 O(V log V)。
998244353 は NTT 可能な素数なので安全に実装できる。
2025/11/15(土) 23:01:39.11
ガイジと申しますん
2025/11/15(土) 23:01:55.68
F解いてるジェネルシは信用できる
2025/11/15(土) 23:03:21.74
新スレ長の悪口言うな
2025/11/15(土) 23:03:30.83
インコ農法ってありそう
2025/11/15(土) 23:04:11.08
旧スレ長~🥺
2025/11/15(土) 23:04:24.08
Gの農のところは、総和記号シグマ で読み替えてくれ
2025/11/15(土) 23:05:07.12
GPT使ってないが順位表見たらFよりG行かざるをえなかった
俺はGPTerの被害者なんだ信じてくれ
2025/11/15(土) 23:05:52.25
F解いてる暖色は実力確かだろうな
2025/11/15(土) 23:06:21.15
XOR回廊に次ぐホワイトリスト入り確定か
2025/11/15(土) 23:06:52.36
FスキップしてGだけ解いてるやつは人狼の疑いあり
2025/11/15(土) 23:07:05.13
このF GPTが解けないのまあまあカスじゃね?
結局典型に毛が生えた問題か数学問しか強くないし全然ギュられてねーじゃねーか
2025/11/15(土) 23:08:55.70
何度も試行錯誤してたらやっとF解いてくれたわ
たぶん正しい解法だよな

平均 M = (尿i)/N を計算し,割り切れなければ -1.
di = Ai−M(総和 0)とおき,di≠0 の添字だけを扱う.
「操作 1 回=重み付き有向辺 1 本」と見ると,各連結成分は少なくとも(頂点数−1)本の辺を要し,スパン木で等号達成.
よって di≠0 の集合を「総和 0 の部分集合」に分割したときの成分数を最大化すれば,最小操作回数は m−(成分数)となる.
これは部分集合 DP:dp[mask]=max_{sum[s]=0, s⊆mask}(1+dp[mask\s]) を最下位ビット固定で計算.
復元は各成分で中心 r を取り,正 di を r に集め,次に r から負 di へ配ると |S|−1 回で実現できる。
2025/11/15(土) 23:09:24.55
今年中にtouristに勝つとか言ってなかったか、OpenAI
黄色以下虐殺みたいな中途半端な状態でずっと停滞するんなら、むしろ競プロ上位層の価値上がりそう
2025/11/15(土) 23:09:24.95
F解いてる57人のジャップ、確かによく見るイツメンジェネルシばかりだな
現代において真に競プロをやれてる生き残りはこいつらだけだろうな
2025/11/15(土) 23:09:50.92
>>274
ちょっと違うくね?
2025/11/15(土) 23:10:14.18
hiro1729君がF解いてて笑顔止まらん
俺は信じてたぞ
2025/11/15(土) 23:10:25.95
今度は シグマA が 尿になったわ
シグマの文字化けがおもしろすぎる
2025/11/15(土) 23:10:40.63
尿iは草
俺もコンテスト中に使うか
2025/11/15(土) 23:11:27.36
競プロをやれてる=GPTを使ってない かつ GPTが解けない問題を解ける なので
2025/11/15(土) 23:11:59.77
部分集合DPとかビットDPそのものに到達できるのはインコでも出来るため
実装が大事です
2025/11/15(土) 23:13:26.69
57人のAtCoder浪士
2025/11/15(土) 23:14:23.71
グロタンディーク素数とかいうガチインコネタが湧かないようもう一人解いてくれてれば
2025/11/15(土) 23:14:24.72
簡単にGPTで解ける問題って、それだけでパフォが200〜500ぐらいは下がってそうだな
2025/11/15(土) 23:14:51.54
ホワイトリスト作るか
お気に入りはこいつらだけにして、真の順位表を作ろう
2025/11/15(土) 23:15:16.79
GPTでF普通に解けたが
2025/11/15(土) 23:20:15.03
どれだけの人数がGPTに考察をやらせてるのやら
2025/11/15(土) 23:20:44.24
MHCの時間 カスすぎる
2025/11/15(土) 23:27:06.81
MHCもう良い気がしてきた
夜遅すぎてやる気なくなります
2025/11/15(土) 23:29:05.69
MHCってどこまでやれば何がもらえんの?
2025/11/15(土) 23:33:19.55
あの人も戦争に行きたくないと嘆いてるな
せいじいが政権を止めてれば
2025/11/15(土) 23:37:46.30
今夜?のRound2で2000位に入ればTシャツがもらえる
がさすがにだるすぎるので寝る
2025/11/15(土) 23:38:42.05
布乞食
2025/11/15(土) 23:45:06.58
意外とボーダーガバガバだからもう2着持ってるんだよな
そして次のラウンドでトップ200入ると ワッペンがつく(これは結構凄い)
2000位Tシャツの権威性がほぼないから一応起きるけど眠かったら寝ようかな😴
2025/11/15(土) 23:56:22.68
Tシャツ獲得即就寝するか
でもあれ提出めんどいんだよな
2025/11/15(土) 23:56:34.81
実質時給あげるか 早時して
2025/11/15(土) 23:57:19.76
すごいつってもその凄さがわかるの全世界に1000人いるかすら怪しいレベルだろ
2025/11/16(日) 00:05:22.97
Meta入社チャンスなら全員カフェイン決めまくって徹夜するだろうに
2025/11/16(日) 00:07:38.23
kaggleガチるのが正解だったか
むしろAI有効活用すべきで現代に合ってるし
2025/11/16(日) 00:09:54.49
新卒で就職するのやめとくか
UT情報ならDでもなんとかなるだろ
2025/11/16(日) 00:12:21.21
明日はARCとCFdiv1がありますよ
2025/11/16(日) 00:58:53.55
ARCのA300点、インコ釣り枠すぎる
2025/11/16(日) 00:59:14.55
てか今日のC ARC-A以上の器だろ
2025/11/16(日) 01:20:47.10
div2Aに置いてもええけど置く場所変えても味は変わらんぞ
2025/11/16(日) 01:33:00.70
負の飴の重さとか飴の所持数に上限追加とか舐め腐った問題文にしたらARCに持ってきていいぞ
持って来るな死ね
2025/11/16(日) 01:39:58.68
https://x.com/antinomie2/status/1862905495121711108?s=46&t=o7wkoiDtuIpGvQUYO9vkRQ

チャイナジェネルシが名門コウリッショーをまとめているので、これを考慮して住居を選びなさい
戦いは中受前から始まってますよ
2025/11/16(日) 02:28:51.65
眠いから寝るわ
ごめん
来年もMHCやってたら出るね
2025/11/16(日) 02:31:44.45
は?FAKEやめてね
明日からお前の名前はインコです
2025/11/16(日) 06:20:09.72
カスの実装量
2025/11/16(日) 06:28:02.13
ワッペン!🧸 ワッペン!🧸
2025/11/16(日) 09:20:04.47
死ねよヒトカス
2025/11/16(日) 09:45:00.47
宇宙人、絶えなさい
2025/11/16(日) 13:00:46.28
🦜「遺伝支配的!」
👽「全方位敵DP」
🐵「宇宙人死ね」
🤓「TKNDKS!UTIS!松尾研!GAFAM!GS!」
🤡「GPT!AI!ギュ鳴らしに備えろ!」
2025/11/16(日) 13:02:57.61
これスレの紹介文に使えるな
nimさん、宣伝していいですよ
2025/11/16(日) 13:04:49.36
>>314
🧸「いばしょ ともだち」

わすれないでね😿
2025/11/16(日) 13:06:13.56
>>314
👽の発言にジェネルシも入れろ
2025/11/16(日) 13:22:17.88
まるでこのスレが異常者の集まりみたいじゃないか
2025/11/16(日) 13:29:14.15
事実の曲解やめてね
2025/11/16(日) 13:52:59.23
憧れて模倣しなさい
2025/11/16(日) 14:36:11.25
https://weblab.t.u-tokyo.ac.jp/startups/
【朗報】Polaris.AIホンモノだった
2025/11/16(日) 14:53:14.97
>>320
学ぶことは真似ぶことだからな
2025/11/16(日) 15:03:11.63
真似ぶキモいオナニー語源主張やめろ死ね
2025/11/16(日) 15:07:42.66
>>320
>>322

憧れるのをやめなさい
遺伝支配的なので無意味
擬態インコ
ただのパクリ
完全下位互換に帰着される
真似される側にとっては迷惑(直球)
2025/11/16(日) 15:08:55.07
街中とか試験会場とかで急に叫んだりキチゲ発散したくなるの俺だけじゃないよな?
というか失うものないし別にやってしまってもいいか
2025/11/16(日) 15:12:38.71
ツイートがとがっていた人たち、働き始めるとツイートが丸くなってしまい悲しい
のいみさんもいつか丸くなるのかな
レスを投稿する

5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。

ニューススポーツなんでも実況