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

**仕様書無しさん** · 2024/03/26(火) 23:36:10.62

競技プログラミング、オンラインジャッジ、プログラミングコンテストや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/

前スレ
競技プログラミングにハマるプログラマのスレ 161
https://medaka.5ch.net/test/read.cgi/prog/1709363800/
競技プログラミングにハマるプログラマのスレ 162
https://medaka.5ch.net/test/read.cgi/prog/1709602428/
競技プログラミングにハマるプログラマのスレ 163
https://medaka.5ch.net/test/read.cgi/prog/1709897526/
競技プログラミングにハマるプログラマのスレ 164
https://medaka.5ch.net/test/read.cgi/prog/1710220809/
競技プログラミングにハマるプログラマのスレ 165
https://medaka.5ch.net/test/read.cgi/prog/1710398066/
競技プログラミングにハマるプログラマのスレ 166
https://medaka.5ch.net/test/read.cgi/prog/1710650865/
競技プログラミングにハマるプログラマのスレ 167
https://medaka.5ch.net/test/read.cgi/prog/1710987911/

**仕様書無しさん** · 2024/03/31(日) 08:00:38.12

マジでAGCで橙パフォ以上頼む

**仕様書無しさん** · 2024/03/31(日) 08:06:40.64

0完でレートが増えるバカのコンテスト最高
黄色は出るだけ期待値損

**仕様書無しさん** · 2024/03/31(日) 08:15:38.58

0完太陽なのにレートが上がる欠陥制度あざす笑
マイナスサムゲームのratedパチンコふるって参加してくれよな

**仕様書無しさん** · 2024/03/31(日) 08:23:12.50

0完でも温まるのほぼ確定な水インコがイキイキしてるな

**仕様書無しさん** · 2024/03/31(日) 09:10:26.87

イキリインコ

**仕様書無しさん** · 2024/03/31(日) 09:11:10.20

黄色のあの人は今日橙色に戻れるの？

**仕様書無しさん** · 2024/03/31(日) 09:19:35.56

【結婚難】時間外労働で共働き妨害【孤独死】

☆犠牲になるのはSEの結婚相手☆

SEは非婚や離婚や中絶や少子化や親不孝を促進

・キモい
・モラルない
・ファッションセンスない
・コミュニケーション苦手
・時間外労働違反で共働き妨害
・人売屋に開発報酬を奪わせる
・人売屋に知的財産を奪わせる
・裁判官が技術判断不正をする

SEは開発料金の詐欺被害で結婚できない
https://codelearn.jp/articles/about-engineer-marriage

**仕様書無しさん** · 2024/03/31(日) 09:38:49.20

AGCの暖色diff自力AC出来ると濃いの出る

**仕様書無しさん** · 2024/03/31(日) 09:44:49.53

https://zukan.pokemon.co.jp/detail/0931-1

イキリ水インコの参考画像貼っておきます

**仕様書無しさん** · 2024/03/31(日) 09:49:17.20

安直すぎるからペラップにしろ

**仕様書無しさん** · 2024/03/31(日) 09:49:26.32

黄色のイキリンコはとくに荒っぽい。ほかの鳥ポケモンを街から追い出したこともある。
↑完全に黄色タッチインコ大王の説明文

大きいグループは 50匹を超える。エサを求め街中や森を騒がしく飛びまわる。
↑完全に馴れ合い寒色インコの説明文

街中で暮らすことを好む。羽の色でグループを作り縄張り争いを繰り広げる。
↑完全にratismの説明文

**仕様書無しさん** · 2024/03/31(日) 09:49:47.23

全てが繋がってるんだよね

**仕様書無しさん** · 2024/03/31(日) 09:55:30.43

繋がってないです
なんでも繋げるな

**仕様書無しさん** · 2024/03/31(日) 09:56:20.12

典型に帰着させる能力は競プロでは大事だからな

**仕様書無しさん** · 2024/03/31(日) 10:07:35.26

>>772
そもそもまだ競技者の土俵に立ってすらいないだろ

**仕様書無しさん** · 2024/03/31(日) 10:14:24.11

プロ失格と言わなかっただけ彼は良識あるよ

**仕様書無しさん** · 2024/03/31(日) 10:18:30.95

競プロじゃなくてただの競になってしまったわけだな

**仕様書無しさん** · 2024/03/31(日) 10:26:33.40

