競技プログラミングにハマるプログラマのスレ 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/30(土) 23:23:33.43

自明問早解きしか出来ない

**仕様書無しさん** · 2024/03/30(土) 23:23:38.57

自分よりレート低い人がwriterやってるの違和感

**仕様書無しさん** · 2024/03/30(土) 23:23:50.45

>>705
へんさち65未満の高校だとポテンシャル黄色はほとんどいないんじゃないか

**仕様書無しさん** · 2024/03/30(土) 23:23:52.84

こどふぉ

**仕様書無しさん** · 2024/03/30(土) 23:24:01.24

>>722
div1ratedだからね　ABCunrated者が多い

**仕様書無しさん** · 2024/03/30(土) 23:24:29.23

3hは普通に長いからやりたくないが明日AGCあるしまあ

**仕様書無しさん** · 2024/03/30(土) 23:26:04.85

声の高い謎のおっさんが提供している指標よりこどふぉのレートのほうが大事

**仕様書無しさん** · 2024/03/30(土) 23:26:53.97

ジャップランドよりも国際的だしね
英語が読めない国際社会の未定義動作にだけはなるな

**仕様書無しさん** · 2024/03/30(土) 23:27:29.45

声の高い謎のおっさんが提供している謎の指標、一体なんなんだ

**仕様書無しさん** · 2024/03/30(土) 23:27:44.63

競プロの性質上、(受験勉強などで)長時間考えることに慣れてる人が多いってのもあるのかな

**仕様書無しさん** · 2024/03/30(土) 23:27:57.27

dpはこれができずに発狂不可避

**仕様書無しさん** · 2024/03/30(土) 23:28:47.89

声の高い謎のおっさんですらTKなのに

**仕様書無しさん** · 2024/03/30(土) 23:29:24.13

KS落ちTK

**仕様書無しさん** · 2024/03/30(土) 23:30:27.90

こどふぉやるか～
途中でダルくなって撤退しそうだが

**仕様書無しさん** · 2024/03/30(土) 23:31:13.38

声の高い謎のおっさんですら美人妻がいるのに俺ときたら...

**仕様書無しさん** · 2024/03/30(土) 23:31:51.36

あとこれも発狂できる
dpだとだるすぎてクリアできません

**仕様書無しさん** · 2024/03/30(土) 23:32:49.99

>>738
年収は？

**仕様書無しさん** · 2024/03/30(土) 23:33:16.57

結局競プロ外も中受支配的か

**仕様書無しさん** · 2024/03/30(土) 23:33:28.20

声の高い謎のおっさん応援スレ

**仕様書無しさん** · 2024/03/30(土) 23:37:44.47

レート800台から抜け出せないねぇ

**仕様書無しさん** · 2024/03/30(土) 23:48:50.42

某8くん、失敗したらすぐ病んで垢名変えるとこはマスくんにそっくり

**仕様書無しさん** · 2024/03/30(土) 23:51:43.80

病み方草
名前芸やめちくり

**仕様書無しさん** · 2024/03/30(土) 23:56:25.38

中学生でもわかる深層学習読もうとして、その執筆者の垢名が競技者失格なのを目にする人を考えたら笑うな

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

人間失格、つまり非人間であることを自覚するインコ

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

マスくんクルド人差別はよくない

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

クルドインコと呼べ

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

急に人間味あるツイートするのやめろ面白いから

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

マスくんは3ヶ月あたりで緑パフォ出せるようになってるあたり明らかに天才寄りなので、もっと自信もってがんばってくれ
緑にも到達できなくて泣いてる人なんていくらでもいるぞ自信を持て

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

下には下がいることを知る毎日

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

日本から出ていくべきは外来種インコである君ですよね

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

国籍を知ってる辺りある程度交流があると伺える

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

マスくんって外国産の鳥なの？

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

マスくん、#9110に電話して相談するといいよ

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

珍しくスレ長が正論言ってるぞ

**ager** · 2024/03/31(日) 01:05:12.30

万年青水反復コーダーの思考ともいえる

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

クルドといえば埼玉のあの都市だけどもしかして

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

Dナップサックに帰着出来ちゃうから上位K個を持つDPで解けなかったらやばいだろと思って解けたのは良かったけどEわからん
偶奇に注目して重複組合せでいけそうなんだが

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

E解けないです
才能の壁感ある
上振れたときにMいったけど紫上位が適正感ある

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

もまいらもう寝ちゃった？
さみしー泣

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

真似っこ戦略で偶奇保てるってところまでわかったのに何故か会わなかったんだけどなあなあ

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

真似っ子で勝てるのは俺もわかったので部分点くーださい

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

コンテスト感想の真似っこやめてね

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

あんなにスレでオウム返しオウム返し言ってたのに一瞬で真似っこ戦略が思いつけないのは過去スレ精進がたりてないぞ

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

真似っ子が思いついても左右動があるから真に正しいか示すの大変なんだが？
mod998を超えられなかったやつくらい山程いるだろなにが感想の真似っ子じゃ

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

こどふぉ終わってから失神してた

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

E、反転させたら一緒になるから一方向だけ考えれば良い

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

チャンコロライター陣がちゃんころ問題パクてるんだから既出なのは当たり前だろｗ

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

ガイジスレ終了

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

今日のAGCで0完して俺も競技者失格してしまったらどうしよう

**仕様書無しさん** · 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

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