競技プログラミングにハマるプログラマのスレ 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(土) 20:11:16.87

送ったから結果フォームあくしろ

**仕様書無しさん** · 2024/03/30(土) 20:12:56.13

太陽でも1600入るから1200-1600は参加するだけ得

**仕様書無しさん** · 2024/03/30(土) 20:13:22.72

やっぱり水色ってアルゴリズムを勉強しなくてもなれるんだね　社長は正しかった

**仕様書無しさん** · 2024/03/30(土) 20:13:45.52

>>623
( ;∀;)
結果ここで見れる

https://customform.jp/form/result/174861

**仕様書無しさん** · 2024/03/30(土) 20:16:04.25

不参加に入れてる奴と参加権すらない未定義動作はFAKE野郎確定なのでとっとと追放しろ

**仕様書無しさん** · 2024/03/30(土) 20:16:59.84

見るたびに値爆増してるしどうせ一人が荒らしてる

**仕様書無しさん** · 2024/03/30(土) 20:17:37.99

数分で40件近く投票あるの草
10人くらいで回してるイメージあったけど結構人おったんやねここ

**仕様書無しさん** · 2024/03/30(土) 20:18:47.61

水未満のクズ多すぎて草

**仕様書無しさん** · 2024/03/30(土) 20:18:53.28

このまま荒らしが連投してAGCの参加人数超えたら笑う

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

こういうしょうもない荒らししてるのどうせageカスなんだよな
水未満に投票しまくる→水タッチの自らの地位を高めようとするみたいなクズ思考が見え見え
大人しく自分の低いレートを上げる努力をしろ

**仕様書無しさん** · 2024/03/30(土) 20:21:17.73

何回でも投票できるやないか～い

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

赤マスさんの告知ツイちょっと面白い

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

絶対A地雷だからBからやろう

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

荒らし行為もアホだが5chで投票し放題なアンケが機能するつもりなのもアホだ

**仕様書無しさん** · 2024/03/30(土) 20:25:33.78

せっかくアンケ作ったのに荒らされて悲C

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

スレ民がAGCを作るかアンケ

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

A200点ぐらいなら生やせるぞ

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

ギャグ担当やめてね

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

人生がギャグの人

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

多重投稿で4-5-4-5-19にしたのに5-5-4-5-19にずらされたのゆるせねえ

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

APC(atcoder parrot contest)開くしかない　インコ作問

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

これでいいはず
もう一回投票頼む

入力フォーム
https://customform.jp/form/input/174863

集計結果
https://customform.jp/form/result/174863

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

連投対策されてて鬱

**仕様書無しさん** · 2024/03/30(土) 20:40:48.42

AGCには参加しないのだ！

**仕様書無しさん** · 2024/03/30(土) 20:55:50.07

ABCいきますよーいきますよーいくいく

**仕様書無しさん** · 2024/03/30(土) 20:57:52.74

明日のAGC出られるようになるくらい勝ちたい

**仕様書無しさん** · 2024/03/30(土) 20:58:46.66

SAISを貼る！(素振り)SAISを貼る！(素振り)

**仕様書無しさん** · 2024/03/30(土) 21:08:53.19

なのだ！の人の実際のレートはいくつ？

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

うんこDP

**仕様書無しさん** · 2024/03/30(土) 22:41:10.15

不可能G　このゲームはクリアできません

**仕様書無しさん** · 2024/03/30(土) 22:41:54.35

C70分くらい1WAが解消できなかったクソ過ぎる

**仕様書無しさん** · 2024/03/30(土) 22:41:59.17

5完太陽
2Dセグ木いじくったけど無理だった

**仕様書無しさん** · 2024/03/30(土) 22:42:30.70

5完だしWAまみれだしもう終わりだよこの競プロ人生

**仕様書無しさん** · 2024/03/30(土) 22:45:19.01

マジで2次元累積和とかやらすの辞めてくれねぇか？
実装苦手過ぎてABCよりARCやAGCのほうが圧倒的にパフォが高くてキレそう

**仕様書無しさん** · 2024/03/30(土) 22:45:20.99

A～E自明(Dでコーナーケースペナ踏んでカス)なのにF解けなくておしまい(インコ大王仕草)
真ん中ないし2つ固定してから差分更新か二次元セグ木でやれば出来そう感があったけど実装と頭が壊れてしまい終了

**仕様書無しさん** · 2024/03/30(土) 22:45:40.03

C問題
dの各要素に対してa+bで割った余りを取って、それをソートした一番大きいものと一番小さいものの差がa未満ならYes

これで1WAずっとついてたんだけどなんでだ...

**仕様書無しさん** · 2024/03/30(土) 22:45:57.35

マスくん今日のC解けてるの偉いじゃん
正直解けなそうだと思ってた

**仕様書無しさん** · 2024/03/30(土) 22:47:12.89

C俺はd_0からの差分をA+Bで割ってあとは同じやり方で一発で解けたな
知らんけどN=1のケースとかじゃね？

**仕様書無しさん** · 2024/03/30(土) 22:47:35.21

Dのしょうもなペナルティカスすぎる

**仕様書無しさん** · 2024/03/30(土) 22:47:56.47

Fみたいなのどうやって早く解くんだ？
FA5分とか早すぎだろ

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

>>659
0 12345 6
日平日土

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

>>660
ペナ出しまくったものの辛うじて解けた

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

1時間以上椅子温めたしこどふぉdiv1+2出るか　不完全燃焼

**仕様書無しさん** · 2024/03/30(土) 22:49:52.41

CもDも普段よりは難しいと思う(適正レート帯の人にとってはという意味で俺は勿論すぐ解けたけど)

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

3つの領域に分ける3つの長方形典型、4角からDPでも解けるのちょっと面白いな

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