FをM×Mタイルを○枚置く最大利得に読み替えたら解ける？
計算量は無視してよく解けるかどうか

**仕様書無しさん** · 2024/03/31(日) 10:36:53.83

>>790
それが効率的に解けるのであれば今回のFもそれに帰着させることでわざわざ場合わけ(分割)せずとも解けるわけだから、愚問ではないか

**仕様書無しさん** · 2024/03/31(日) 10:38:00.45

難しいことが既知とされている一般的な問題に帰着させるのは計算量理論での証明典型

**仕様書無しさん** · 2024/03/31(日) 10:38:53.33

正直4でもだいぶ苦しそう

**仕様書無しさん** · 2024/03/31(日) 10:40:05.28

ワンチャンフローとかで出来たりするかもだが

**仕様書無しさん** · 2024/03/31(日) 10:42:29.94

>>791
N^2マスためし塗りしてM^2の矩形の個数を数える愚直解O(2^N^2×N^2×M^2)より効率的な解法は存在するか？という意味です

**仕様書無しさん** · 2024/03/31(日) 10:47:48.15

この前のABC-DみたいにバックトラックDFSで枝狩りすれば定数倍は良くなりそうだけど流石に指数時間から落とすのは苦しそう

**仕様書無しさん** · 2024/03/31(日) 10:50:36.77

bitDPでN≦9なら解けるか
P=N-M+1と置くとO(N×M^P×P^(N/M))
M=1はソートして貪欲

**仕様書無しさん** · 2024/03/31(日) 10:51:48.19

盤面に置いた個数を持たないとだめだから計算量もっと悪かったわ

**仕様書無しさん** · 2024/03/31(日) 10:53:43.81

>>796
置く個数が4個5個なら耐えそう

**仕様書無しさん** · 2024/03/31(日) 10:54:06.11

M=2も2次元DPで回転と反転で8通り網羅(二つの位置関係を↘︎)させればN^2でいける

**仕様書無しさん** · 2024/03/31(日) 10:54:55.48

>>799
Mが小さい時(というよりN-Mが大きい時)に全く耐えません

**仕様書無しさん** · 2024/03/31(日) 10:57:33.79

>>801
なんで？
置く候補地は高々(N-M+1)^2通りで、ここからたとえばK個を選ぶんだろ
(N-M+1)^2 choose KだからK乗で抑えられるだろ
いやこれを耐えるというのは詐欺かも

**仕様書無しさん** · 2024/03/31(日) 10:58:56.31

今回のN=1000、K=3ですら無理な時点ではい

**仕様書無しさん** · 2024/03/31(日) 10:59:44.38

ぜんぜんN=10とかでいいんだけど

**仕様書無しさん** · 2024/03/31(日) 11:01:38.58

いうて10^8～10^9オーダーだしもしかして今回のF異常高速化頑張れば愚直バックトラックDFSで通っちゃったりする？

**仕様書無しさん** · 2024/03/31(日) 11:02:58.52

>>805
2乗忘れてたから大嘘だった　通るわけない

**仕様書無しさん** · 2024/03/31(日) 11:03:00.41

10^18くらいになると思うんだけど

**仕様書無しさん** · 2024/03/31(日) 11:03:45.96

はい

**仕様書無しさん** · 2024/03/31(日) 11:03:51.37

>>800
置く個数が無限だとしても無理じゃねえ？
11000
11220
00220
33044
33044
とかどうすんの

**仕様書無しさん** · 2024/03/31(日) 11:04:21.33

>>809
すまんK＝2の間違いだった
置く個数2つ

**仕様書無しさん** · 2024/03/31(日) 11:06:38.42

AGCマジで勝ちたい

**仕様書無しさん** · 2024/03/31(日) 11:07:08.11

>>810
あはい

**仕様書無しさん** · 2024/03/31(日) 11:11:32.29

K=2が典型23貼るだけだから高速化は不可能おわり！平定！

**仕様書無しさん** · 2024/03/31(日) 11:13:02.35

それを言いたいならM=3だろ

**仕様書無しさん** · 2024/03/31(日) 11:13:56.33

M=2だった　すいません

**仕様書無しさん** · 2024/03/31(日) 11:14:51.00

インコ仕草だらけ　あーもうめちゃくちゃだよ

**仕様書無しさん** · 2024/03/31(日) 11:16:55.54

病気は治さなくて良いのかい

