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

■ このスレッドは過去ログ倉庫に格納されています
1デフォルトの名無しさん (ﾗｸｯﾍﾟﾍﾟ MM7f-osoq)
垢版 |
2022/10/02(日) 17:43:58.66ID:FqAfPtIrM
↑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/26(水) 23:49:51.56ID:PGlvwJA80
charでも使ってんのか
229デフォルトの名無しさん (ﾜｯﾁｮｲ 0255-w3aL)
垢版 |
2022/10/27(木) 16:34:41.72ID:dAuDGVLY0
ハードウェアとかコンパイラとか全然知らないのですが、

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

とか初期値を指定して初期化する場合、初期化の処理にΘ(N^2)回の計算量が必要になりますか？
230デフォルトの名無しさん (ｱｳｱｳｳｰ Sa45-dV9P)
垢版 |
2022/10/27(木) 16:35:26.87ID:efUshkpEa
なる
231デフォルトの名無しさん (ﾜｯﾁｮｲ 0255-w3aL)
垢版 |
2022/10/27(木) 16:57:58.07ID:dAuDGVLY0
>>230
ありがとうございました。
232デフォルトの名無しさん (ﾜｯﾁｮｲ 0255-w3aL)
垢版 |
2022/10/27(木) 17:00:44.14ID:dAuDGVLY0
でも不思議です。
今まで
>>229
のようなコードを例えば、O(n * log(n))の計算量が求められる問題で使用してきましたが、
ちゃんとパスしてきたと思います。
>>229
のようなコードがあるとそれだけでO(n^2)以上の計算量が必要ですよね？
n^2の係数が極端に小さいんですか？

いずれにしても理論的にはO(n^2)以上ということになりますよね？
2022/10/27(木) 17:36:43.76ID:RXobkv660
そう、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.04ID:RXobkv660
すまん、2453msじゃない
終了コード9で終わってたからただのタイムアウトだった
まあダメってことだ
235デフォルトの名無しさん (ﾜｯﾁｮｲ 0255-w3aL)
垢版 |
2022/10/27(木) 17:39:59.24ID:dAuDGVLY0
>>233-234
ありがとうございました。
今度から意識して初期化するようにしてみます。
2022/10/27(木) 17:44:47.51ID:9aVmm+3a0
vector上の数字を全部0にセットする処理はかなり定数倍軽そうだし、思ったよりも通りそうではある
もちろん無意味なオーバーヘッドを生んでるだけなのでやめた方がいいけど
2022/10/27(木) 18:18:50.06ID:CyvCxP85d
メモリをN^2使ったら駄目だろ
2022/10/28(金) 02:02:28.05ID:O+kal+GIM
>>234
タイムアウトではなくメモリの方だね
コードテストだと10秒待ってくれる

>>236
何と比較するかではあるけどメモリ確保は一般には定数倍重い部類の操作だと思う
2022/10/28(金) 02:05:18.44ID:yFKHaKvH0
ああ、たしかにめっちゃメモリ食うやん
240デフォルトの名無しさん (ﾜｯﾁｮｲ 0255-w3aL)
垢版 |
2022/10/28(金) 04:18:20.91ID:XEpm5NPR0
でもN^2のメモリが必要な問題もありますよね。
迷路の問題とか。
2022/10/28(金) 04:58:13.49ID:HEmow1maa
具体的な問題あげてみなよ
2022/10/28(金) 10:38:59.44ID:wJEv6FjSM
当たり前だけどNの大きさによるので
Nが3000以下とかならN^2のメモリ確保でもどうにかなるし、100000なら無理というだけ
2022/10/28(金) 11:25:04.27ID:tzaausWG0
O(N^2)って"高々"N^2の定数倍で抑えられる、だから計算量がNでもlogNでもO(N^2)だし、今回の文脈で使われると典型的な誤用で気持ち悪く見えるな
2022/10/28(金) 11:51:58.80ID:lD5FibjIM
じゃあΩ(N^2)使ってくか
2022/10/28(金) 13:48:32.69ID:55wbFwqJM
こことかTwitterとかでやりとりする分には大抵オーダー記法とっぱらっちゃっても伝わるな
誤用よりマシな気がする
2022/10/28(金) 13:51:51.24ID:yFKHaKvH0
>>229,240 を見る限り制約に全く触れられてないので、計算量についてなにか勘違いしていそう
2022/10/28(金) 16:54:39.37ID:ICdwrTkda
N^2がTLEするようなNの大きさならN^2のサイズの領域確保したらだいたいMLE
2022/10/28(金) 21:34:06.53ID:subS4Uwn0
基本的にTLEにならないコード書けば自然とMLEも回避できると思ってる
249デフォルトの名無しさん (ﾜｯﾁｮｲ 1355-FQW+)
垢版 |
2022/10/29(土) 12:58:54.16ID:mklHRG3O0
C++のpriority_queueについて質問です。