×__builtin_popcount()
○__builtin_popcountll()

**仕様書無しさん** · 2024/03/30(土) 22:52:14.59

逆に言うとコーナーケースがこれしか思いつかないので予定日を乱択でずらせば通せそうだが

**仕様書無しさん** · 2024/03/30(土) 22:52:17.04

今回のCはARC-Aでも良さそう

**仕様書無しさん** · 2024/03/30(土) 22:52:27.12

>>664
ごめんわからんｗ
その場合0を土1を日とみればいいんじゃないの？

**仕様書無しさん** · 2024/03/30(土) 22:53:01.88

燃やす埋めるコンテスト中に解けたことなし

**仕様書無しさん** · 2024/03/30(土) 22:54:00.81

この手のコンテストは必ずペナ踏みまくるから本質的に向いてない人生

**仕様書無しさん** · 2024/03/30(土) 22:54:07.48

ちゃんとテストケース作れや

**仕様書無しさん** · 2024/03/30(土) 22:54:58.17

F盤面回転するところまでは思いついたんだけどなあ

**仕様書無しさん** · 2024/03/30(土) 22:55:38.94

>>672
2 2 5
6 7 ないし 1 7
で落ちないか試せ

**仕様書無しさん** · 2024/03/30(土) 22:55:43.52

盤面回転すれば実装楽できるやん
思いつければ良かったが

**仕様書無しさん** · 2024/03/30(土) 22:55:49.72

D問題最後のテストケースの出力結果がxとyでサンプルの出力と逆だったけど通った
これは何か面白い性質があるのかな？

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

普通に解が1/10^9になるような問題を作れるので、C乱択は通りません

**仕様書無しさん** · 2024/03/30(土) 22:57:24.89

>>667
6 7 の場合に落ちたわ
そういうことか理解できたありがとう

**仕様書無しさん** · 2024/03/30(土) 22:57:33.73

>>668
なるほど、正方形を取った数+どこまで見たかか
確かに出来るな

**仕様書無しさん** · 2024/03/30(土) 22:57:51.57

xorの可換性を面白いと捉えるならそうだな

**仕様書無しさん** · 2024/03/30(土) 22:57:51.69

>>680
平日1日休日10^9日で乱択落とせるたしかにだな

**仕様書無しさん** · 2024/03/30(土) 22:58:22.97

>>668
逆の対角線上にある場合ってどうやんの？
遷移できなくね？

**仕様書無しさん** · 2024/03/30(土) 22:58:26.30

俺マスくんの隣人である可能性出てきた

**仕様書無しさん** · 2024/03/30(土) 22:58:57.02

>>681
間違えた>>677

**仕様書無しさん** · 2024/03/30(土) 22:58:58.40

>>685
四隅から始めるため

**仕様書無しさん** · 2024/03/30(土) 22:59:35.57

おれもマスくんと近いかも

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

クルド人中学受験をしているのだろうか？
不安だ

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

彼って毎回才能について語る縛りでもしてるの？

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

はい

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

>>688
どう回転しても↘︎方向だけじゃなくて↗︎or↙︎方向に存在する正方形同士が最大になるケースもあると思うから無理じゃね

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

>>686
クルド人の方ですか？

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

あーF2つの最大値を回転+dpするところまでは出来てたから二次元セグ木持ってたら解けたわゴミすぎ

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

何行目まで使ったかと何列目まで使ったかを持って、新たにm行以上使用して区間maxじゃダメ？
ちょっと分からんので図示してくれ

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

>>683
なるほど

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

>>696
サンプル1から無理じゃね？

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

新たにm行or列使えば必ずその領域上にmの正方形が作れる性質で行けそうじゃない？

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

>>698
右上からやれば出来そうじゃない？

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

Eとかいうのかなりやるだけで完全に空気

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

のこのバランス感覚すげーな
C350を主張したのかなり偉い

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

>>700
どう遷移させてるの

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

クルド人街は殺傷事件があっても警察はアンタッチャブル

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

黄になる程度だったら競プロに才能なんて関係ないだろ
高校卒業できる程度の低能があるなら努力すれば誰でも到達できる

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

のこさんはちゃんとARC出てるからね偉いよ

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

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行目の中で取れる最大の正方形])

これダメかな？

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

競技者を失格してしまった人

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

>>699
これわからん
m行m列以上の3区域に分割する方法を全探索するということか？
切り方は目と円の字に切る2パターンだけ試せればよく、あとは90度回転4回やればいいってこと？

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

ちょっと待ってくれ、明日余裕あったら実装してみてACしたらPaiza.ioのエディターで共有するわ

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

>>707
そのdpをやるくらいなら絶対に上から埋めればよくね
H行目までを確定させたときにM個採用のほうがdpがシンプル
一点更新矩形和が取れると仮定すればお前のやり方でも可能だとは思うが計算量が怪しい

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

>>705
NDTKKSでも誰でもは無理だろう

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

>>710
わかった提出監視しとくわ

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

Fで品目のパターンマッチング出来る人々流石に典型化が行き届きすぎててすごい

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

TKNDKS合格が事実上の1次試験だから

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

mの正方形の区間和を行ごとと列ごとに前計算しておいてsparse tableで行けそうじゃない？

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

こどふぉやるぞやるぞ
3h

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

>>713
ネトストやめてください！

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

そこまでわかってるならDPせずとも解けそう感がすごい

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

>>716
あーまあそうか
でもでもfor h: for w:の順でループするから結局行ごとに確定させるわけで、これ高速化したら711の上から埋めるdpでよくね

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

>>716
いや、ごめん無理だわ
無理ぽいです

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

今からこどふぉやる気力あるやつバケモン過ぎるな
そういう人たちにとってはABCが余興みたいなもんだからか

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

こどふぉ行くぞ！