競技プログラミング総合スレ 64

2022/10/02(日) 17:43:58.66

↑2行になるようにする

競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder https://atcoder.jp/
yukicoder https://yukicoder.me/
Codeforces https://codeforces.com/
CodeChef https://codechef.com/
Project Euler https://projecteuler.net/
CLIST https://clist.by/
AtCoder Problems https://kenkoooo.com/atcoder/
AtCoder Clans https://kato-hiro.github.io/AtCoderClans/

※前スレ
競技プログラミング総合スレ 63
https://mevius.5ch.net/test/read.cgi/tech/1627477128
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

2022/10/24(月) 15:13:18.61

chokudaiに限らず、銅冠以上が解けてない問題を典型って言っちゃうのは、典型とは一体っていう感じだけど

2022/10/24(月) 15:13:43.19

AVL木とか赤黒木辺りの仕組みをちゃんと理解してないと解けない問題ってある？
こういうのってやっぱり競プロ文脈だと自力で実装する必要ないのかな

2022/10/24(月) 15:56:17.71

avl木を題材にした問題は見たことあるけど仕組みの理解が必要かは疑問
せいぜい問題設定の理解が楽になる程度じゃないかなあ

その場でちゃちゃっと機能付け足せるくらい手に馴染んだ平衡二分木持ってると得するっつーか楽できる場面は結構ある

2022/10/24(月) 16:57:52.37

確か赤黒木は、木の再構成を頻繁に行わないように、
木の高さが2倍になった時に初めて、再構成するのでしょ？

確か、Linux のタスク管理などに使われているのか？

この2倍と言うのが、解く問題に影響するかどうか

2022/10/24(月) 17:17:37.19

「ちゃんと理解してないと」って言われても理解の深さにも差があるからなあ・・・
https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum
こういう問題をサラっと解けるならおれはそこそこ理解してると思っちゃうけど、ライブラリ叩くだけだからこんなんじゃ理解したなんて言えない、と判断する人もいると思う

フェニック木やセグ木以外で、平衡二分木の実装まで要求してしまうとそこそこ重いし、深い理解を要求する問題にはあんまり遭遇しなそう
逆にいうと、セグ木でだいたいなんとかなってしまうともいえる

2022/10/24(月) 18:27:07.50

平衡二分探索木のmerge-split系の操作が難しめの問題で役に立つみたいなのたまに見るけど、その辺り詳しくない
まあ、自作平衡二分探索木があると、std::setにない機能を追加できたり何かと捗るので自分で実装するのも悪くないと思うよ
順位取得とかね
座圧セグ木でもできることが多いけど

2022/10/24(月) 18:59:23.04

オフライン性活かした実装ってダルいからそれスキップできるだけでも強い
永続系も似た用途で使えることあるね

2022/10/26(水) 14:14:56.58

???「赤にいかないうちは、典型も解けていないという証拠なのでどんな問題がでても文句を言わずに解きましょう」

2022/10/26(水) 20:39:16.10

bit系のオリジナルライブラリ作ったけどstdの方が16倍くらい早くて泣いた

2022/10/26(水) 23:49:51.56

charでも使ってんのか

2022/10/27(木) 16:34:41.72

ハードウェアとかコンパイラとか全然知らないのですが、

vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));

とか初期値を指定して初期化する場合、初期化の処理にΘ(N^2)回の計算量が必要になりますか？

2022/10/27(木) 16:35:26.87

なる

2022/10/27(木) 16:57:58.07

>>230
ありがとうございました。

2022/10/27(木) 17:00:44.14

でも不思議です。
今まで
>>229
のようなコードを例えば、O(n * log(n))の計算量が求められる問題で使用してきましたが、
ちゃんとパスしてきたと思います。
>>229
のようなコードがあるとそれだけでO(n^2)以上の計算量が必要ですよね？
n^2の係数が極端に小さいんですか？

