[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 168 (794ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
1(1): 仕様書無しさん [sage] 2024/03/26(火)23:36
競技プログラミング、オンラインジャッジ、プログラミングコンテストや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
2chｽﾚ:prog
競技プログラミングにハマるプログラマのスレ 162
2chｽﾚ:prog
競技プログラミングにハマるプログラマのスレ 163
2chｽﾚ:prog
競技プログラミングにハマるプログラマのスレ 164
2chｽﾚ:prog
競技プログラミングにハマるプログラマのスレ 165
2chｽﾚ:prog
競技プログラミングにハマるプログラマのスレ 166
2chｽﾚ:prog
競技プログラミングにハマるプログラマのスレ 167
2chｽﾚ:prog
695: 仕様書無しさん [sage] 2024/03/30(土)23:03
あーF2つの最大値を回転+dpするところまでは出来てたから二次元セグ木持ってたら解けたわゴミすぎ
696(1): 仕様書無しさん [sage] 2024/03/30(土)23:03
何行目まで使ったかと何列目まで使ったかを持って、新たにm行以上使用して区間maxじゃダメ？
ちょっと分からんので図示してくれ
697: 仕様書無しさん [sage] 2024/03/30(土)23:03
>>683
なるほど
698(1): 仕様書無しさん [sage] 2024/03/30(土)23:03
>>696
サンプル1から無理じゃね？
699(1): 仕様書無しさん [sage] 2024/03/30(土)23:05
新たにm行or列使えば必ずその領域上にmの正方形が作れる性質で行けそうじゃない？
700(1): 仕様書無しさん [sage] 2024/03/30(土)23:05
>>698
右上からやれば出来そうじゃない？
701: 仕様書無しさん [sage] 2024/03/30(土)23:06
Eとかいうのかなりやるだけで完全に空気
702: 仕様書無しさん [sage] 2024/03/30(土)23:07
のこのバランス感覚すげーな
C350を主張したのかなり偉い
703: 仕様書無しさん [sage] 2024/03/30(土)23:07
>>700
どう遷移させてるの
704: 仕様書無しさん [sage] 2024/03/30(土)23:08
クルド人街は殺傷事件があっても警察はアンタッチャブル
705(2): 仕様書無しさん [sage] 2024/03/30(土)23:10
黄になる程度だったら競プロに才能なんて関係ないだろ
高校卒業できる程度の低能があるなら努力すれば誰でも到達できる
706: 仕様書無しさん [sage] 2024/03/30(土)23:12
のこさんはちゃんとARC出てるからね偉いよ
707(1): 仕様書無しさん [sage] 2024/03/30(土)23:14
dp[作った正方形][何行目まで使ったか][何列目まで使ったか]ときの最大の和を持つ
dp[任意][i][j]=max(dp[任意][i][j],dp[任意][i-1][j],dp[任意][i][j-1])
iとjがm以上ならdp[任意+1][i][j]=max(dp[任意][i][j],dp[任意][i][j-m]+[j-mからj列目の中で取れる最大の正方形])
dp[任意+1][i][j]=max(dp[任意+1][i][j],dp[任意][i-m][j]+[i-mからi行目の中で取れる最大の正方形])
これダメかな？
708: 仕様書無しさん [sage] 2024/03/30(土)23:14
競技者を失格してしまった人
709: 仕様書無しさん [sage] 2024/03/30(土)23:14
>>699
これわからん
m行m列以上の3区域に分割する方法を全探索するということか？
切り方は目と円の字に切る2パターンだけ試せればよく、あとは90度回転4回やればいいってこと？
710(1): 仕様書無しさん [sage] 2024/03/30(土)23:16
ちょっと待ってくれ、明日余裕あったら実装してみてACしたらPaiza.ioのエディターで共有するわ
711: 仕様書無しさん [sage] 2024/03/30(土)23:17
>>707
そのdpをやるくらいなら絶対に上から埋めればよくね
H行目までを確定させたときにM個採用のほうがdpがシンプル
一点更新矩形和が取れると仮定すればお前のやり方でも可能だとは思うが計算量が怪しい
712: 仕様書無しさん [sage] 2024/03/30(土)23:17
>>705
NDTKKSでも誰でもは無理だろう
713(1): 仕様書無しさん [sage] 2024/03/30(土)23:18
>>710
わかった提出監視しとくわ
714: 仕様書無しさん [sage] 2024/03/30(土)23:18
Fで品目のパターンマッチング出来る人々流石に典型化が行き届きすぎててすごい
715: 仕様書無しさん [sage] 2024/03/30(土)23:18
TKNDKS合格が事実上の1次試験だから
716(2): 仕様書無しさん [sage] 2024/03/30(土)23:19
mの正方形の区間和を行ごとと列ごとに前計算しておいてsparse tableで行けそうじゃない？
717: 仕様書無しさん [sage] 2024/03/30(土)23:20
こどふぉやるぞやるぞ
3h
718: 仕様書無しさん [sage] 2024/03/30(土)23:20
>>713
ネトストやめてください！
719: 仕様書無しさん [sage] 2024/03/30(土)23:20
そこまでわかってるならDPせずとも解けそう感がすごい
720: 仕様書無しさん [sage] 2024/03/30(土)23:21
>>716
あーまあそうか
でもでもfor h: for w:の順でループするから結局行ごとに確定させるわけで、これ高速化したら711の上から埋めるdpでよくね
721: 仕様書無しさん [sage] 2024/03/30(土)23:22
>>716
いや、ごめん無理だわ
無理ぽいです
722(1): 仕様書無しさん [sage] 2024/03/30(土)23:22
今からこどふぉやる気力あるやつバケモン過ぎるな
そういう人たちにとってはABCが余興みたいなもんだからか
723: 仕様書無しさん [sage] 2024/03/30(土)23:23
こどふぉ行くぞ！
724: 仕様書無しさん [sage] 2024/03/30(土)23:23
自明問早解きしか出来ない
725: 仕様書無しさん [sage] 2024/03/30(土)23:23
自分よりレート低い人がwriterやってるの違和感
726: 仕様書無しさん [sage] 2024/03/30(土)23:23
>>705
へんさち65未満の高校だとポテンシャル黄色はほとんどいないんじゃないか
727: 仕様書無しさん [sage] 2024/03/30(土)23:23
こどふぉ
728: 仕様書無しさん [sage] 2024/03/30(土)23:24
>>722
div1ratedだからね ABCunrated者が多い
729: 仕様書無しさん [sage] 2024/03/30(土)23:24
3hは普通に長いからやりたくないが明日AGCあるしまあ
730: 仕様書無しさん [sage] 2024/03/30(土)23:26
声の高い謎のおっさんが提供している指標よりこどふぉのレートのほうが大事
731: 仕様書無しさん [sage] 2024/03/30(土)23:26
ジャップランドよりも国際的だしね
英語が読めない国際社会の未定義動作にだけはなるな
732: 仕様書無しさん [sage] 2024/03/30(土)23:27
声の高い謎のおっさんが提供している謎の指標、一体なんなんだ
733: 仕様書無しさん [sage] 2024/03/30(土)23:27
競プロの性質上、(受験勉強などで)長時間考えることに慣れてる人が多いってのもあるのかな
734: 仕様書無しさん [sage] 2024/03/30(土)23:27
dpはこれができずに発狂不可避
735: 仕様書無しさん [sage] 2024/03/30(土)23:28
声の高い謎のおっさんですらTKなのに
736: 仕様書無しさん [sage] 2024/03/30(土)23:29
KS落ちTK
737: 仕様書無しさん [sage] 2024/03/30(土)23:30
こどふぉやるか〜
途中でダルくなって撤退しそうだが
738(1): 仕様書無しさん [sage] 2024/03/30(土)23:31
声の高い謎のおっさんですら美人妻がいるのに俺ときたら...
739: 仕様書無しさん [sage] 2024/03/30(土)23:31
あとこれも発狂できる
dpだとだるすぎてクリアできません
740: 仕様書無しさん [sage] 2024/03/30(土)23:32
>>738
年収は？
741: 仕様書無しさん [sage] 2024/03/30(土)23:33
結局競プロ外も中受支配的か
742: 仕様書無しさん [sage] 2024/03/30(土)23:33
声の高い謎のおっさん応援スレ
743: 仕様書無しさん [sage] 2024/03/30(土)23:37
レート800台から抜け出せないねぇ
744: 仕様書無しさん [sage] 2024/03/30(土)23:48
某8くん、失敗したらすぐ病んで垢名変えるとこはマスくんにそっくり
745: 仕様書無しさん [sage] 2024/03/30(土)23:51
病み方草
名前芸やめちくり
746: 仕様書無しさん [sage] 2024/03/30(土)23:56
中学生でもわかる深層学習読もうとして、その執筆者の垢名が競技者失格なのを目にする人を考えたら笑うな
747: 仕様書無しさん [sage] 2024/03/31(日)00:11
人間失格、つまり非人間であることを自覚するインコ
748: 仕様書無しさん [sage] 2024/03/31(日)00:15
マスくんクルド人差別はよくない
749: 仕様書無しさん [sage] 2024/03/31(日)00:16
クルドインコと呼べ
750: 仕様書無しさん [sage] 2024/03/31(日)00:19
急に人間味あるツイートするのやめろ面白いから
751: 仕様書無しさん [sage] 2024/03/31(日)00:23
マスくんは3ヶ月あたりで緑パフォ出せるようになってるあたり明らかに天才寄りなので、もっと自信もってがんばってくれ
緑にも到達できなくて泣いてる人なんていくらでもいるぞ自信を持て
752: 仕様書無しさん [sage] 2024/03/31(日)00:25
下には下がいることを知る毎日
753: 仕様書無しさん [sage] 2024/03/31(日)00:26
日本から出ていくべきは外来種インコである君ですよね
754: 仕様書無しさん [sage] 2024/03/31(日)00:28
国籍を知ってる辺りある程度交流があると伺える
755: 仕様書無しさん [sage] 2024/03/31(日)00:34
マスくんって外国産の鳥なの？
756: 仕様書無しさん [sage] 2024/03/31(日)00:34
マスくん、#9110に電話して相談するといいよ
757: 仕様書無しさん [sage] 2024/03/31(日)00:54
珍しくスレ長が正論言ってるぞ
758: ager [sage] 2024/03/31(日)01:05
万年青水反復コーダーの思考ともいえる
759: 仕様書無しさん [sage] 2024/03/31(日)02:32
クルドといえば埼玉のあの都市だけどもしかして
760: 仕様書無しさん [sage] 2024/03/31(日)02:40
Dナップサックに帰着出来ちゃうから上位K個を持つDPで解けなかったらやばいだろと思って解けたのは良かったけどEわからん
偶奇に注目して重複組合せでいけそうなんだが
761: 仕様書無しさん [sage] 2024/03/31(日)02:44
E解けないです
才能の壁感ある
上振れたときにMいったけど紫上位が適正感ある
762: 仕様書無しさん [sage] 2024/03/31(日)02:49
もまいらもう寝ちゃった？
さみしー泣
763: 仕様書無しさん [sage] 2024/03/31(日)02:54
真似っこ戦略で偶奇保てるってところまでわかったのに何故か会わなかったんだけどなあなあ
764: 仕様書無しさん [sage] 2024/03/31(日)03:05
真似っ子で勝てるのは俺もわかったので部分点くーださい
765: 仕様書無しさん [sage] 2024/03/31(日)03:11
コンテスト感想の真似っこやめてね
766: 仕様書無しさん [sage] 2024/03/31(日)03:12
あんなにスレでオウム返しオウム返し言ってたのに一瞬で真似っこ戦略が思いつけないのは過去スレ精進がたりてないぞ
767: 仕様書無しさん [sage] 2024/03/31(日)03:17
真似っ子が思いついても左右動があるから真に正しいか示すの大変なんだが？
mod998を超えられなかったやつくらい山程いるだろなにが感想の真似っ子じゃ
768: 仕様書無しさん [sage] 2024/03/31(日)05:07
こどふぉ終わってから失神してた
769: 仕様書無しさん [sage] 2024/03/31(日)05:24
E、反転させたら一緒になるから一方向だけ考えれば良い
770: 仕様書無しさん [sage] 2024/03/31(日)06:15
チャンコロライター陣がちゃんころ問題パクてるんだから既出なのは当たり前だろｗ
771: 仕様書無しさん [sage] 2024/03/31(日)06:41
ガイジスレ終了
772(1): 仕様書無しさん [sage] 2024/03/31(日)06:52
今日のAGCで0完して俺も競技者失格してしまったらどうしよう
773: 仕様書無しさん [sage] 2024/03/31(日)08:00
マジでAGCで橙パフォ以上頼む
774: 仕様書無しさん [sage] 2024/03/31(日)08:06
0完でレートが増えるバカのコンテスト最高
黄色は出るだけ期待値損
775: 仕様書無しさん [sage] 2024/03/31(日)08:15
0完太陽なのにレートが上がる欠陥制度あざす笑
マイナスサムゲームのratedパチンコふるって参加してくれよな
776: 仕様書無しさん [sage] 2024/03/31(日)08:23
0完でも温まるのほぼ確定な水インコがイキイキしてるな
777: 仕様書無しさん [sage] 2024/03/31(日)09:10
イキリインコ
778: 仕様書無しさん [sage] 2024/03/31(日)09:11
黄色のあの人は今日橙色に戻れるの？
779: 仕様書無しさん [] 2024/03/31(日)09:19
【結婚難】時間外労働で共働き妨害【孤独死】
☆犠牲になるのはSEの結婚相手☆
SEは非婚や離婚や中絶や少子化や親不孝を促進
・キモい
・モラルない
・ファッションセンスない
・コミュニケーション苦手
・時間外労働違反で共働き妨害
・人売屋に開発報酬を奪わせる
・人売屋に知的財産を奪わせる
・裁判官が技術判断不正をする
SEは開発料金の詐欺被害で結婚できない
https://codelearn.jp/articles/about-engineer-marriage
780: 仕様書無しさん [sage] 2024/03/31(日)09:38
AGCの暖色diff自力AC出来ると濃いの出る
781: 仕様書無しさん [sage] 2024/03/31(日)09:44
https://zukan.pokemon.co.jp/detail/0931-1
イキリ水インコの参考画像貼っておきます
782: 仕様書無しさん [sage] 2024/03/31(日)09:49
安直すぎるからペラップにしろ
783: 仕様書無しさん [sage] 2024/03/31(日)09:49
黄色の イキリンコは とくに 荒っぽい。 ほかの 鳥ポケモンを 街から 追い出したこともある。
↑完全に黄色タッチインコ大王の説明文
大きい グループは 50匹を 超える。 エサを 求め 街中や 森を 騒がしく 飛びまわる。
↑完全に馴れ合い寒色インコの説明文
街中で 暮らすことを 好む。 羽の 色で グループを 作り 縄張り争いを 繰り広げる。
↑完全にratismの説明文
784: 仕様書無しさん [sage] 2024/03/31(日)09:49
全てが繋がってるんだよね
785: 仕様書無しさん [sage] 2024/03/31(日)09:55
繋がってないです
なんでも繋げるな
786: 仕様書無しさん [sage] 2024/03/31(日)09:56
典型に帰着させる能力は競プロでは大事だからな
787: 仕様書無しさん [sage] 2024/03/31(日)10:07
>>772
そもそもまだ競技者の土俵に立ってすらいないだろ
788: 仕様書無しさん [sage] 2024/03/31(日)10:14
プロ失格と言わなかっただけ彼は良識あるよ
789: 仕様書無しさん [sage] 2024/03/31(日)10:18
競プロじゃなくてただの競になってしまったわけだな
790(1): 仕様書無しさん [sage] 2024/03/31(日)10:26
FをM×Mタイルを○枚置く最大利得に読み替えたら解ける？
計算量は無視してよく解けるかどうか
791: 仕様書無しさん [sage] 2024/03/31(日)10:36
>>790
それが効率的に解けるのであれば今回のFもそれに帰着させることでわざわざ場合わけ(分割)せずとも解けるわけだから、愚問ではないか
792: 仕様書無しさん [sage] 2024/03/31(日)10:38
難しいことが既知とされている一般的な問題に帰着させるのは計算量理論での証明典型
793: 仕様書無しさん [sage] 2024/03/31(日)10:38
正直4でもだいぶ苦しそう
794: 仕様書無しさん [sage] 2024/03/31(日)10:40
ワンチャンフローとかで出来たりするかもだが
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.226s*