**仕様書無しさん** · 2024/03/31(日) 11:18:29.44

どうでもいいゴシの話してるよりはこっちの方がいいけどな

**仕様書無しさん** · 2024/03/31(日) 11:24:41.14

ろくずっぱ推敲せず見切り発車でレスする思慮の浅い仕草のこと（29字）

**仕様書無しさん** · 2024/03/31(日) 11:30:55.93

昨日のABC-DでもコーナーケースでWA出してそう

**仕様書無しさん** · 2024/03/31(日) 11:31:31.92

ゴシインコ集団スヤスヤ睡眠中

🦜💤　🦜💤

**仕様書無しさん** · 2024/03/31(日) 11:31:49.54

水未満はゴミ水以上は誤差
明治未満はゴミ明治以上は誤差

**仕様書無しさん** · 2024/03/31(日) 11:33:30.88

水になるのにアルゴリズムは必要ないと社長が言ってるので水以下は誤差

**仕様書無しさん** · 2024/03/31(日) 11:34:08.06

ageカス起床でデアスレタイムもおしまいか

**仕様書無しさん** · 2024/03/31(日) 11:40:29.50

フローは二部グラフに落ちなかったので無理と判明

**仕様書無しさん** · 2024/03/31(日) 11:46:10.14

昨日のDのコーナーケースってなんだよ

**仕様書無しさん** · 2024/03/31(日) 11:56:27.76

ゴシゴシゴシゴシ！

**仕様書無しさん** · 2024/03/31(日) 12:34:50.01

a=b=60
C=2^59+2^58
Yes
A,B100桁

**仕様書無しさん** · 2024/03/31(日) 12:36:26.62

C 000…0110…00
A 111…1100…00
B 111…1010…00
みたいに末尾ゼロ埋めすると死ぬんじゃね
コーナーケースというより誤読だがXで落ちてるのはだいたいこんなのばかり

**仕様書無しさん** · 2024/03/31(日) 12:46:26.98

0の場合でバグる場合もありそうだし、実装次第では結構場合わけ忘れでペナ踏みそう

**仕様書無しさん** · 2024/03/31(日) 12:55:08.55

おまんこビッチ

**仕様書無しさん** · 2024/03/31(日) 13:04:27.50

>>830
脳内管理する値が多いから飲酒してたらペナ量産しそう
dp復元のほうがかえって安全確実な可能性あるな

**仕様書無しさん** · 2024/03/31(日) 13:17:30.38

AGC-A異常構築問の予感しかしない

**仕様書無しさん** · 2024/03/31(日) 13:35:55.86

こどふぉの仮想通貨がもらえる条件って何？

**仕様書無しさん** · 2024/03/31(日) 13:36:39.42

インコイン

**仕様書無しさん** · 2024/03/31(日) 13:48:42.76

年度末にインコイン暴落するって言われてたけどぜんぜん落ちなかったな
大荒れの双子回から私はゴミカステストを作りました->b->UT3人ときて大崩れなし

**仕様書無しさん** · 2024/03/31(日) 14:00:57.68

今日のAGC、太陽あるな

**仕様書無しさん** · 2024/03/31(日) 14:04:04.51

ぽかぽか陽気にあてられて競技者失格氏のメンタルもすくすく回復

**仕様書無しさん** · 2024/03/31(日) 14:06:08.30

競技者失格おもろすぎる

**仕様書無しさん** · 2024/03/31(日) 14:10:58.03

競技者失格さんとキングオブガイジさん好き

**仕様書無しさん** · 2024/03/31(日) 14:11:48.42

ABCでの負けをAGCで取り返さなくていいのか？

**仕様書無しさん** · 2024/03/31(日) 14:13:03.35

ABC負け(パフォカンスト)

**仕様書無しさん** · 2024/03/31(日) 14:44:39.82

ABCは初心者向けなので普通の競技者なら誰でもパフォカンストします

**仕様書無しさん** · 2024/03/31(日) 14:45:28.83

競技者として失格になっても統合は失調しないよう気を付けましょう

**仕様書無しさん** · 2024/03/31(日) 15:09:27.30

e8様に人生を否定されたみたいでつらい

**仕様書無しさん** · 2024/03/31(日) 15:22:06.68

水以上は一人前の競技者と言えるが、水未満は人間ですらない
明治以上は一人前の高学歴と言えるが、明治未満は人間ですらない

**仕様書無しさん** · 2024/03/31(日) 15:24:01.47