いずれにしても理論的にはO(n^2)以上ということになりますよね？

2022/10/27(木) 17:36:43.76

そう、O(n^2)だよ

当然だけど通るかどうかはNの値による
下のコードをN = 100000で、AtCoderのコードテストやってみたら2453msとかになったから、このサイズだとだいたいダメだろう

int main() {
int N = 100000;
vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));
cout << dp[0][0] << endl;
}

2022/10/27(木) 17:39:01.04

すまん、2453msじゃない
終了コード9で終わってたからただのタイムアウトだった
まあダメってことだ

2022/10/27(木) 17:39:59.24

>>233-234
ありがとうございました。
今度から意識して初期化するようにしてみます。

2022/10/27(木) 17:44:47.51

vector上の数字を全部0にセットする処理はかなり定数倍軽そうだし、思ったよりも通りそうではある
もちろん無意味なオーバーヘッドを生んでるだけなのでやめた方がいいけど

2022/10/27(木) 18:18:50.06

メモリをN^2使ったら駄目だろ

2022/10/28(金) 02:02:28.05

>>234
タイムアウトではなくメモリの方だね
コードテストだと10秒待ってくれる

>>236
何と比較するかではあるけどメモリ確保は一般には定数倍重い部類の操作だと思う

2022/10/28(金) 02:05:18.44

ああ、たしかにめっちゃメモリ食うやん

2022/10/28(金) 04:18:20.91

でもN^2のメモリが必要な問題もありますよね。
迷路の問題とか。

2022/10/28(金) 04:58:13.49

具体的な問題あげてみなよ

2022/10/28(金) 10:38:59.44

当たり前だけどNの大きさによるので
Nが3000以下とかならN^2のメモリ確保でもどうにかなるし、100000なら無理というだけ

2022/10/28(金) 11:25:04.27

O(N^2)って"高々"N^2の定数倍で抑えられる、だから計算量がNでもlogNでもO(N^2)だし、今回の文脈で使われると典型的な誤用で気持ち悪く見えるな

2022/10/28(金) 11:51:58.80

じゃあΩ(N^2)使ってくか

2022/10/28(金) 13:48:32.69

こことかTwitterとかでやりとりする分には大抵オーダー記法とっぱらっちゃっても伝わるな
誤用よりマシな気がする

2022/10/28(金) 13:51:51.24

>>229,240 を見る限り制約に全く触れられてないので、計算量についてなにか勘違いしていそう

2022/10/28(金) 16:54:39.37

N^2がTLEするようなNの大きさならN^2のサイズの領域確保したらだいたいMLE

2022/10/28(金) 21:34:06.53

基本的にTLEにならないコード書けば自然とMLEも回避できると思ってる

2022/10/29(土) 12:58:54.16

C++のpriority_queueについて質問です。

優先度付きキューに入っているある要素の優先度を変更する方法ってありますか？

2022/10/29(土) 13:23:15.94

高速な方法は、ない

2022/10/29(土) 13:32:10.33

>>250
自分で作るしかないということですか。
ありがとうございました。

2022/10/29(土) 13:48:55.13

古い優先度の要素は残したまま新しい優先度の要素を突っ込んで、
取り出したときに優先度が古ければ無視

で大体なんとかなる印象

2022/10/29(土) 14:29:52.84

ダイクストラのやつね

2022/10/29(土) 14:39:48.64

Fibonacci heapは優先度を変えられるからダイクストラの計算量が落ちるってことだったのか

2022/10/29(土) 16:17:47.20

N^2の計算ができるって、江戸時代からしたらものすごいことなんだけど人類はまだそれでも飽き足らないからすごいことだよね

2022/10/29(土) 17:02:47.53

そこからさらに、並列処理可能にして一気に処理したり
根底から覆す量子コンピュータとか

2022/10/29(土) 17:36:48.50

>>252-254
ありがとうございました。

>>252
なるほど、それでも全く問題ないですね。
気持ち的には、ちょっと気持ちが悪いですが。

