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