こんな童貞になってはいけません

**仕様書無しさん** · 2024/03/31(日) 15:31:39.36

ゆきこおわり
バランス調整やりますねえ！
昨日のインコ虐殺コン運営はこの難易度を見習うんやど

**仕様書無しさん** · 2024/03/31(日) 15:53:30.05

どうでもいいけどさ、くんの質問箱の回答って質問に対する回答になってないことが多くないか？

e.g.
これからはAですか？

はい。ですが音ゲーが～。誹謗中傷が～。精神が～。(結局回答になっていない)

**仕様書無しさん** · 2024/03/31(日) 15:53:54.08

どうでもいいなら書き込まなくていいです

**仕様書無しさん** · 2024/03/31(日) 15:54:51.76

マジで重要で俺は興味津々なんだけどさ、くんの質問箱の回答って質問に対する回答になってないことが多くないか？

e.g.
これからはAですか？

はい。ですが音ゲーが～。誹謗中傷が～。精神が～。(結局回答になっていない)

**仕様書無しさん** · 2024/03/31(日) 15:56:31.69

マジで重要なら書き込んでください

**仕様書無しさん** · 2024/03/31(日) 16:04:25.26

くん…
https://marshmallow-qa.com/messages/e78e5983-a34f-48e0-8d10-af04a3186f86?utm_medium=twitter&utm_source=answer

**仕様書無しさん** · 2024/03/31(日) 16:04:32.45

マジで重要というので回答すると地に足ついてない子供の思考が抜けてない
自責で行動する大人の段階よりも手前の、言いつけを守る子供の段階にいるものだから、何も言いつけなかった癖にいきなり責任被せんな！となっているわけ
質問箱の回答が子供の夢想じみているのも子供特有の計画性のなさが原因かな

**仕様書無しさん** · 2024/03/31(日) 16:04:36.22

マジで重要な問題だしもう競プロなんかやってる場合じゃないな

**仕様書無しさん** · 2024/03/31(日) 16:05:01.85

もう回答したので競プロに戻ってよいですよ

**仕様書無しさん** · 2024/03/31(日) 16:06:00.41

審議が不十分なので競プロには戻れません

**仕様書無しさん** · 2024/03/31(日) 16:06:32.63

審議の余地がないので却下します

**仕様書無しさん** · 2024/03/31(日) 16:09:35.26

八勝って治療できないのかな
不治の病？

**仕様書無しさん** · 2024/03/31(日) 16:45:29.93

真の競プロerなら昨日今日とオンサイトコンテストにちゃんと参加してるよな？

**仕様書無しさん** · 2024/03/31(日) 16:49:47.52

4留1休学中退のワイ高みの見物
国立学費安いんだからどれだけかかろうが卒業さえできればええやろ

**仕様書無しさん** · 2024/03/31(日) 16:53:04.54

国立安いって言うがまさか親に払ってもらってないだろうな？奨学金で借金背負うにしても卒業後の負担小さくないよ

**仕様書無しさん** · 2024/03/31(日) 16:54:35.42

>>860
オンサイト参加しないやつは完全にエアプだからな

**仕様書無しさん** · 2024/03/31(日) 16:55:01.46

学業なんて失敗しても一時の恥だから家族関係のほうが大事だよ

**仕様書無しさん** · 2024/03/31(日) 16:59:44.72

わざわざインココンのオンサイトに行くかよw

**仕様書無しさん** · 2024/03/31(日) 17:01:09.47

国立でも4回浪人か留年したら私立と変わらんしな

**仕様書無しさん** · 2024/03/31(日) 17:01:35.91

私立で留年してるけど環境にブツブツ言ってるやつ

**仕様書無しさん** · 2024/03/31(日) 17:04:35.38

親に1000万近く学費出して貰ってるくせに環境に文句を言ってるやつ

**仕様書無しさん** · 2024/03/31(日) 17:06:11.29

マスくん…

**仕様書無しさん** · 2024/03/31(日) 17:06:48.98

プーチンだってキンペイだってあんなに広い領土があっても環境に文句を言って戦争しちゃうんだし仕方ないよ

**仕様書無しさん** · 2024/03/31(日) 17:09:18.64

マスくんの憧れはプーチンとキンペイ

**仕様書無しさん** · 2024/03/31(日) 17:11:23.26

こどふぉの爺angryの写真って彼女？