2022/10/29(土) 20:07:47.15

自作するとして、元の要素がどれか特定する部分が遅いんだよな
よくある実装だとunordered_map使うから定数倍が重い
acl::maxflowのadd_edgeのように、要素を追加したら後で優先度を変更する際の引換券を返すのが良いのか？

2022/10/29(土) 22:41:09.93

E問題。。。。
t-1回目にどのマスにいるかの確率（というか回数）を出して
t回目にどのマスにいるかを算出すればできるってことはわかってるのに時間が足りない。。

しかしこの考え方ってあってるのかな
dp的にやると100万×動けるマス10マスで1000万だからこのままやっても計算量的にアウトだったんだろうか

2022/10/29(土) 22:41:56.11

実装重いのをCに置くのはほんとやめて

2022/10/29(土) 22:44:01.17

公式解説もNMKだったから一応あってるのか

今回の結果
https://imgur.com/a/C2RD1bF
この間茶色になったばっかりだが、少しでも緑に近づけてることを願う

2022/10/29(土) 22:45:05.88

>>259
あってるぞ、O(NMK)になるからな

2022/10/29(土) 22:46:38.52

https://imgur.com/c9Dco1P
ええ。。
Cを一回間違えてしまったとはいえ4完全したのにマイナス6かよ、、、緑むりげーだろ

2022/10/29(土) 22:47:59.86

>>262
公式見るとあっていたみたいだね。
ただ、低速な言語だと間に合わないで前計算が必要って書いてあったけド、このあたりまだ理解できていないので分数のmodについてちゃんと理解しておくようにする

2022/10/29(土) 22:48:01.40

Eは解説とほぼ同じように作ったのに1時間最後まで合わなかった…むなしい…

2022/10/29(土) 22:50:45.78

でもE問題が射程範囲に入ったのはちょっと嬉しかった。
C問題がかなり苦戦して、どっち方向に直交ベクトルをかけるかっていう部分に関してかなり苦労してしまった。
結局2パターンについてべた書きしてしまった

D問題はメモ化再帰して一瞬だった。
C飛ばしてEに挑戦してればレーティング上がったのかな

2022/10/29(土) 22:52:01.22

>>263
それ前回のパフォじゃん
さすがに今回はレートあがるだろ

2022/10/29(土) 22:52:46.63

>>263
これに表示されてるは前回の結果だよ　コンテスト名を見ればわかる
今回も含めてコンテストの結果は数時間後に出る事が多いから終わってすぐには反映されないよ

2022/10/29(土) 22:54:16.01