優先度付きキューに入っているある要素の優先度を変更する方法ってありますか？
2022/10/29(土) 13:23:15.94ID:XKYsH2uyM
高速な方法は、ない
251デフォルトの名無しさん (ﾜｯﾁｮｲ 1355-FQW+)
垢版 |
2022/10/29(土) 13:32:10.33ID:mklHRG3O0
>>250
自分で作るしかないということですか。
ありがとうございました。
2022/10/29(土) 13:48:55.13ID:obGqM2Iua
古い優先度の要素は残したまま新しい優先度の要素を突っ込んで、
取り出したときに優先度が古ければ無視

で大体なんとかなる印象
2022/10/29(土) 14:29:52.84ID:ALsCFNRZ0
ダイクストラのやつね
2022/10/29(土) 14:39:48.64ID:ALsCFNRZ0
Fibonacci heapは優先度を変えられるからダイクストラの計算量が落ちるってことだったのか
255デフォルトの名無しさん (ｱｳｱｳｳｰ Sa9d-gcVw)
垢版 |
2022/10/29(土) 16:17:47.20ID:cBW2XQMEa
N^2の計算ができるって、江戸時代からしたらものすごいことなんだけど人類はまだそれでも飽き足らないからすごいことだよね
2022/10/29(土) 17:02:47.53ID:1nZDK7qud
そこからさらに、並列処理可能にして一気に処理したり
根底から覆す量子コンピュータとか
257デフォルトの名無しさん (ﾜｯﾁｮｲ 1355-FQW+)
垢版 |
2022/10/29(土) 17:36:48.50ID:mklHRG3O0
>>252-254
ありがとうございました。

>>252
なるほど、それでも全く問題ないですね。
気持ち的には、ちょっと気持ちが悪いですが。
2022/10/29(土) 20:07:47.15ID:81wL0y4v0
自作するとして、元の要素がどれか特定する部分が遅いんだよな
よくある実装だとunordered_map使うから定数倍が重い
acl::maxflowのadd_edgeのように、要素を追加したら後で優先度を変更する際の引換券を返すのが良いのか？
2022/10/29(土) 22:41:09.93ID:2S1iCoxk0
E問題。。。。
t-1回目にどのマスにいるかの確率（というか回数）を出して
t回目にどのマスにいるかを算出すればできるってことはわかってるのに時間が足りない。。

しかしこの考え方ってあってるのかな
dp的にやると100万×動けるマス10マスで1000万だからこのままやっても計算量的にアウトだったんだろうか
260デフォルトの名無しさん (ﾜｯﾁｮｲ 7be2-tAkO)
垢版 |
2022/10/29(土) 22:41:56.11ID:uHm3dTvI0
実装重いのをCに置くのはほんとやめて
2022/10/29(土) 22:44:01.17ID:2S1iCoxk0
公式解説もNMKだったから一応あってるのか

今回の結果
https://imgur.com/a/C2RD1bF
この間茶色になったばっかりだが、少しでも緑に近づけてることを願う
2022/10/29(土) 22:45:05.88ID:yV+y7EmI0
>>259
あってるぞ、O(NMK)になるからな
2022/10/29(土) 22:46:38.52ID:2S1iCoxk0
https://imgur.com/c9Dco1P
ええ。。
Cを一回間違えてしまったとはいえ4完全したのにマイナス6かよ、、、緑むりげーだろ
2022/10/29(土) 22:47:59.86ID:2S1iCoxk0
>>262
公式見るとあっていたみたいだね。
ただ、低速な言語だと間に合わないで前計算が必要って書いてあったけド、このあたりまだ理解できていないので分数のmodについてちゃんと理解しておくようにする
2022/10/29(土) 22:48:01.40ID:fWX5042N0
Eは解説とほぼ同じように作ったのに1時間最後まで合わなかった…むなしい…
2022/10/29(土) 22:50:45.78ID:2S1iCoxk0
でもE問題が射程範囲に入ったのはちょっと嬉しかった。
C問題がかなり苦戦して、どっち方向に直交ベクトルをかけるかっていう部分に関してかなり苦労してしまった。
結局2パターンについてべた書きしてしまった

D問題はメモ化再帰して一瞬だった。
C飛ばしてEに挑戦してればレーティング上がったのかな
2022/10/29(土) 22:52:01.22ID:yV+y7EmI0
>>263
それ前回のパフォじゃん
さすがに今回はレートあがるだろ
2022/10/29(土) 22:52:46.63ID:KrD0TJfX0
>>263
これに表示されてるは前回の結果だよ　コンテスト名を見ればわかる
今回も含めてコンテストの結果は数時間後に出る事が多いから終わってすぐには反映されないよ
2022/10/29(土) 22:54:16.01ID:2S1iCoxk0
>>267-268
ほんまやあああああああああ
サンクス
しかしC問題で一回間違えた(直交方向に足した値が範囲内でおさまってるかの処理を書き忘れた）ので少しそれが心配。。
2022/10/29(土) 22:54:24.14ID:KrD0TJfX0
あとそのレートで4完してるなら今回でレートは100くらい上がるんじゃない？
2022/10/29(土) 22:55:21.84ID:CGLSS5oS0
ac-predictor入れなよ
2022/10/29(土) 22:57:09.33ID:KrD0TJfX0
レートの更新が来てるわね
2022/10/29(土) 22:57:27.79ID:2S1iCoxk0
https://imgur.com/a/5ACK8kd
ほんまやああああああ
緑色がみえてきたあああああああ

E問題まで確実にとけるように頑張りたい
2022/10/29(土) 22:58:19.47ID:xju5Olpip
Fって精進すればDP使おうってすぐ見抜けるようになるものなん？
2022/10/29(土) 22:59:37.34ID:94koNtTB0
うん
2022/10/29(土) 23:04:29.61ID:fWX5042N0
dpのiとjのループの順番を逆にしたら通った…
2022/10/29(土) 23:07:12.53ID:n8+2LG4s0
Fはいつもより典型度高めかな
ナップサックDPをするついでに、選ぶときの遷移と選ばないときの遷移でちょっと処理を変えるみたいなのは結構見る
2022/10/29(土) 23:08:20.93ID:2S1iCoxk0
from functools import lru_cache
pythonってメモ化再帰再帰が標準実装されてるんだ
知らなかった・・
どうやって制御してるんだって感じだが、やっぱり標準モジュール？ってすごいな
2022/10/29(土) 23:13:13.23ID:n8+2LG4s0
実際どうやってんのか知らないけど、メモ化再帰の実装はpythonのデコレータと相性いいと思う
2022/10/29(土) 23:18:18.42ID:n8+2LG4s0
計算時間の見積もりだけど、ラフに計算して10^8以下で平均的な定数倍の重さだったら2 secで間に合うし、普通に想定解になりうると思うよ
2022/10/29(土) 23:19:43.68ID:yV+y7EmI0
簡単にいうと、デコレータで内部的にdictを作って、引数と戻り値つっこんでるだけでしょ
dictより自分でlistを使ってメモ化したほうが高速だし、別にlru_cacheは覚えなくてもいい気がするな
2022/10/29(土) 23:25:38.82ID:2S1iCoxk0
標準実装部分って一度Cでコンパイルされてるから自前実装より速いと思っていたんだけどどうなんだろう。
あとdictってハッシュだから速いと思ってたんだけどlistの方が早いっていうことってあるの？
インデックスへのアクセスがn(1)だとしても再帰関数の場合はインデックスもばらばらだと思ったんだけど
283デフォルトの名無しさん (ﾜｯﾁｮｲ 7be2-tAkO)
垢版 |
2022/10/29(土) 23:30:42.87ID:uHm3dTvI0
mod逆元なんて意味不明な計算させんでも、誤差を認めた小数でええやん
2022/10/29(土) 23:30:58.93ID:n8+2LG4s0
Pythonの標準実装は、Cで高速化されて優秀なときと生Pythonで微妙な実装が施されていてひどいときの両方がある印象だね
PyPyに至っては最適化の仕方がよくわからないから実際に試すしかない
2022/10/29(土) 23:36:12.18ID:NT00hHOFM
>>282
ハッシュ化のオーバーヘッドがあるから、とりうる引数の値が小さいんならlistの方が定数倍速いこともありうる
今回はそもそもlistでは対応できないはず
2022/10/29(土) 23:36:54.42ID:DPwzGxhV0
Pythonを使ってた時は自前で書いた二分探索だと通らなくてそこを二分探索のライブラリに置き換えたら余裕を持って通ったことがあったからCによる高速化の恩恵は大きそう
287デフォルトの名無しさん (ﾜｯﾁｮｲ 69bd-8V2j)
垢版 |
2022/10/29(土) 23:42:41.35ID:n8+2LG4s0
>>283
ターンが進むごとに指数的に減衰していきそうな行動パターンまでちゃんと追跡できてるかを問いたいとすると、mod逆元の方がいいと思う
まあ、小数解答方式でそういうタイプの枝刈りで通せる人はそもそも今回の問題だと問題なく想定解にたどり着ける気がするけど
2022/10/29(土) 23:45:49.46ID:NT00hHOFM
Ex、ぱっと見Cartesian木で貪欲でいけるんじゃないかと思ってしまうが、そんな単純な問題じゃないっぽい
2022/10/29(土) 23:48:54.20ID:fWX5042N0
んー、F難しくはなかった
毎回変なところで失敗するからたどり着けないけど
2022/10/30(日) 00:52:02.32ID:m4pYUh8Q0
Eまでは安定するようになってきたけどFが中々安定しない
今回のFは素直なDPで良いって聞いたらすぐだったのに
2022/10/30(日) 01:22:58.95ID:NjCulbvXM
Cで正方形の定義書いてほしいと思うのは甘え？
2022/10/30(日) 01:28:08.60ID:FuzvB50W0
GもExも見方によってはLPだし後ろの方はLP回だったのかも
293デフォルトの名無しさん (ﾜｯﾁｮｲ b3bd-gcVw)
垢版 |
2022/10/30(日) 01:28:10.10ID:vMGX6/JC0
長さが同じっていうだけで判定すると菱形も拾ってしまうよね

直行条件って内積知らないと厳しいと思うけど、やっぱり数学の知識が必要なんだと思った
2022/10/30(日) 01:31:32.00ID:FuzvB50W0
>>290
部分和をちょうどxにするときに何かを最適化する問題って地味に取れる手立てが少なくて（今回のGみたいに例外的に連続緩和できるとかならともかく）、ABCだったらナップサックDPを出発点に考えても大体外れないと思う
2022/10/30(日) 01:35:18.53ID:FuzvB50W0
数学から離れて長かったり数学にあんま縁がない人だと、辺の長さが全部等しい四角形が正方形であることの必要十分条件だと勘違いするのはめちゃくちゃありそう
2022/10/30(日) 14:22:57.27ID:rp4qVfcRM
ARCなくね？
AGCない代わりに最近たくさんあるなと思ってたけど、こっちも放出されつくした？
2022/10/30(日) 14:31:31.53ID:rp4qVfcRM
問題の枯渇で純粋なアドホック考察ゲー作るのが難しくなってきて破綻しつつあるから、アルゴの方はABCの延長線上みたいなゆるふわコンテンツがメインになり、AHCに賭けてるんじゃないかとか邪推してしまうな
2022/10/30(日) 14:56:59.25ID:m4pYUh8Q0
短期AHC久しぶりだ
2022/10/30(日) 16:38:01.85ID:D0tYX88gx
2週間前から始めていますが、AtCoderのBeginnerさえ1問しか解けません
復習はしていますが、全然スキルが上がった感じがしません(´；ω；｀)
2022/10/30(日) 16:41:43.31ID:o9yKLUrNp
とりあえず鉄則本やっておけばいいんじゃないかな
2022/10/30(日) 16:47:38.26ID:FuzvB50W0
Bが解けないとすると、使用言語の文法みたいな基礎事項から勉強しながらやった方がいいかも
C++使いならAPG4bとか
Python使い用のも探せばあると思う
2022/10/30(日) 16:48:51.47ID:FuzvB50W0
ARCは今年たくさんやったからいいとして、AGCは本当に生えてこなくなったね
2022/10/30(日) 17:05:56.90ID:o9yKLUrNp
AGC少なすぎて赤以上のレートはあまり参考にならんのよね…
2022/10/30(日) 19:01:29.07ID:+gGQ3BRS0
頑張って高速化しただけで終わった
2022/10/30(日) 19:05:21.35ID:m4pYUh8Q0
出力しないと次の入力を受け取れないシステムになってることを途中から忘れてたの本当にしょうもないミスだ
2022/10/30(日) 19:23:01.86ID:rp4qVfcRM
AHCはみんながガチすぎないことによって、昔のアルゴにあったっぽい良さが保持されている気がする
2022/10/30(日) 20:26:24.18ID:YI631LzC0
本当にちょっとした改善（ただし自分では思いつけない）でスコア爆上がりすることをコンテスト後に知るとめちゃくちゃ悔しい
2022/10/31(月) 00:06:58.82ID:hSKO4zcmM
まずは“本当にちょっとした”とかいう歪んだ認知を直すところからやね
2022/10/31(月) 02:21:24.13ID:XwJ24qqi0
短期コンだと本当にちょっとした改善でスコア爆上がりすることが多すぎて辛い
なんで本番中は入力を虚空に放り投げてることに気付けなかったんだと後悔してる
2022/10/31(月) 12:30:07.84ID:qgwFPKRF0
>>300
ありがとうございます、鉄則本頑張ります
2022/10/31(月) 12:31:58.77ID:qgwFPKRF0
問題に付いてるサンプルケースでは正解なのに、ソースコード提出すると他のテストケースで不正解となるんです

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

過去のコンテストのテストケースって全部どこかにアップロードされているんでしょうか？
2022/10/31(月) 13:05:29.42ID:MMRjCKAsd
https://atcoder.jp/posts/20
ないものも多いですしテストケースを見ることは推奨されていません
自力でテストケースを作って頑張る方法を身につけるのがいい
参考：https://betrue12.hateblo.jp/entry/2019/09/07/171628
2022/10/31(月) 13:10:33.60ID:MMRjCKAsd
オーバーフローならC++(gcc)だったら-fsanitize=undefinedで見つかるかも
2022/10/31(月) 13:25:03.50ID:xYj0Vm7Pa
オーバーフローしていることが原因とまで当たりついてるなら、一ヶ所ずつ型変えて提出してみたら
2022/10/31(月) 13:29:23.39ID:lvkiQp2cM
オーバーフローが原因だと分かってるんならもうACはすぐそこじゃないか
頑張れ
2022/10/31(月) 14:29:51.95ID:qgwFPKRF0
>>312
>>313
貴重な情報ありがとうございます

>>314
>>315
unsigned longでもオーバーフローしてしまいます
2022/10/31(月) 14:46:00.66ID:yghxSU5fd
実はオーバーフローしてないんじゃない？
2022/10/31(月) 15:57:04.81ID:XwJ24qqi0
まさか余りをとる時に負になるケースを考慮していないとか？
ABC-DEFとか
319デフォルトの名無しさん (ﾜｯﾁｮｲ 1355-FQW+)
垢版 |
2022/10/31(月) 16:02:58.05ID:I3dWRJ7/0
(-m) % n がマイナスの余りになるという仕様になっているのはなぜですか？
((-m) % n) + n とするのが面倒です。
2022/10/31(月) 16:03:27.21ID:cNn+NHKm0
>>299,310,311 が同一人物だとしたら、そのレベルならあらゆるミスをしそうだし、原因はなんともかんとも
愚直で応えるコードを書いてもバグらせそうだし、他の人がACしたコードと比べてみるのがいいんじゃないか・・・
2022/10/31(月) 16:27:35.89ID:4XZxl/4jM
WAの原因なんてオーバーフロー以外にも無数にあるぞ
バグ、mod取り忘れ、コーナーケース、そもそも解法が間違ってる、等
2022/10/31(月) 16:34:07.66ID:yghxSU5fd
>>319
C++の整数型は(m/n)*n + m%n == mが成り立つことになっていて、除算は0方向に丸めることが規定されているからです（C++11以降）
modintがおすすめ
2022/10/31(月) 17:50:46.88ID:lvkiQp2cM
標準的な型の演算規則ぐらいは身に染み付いてた方が良いと思うので、modintなしで地雷踏み尽くして覚えていくのもありではある
324デフォルトの名無しさん (ﾜｯﾁｮｲ 2bbd-gcVw)
垢版 |
2022/10/31(月) 18:15:49.14ID:hz0WOit40
競プロって意味ないって言われてるけどどうなんだろうね？俺は楽しいからやってるけど

確かにこのアルゴリズムを直接的に実務で使うことはあまりないかもしれないけど、バグの発見とかは競プロで鍛えると速くなる気はしてる
2022/10/31(月) 18:22:42.24ID:cNn+NHKm0
まあ高校の数学と同程度には役に立つよ

ようするにめったに使わないし、そんな知識を活用せずに大成功してるひとのほうが多いくらい
2022/10/31(月) 19:21:20.60ID:sCpxrilS0
脳トレが出来るオンラインゲームみたいなもんだし実生活に役立ったら美味しいくらいの気持ちで良さそう
2022/10/31(月) 19:28:31.38ID:GYR048690
ABCのD問題までスムーズに解けたらあとは趣味程度に思った方がいいと思うよ
逆にD問題までスムーズに通せるようになることで、ある言語で手早くスクラッチする力や計算量を意識する力はかなり身につくと思う
2022/10/31(月) 19:36:01.13ID:GYR048690
あと、アルゴリズムに興味を持つきっかけになるかな
スタックがLIFOでキューがFIFOだとか基礎教養でやったとき、正直つまらない暗記対象としか思ってなかったけど、ちゃんと意味があって重要だということが分かった
SQLでB木使うとかも競プロやらなかったら意識しなかっただろうし
ハマる人とっては情報科学の入口として優秀じゃないかな、競プロと相性悪い人はストレートに勉強した方がいいんだろうけど
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況