>>267-268
ほんまやあああああああああ
サンクス
しかしC問題で一回間違えた(直交方向に足した値が範囲内でおさまってるかの処理を書き忘れた）ので少しそれが心配。。

2022/10/29(土) 22:54:24.14

あとそのレートで4完してるなら今回でレートは100くらい上がるんじゃない？

2022/10/29(土) 22:55:21.84

ac-predictor入れなよ

2022/10/29(土) 22:57:09.33

レートの更新が来てるわね

2022/10/29(土) 22:57:27.79

https://imgur.com/a/5ACK8kd
ほんまやああああああ
緑色がみえてきたあああああああ

E問題まで確実にとけるように頑張りたい

2022/10/29(土) 22:58:19.47

Fって精進すればDP使おうってすぐ見抜けるようになるものなん？

2022/10/29(土) 22:59:37.34

うん

2022/10/29(土) 23:04:29.61

dpのiとjのループの順番を逆にしたら通った…

2022/10/29(土) 23:07:12.53

Fはいつもより典型度高めかな
ナップサックDPをするついでに、選ぶときの遷移と選ばないときの遷移でちょっと処理を変えるみたいなのは結構見る

2022/10/29(土) 23:08:20.93

from functools import lru_cache
pythonってメモ化再帰再帰が標準実装されてるんだ
知らなかった・・
どうやって制御してるんだって感じだが、やっぱり標準モジュール？ってすごいな

2022/10/29(土) 23:13:13.23

実際どうやってんのか知らないけど、メモ化再帰の実装はpythonのデコレータと相性いいと思う

2022/10/29(土) 23:18:18.42

計算時間の見積もりだけど、ラフに計算して10^8以下で平均的な定数倍の重さだったら2 secで間に合うし、普通に想定解になりうると思うよ

2022/10/29(土) 23:19:43.68

簡単にいうと、デコレータで内部的にdictを作って、引数と戻り値つっこんでるだけでしょ
dictより自分でlistを使ってメモ化したほうが高速だし、別にlru_cacheは覚えなくてもいい気がするな

2022/10/29(土) 23:25:38.82

標準実装部分って一度Cでコンパイルされてるから自前実装より速いと思っていたんだけどどうなんだろう。
あとdictってハッシュだから速いと思ってたんだけどlistの方が早いっていうことってあるの？
インデックスへのアクセスがn(1)だとしても再帰関数の場合はインデックスもばらばらだと思ったんだけど

2022/10/29(土) 23:30:42.87

mod逆元なんて意味不明な計算させんでも、誤差を認めた小数でええやん

2022/10/29(土) 23:30:58.93

Pythonの標準実装は、Cで高速化されて優秀なときと生Pythonで微妙な実装が施されていてひどいときの両方がある印象だね
PyPyに至っては最適化の仕方がよくわからないから実際に試すしかない

2022/10/29(土) 23:36:12.18

>>282
ハッシュ化のオーバーヘッドがあるから、とりうる引数の値が小さいんならlistの方が定数倍速いこともありうる
今回はそもそもlistでは対応できないはず

2022/10/29(土) 23:36:54.42

Pythonを使ってた時は自前で書いた二分探索だと通らなくてそこを二分探索のライブラリに置き換えたら余裕を持って通ったことがあったからCによる高速化の恩恵は大きそう

2022/10/29(土) 23:42:41.35

>>283
ターンが進むごとに指数的に減衰していきそうな行動パターンまでちゃんと追跡できてるかを問いたいとすると、mod逆元の方がいいと思う
まあ、小数解答方式でそういうタイプの枝刈りで通せる人はそもそも今回の問題だと問題なく想定解にたどり着ける気がするけど

2022/10/29(土) 23:45:49.46

Ex、ぱっと見Cartesian木で貪欲でいけるんじゃないかと思ってしまうが、そんな単純な問題じゃないっぽい

2022/10/29(土) 23:48:54.20

んー、F難しくはなかった
毎回変なところで失敗するからたどり着けないけど

2022/10/30(日) 00:52:02.32

Eまでは安定するようになってきたけどFが中々安定しない
今回のFは素直なDPで良いって聞いたらすぐだったのに

2022/10/30(日) 01:22:58.95

Cで正方形の定義書いてほしいと思うのは甘え？

2022/10/30(日) 01:28:08.60

GもExも見方によってはLPだし後ろの方はLP回だったのかも

2022/10/30(日) 01:28:10.10

長さが同じっていうだけで判定すると菱形も拾ってしまうよね

直行条件って内積知らないと厳しいと思うけど、やっぱり数学の知識が必要なんだと思った

2022/10/30(日) 01:31:32.00

>>290
部分和をちょうどxにするときに何かを最適化する問題って地味に取れる手立てが少なくて（今回のGみたいに例外的に連続緩和できるとかならともかく）、ABCだったらナップサックDPを出発点に考えても大体外れないと思う

2022/10/30(日) 01:35:18.53

数学から離れて長かったり数学にあんま縁がない人だと、辺の長さが全部等しい四角形が正方形であることの必要十分条件だと勘違いするのはめちゃくちゃありそう

2022/10/30(日) 14:22:57.27

ARCなくね？
AGCない代わりに最近たくさんあるなと思ってたけど、こっちも放出されつくした？

2022/10/30(日) 14:31:31.53

問題の枯渇で純粋なアドホック考察ゲー作るのが難しくなってきて破綻しつつあるから、アルゴの方はABCの延長線上みたいなゆるふわコンテンツがメインになり、AHCに賭けてるんじゃないかとか邪推してしまうな

2022/10/30(日) 14:56:59.25

短期AHC久しぶりだ

2022/10/30(日) 16:38:01.85

2週間前から始めていますが、AtCoderのBeginnerさえ1問しか解けません
復習はしていますが、全然スキルが上がった感じがしません(´；ω；｀)

2022/10/30(日) 16:41:43.31

とりあえず鉄則本やっておけばいいんじゃないかな

2022/10/30(日) 16:47:38.26

Bが解けないとすると、使用言語の文法みたいな基礎事項から勉強しながらやった方がいいかも
C++使いならAPG4bとか
Python使い用のも探せばあると思う

2022/10/30(日) 16:48:51.47

ARCは今年たくさんやったからいいとして、AGCは本当に生えてこなくなったね

2022/10/30(日) 17:05:56.90

AGC少なすぎて赤以上のレートはあまり参考にならんのよね…

2022/10/30(日) 19:01:29.07

頑張って高速化しただけで終わった

2022/10/30(日) 19:05:21.35

出力しないと次の入力を受け取れないシステムになってることを途中から忘れてたの本当にしょうもないミスだ

2022/10/30(日) 19:23:01.86

AHCはみんながガチすぎないことによって、昔のアルゴにあったっぽい良さが保持されている気がする

2022/10/30(日) 20:26:24.18

本当にちょっとした改善（ただし自分では思いつけない）でスコア爆上がりすることをコンテスト後に知るとめちゃくちゃ悔しい

2022/10/31(月) 00:06:58.82

まずは“本当にちょっとした”とかいう歪んだ認知を直すところからやね

2022/10/31(月) 02:21:24.13

短期コンだと本当にちょっとした改善でスコア爆上がりすることが多すぎて辛い
なんで本番中は入力を虚空に放り投げてることに気付けなかったんだと後悔してる

2022/10/31(月) 12:30:07.84

>>300
ありがとうございます、鉄則本頑張ります

2022/10/31(月) 12:31:58.77

問題に付いてるサンプルケースでは正解なのに、ソースコード提出すると他のテストケースで不正解となるんです

おそらくどこかでオーバーフローしていることが原因です

過去のコンテストのテストケースって全部どこかにアップロードされているんでしょうか？

2022/10/31(月) 13:05:29.42

https://atcoder.jp/posts/20
ないものも多いですしテストケースを見ることは推奨されていません
自力でテストケースを作って頑張る方法を身につけるのがいい
参考：https://betrue12.hateblo.jp/entry/2019/09/07/171628

2022/10/31(月) 13:10:33.60

オーバーフローならC++(gcc)だったら-fsanitize=undefinedで見つかるかも

2022/10/31(月) 13:25:03.50

オーバーフローしていることが原因とまで当たりついてるなら、一ヶ所ずつ型変えて提出してみたら

2022/10/31(月) 13:29:23.39

オーバーフローが原因だと分かってるんならもうACはすぐそこじゃないか
頑張れ

2022/10/31(月) 14:29:51.95

>>312
>>313
貴重な情報ありがとうございます

>>314
>>315
unsigned longでもオーバーフローしてしまいます

2022/10/31(月) 14:46:00.66

実はオーバーフローしてないんじゃない？

2022/10/31(月) 15:57:04.81

まさか余りをとる時に負になるケースを考慮していないとか？
ABC-DEFとか

2022/10/31(月) 16:02:58.05

(-m) % n がマイナスの余りになるという仕様になっているのはなぜですか？
((-m) % n) + n とするのが面倒です。