競技プログラミング総合スレ 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/23(日) 00:43:07.21ID:Gmi6Wv/G0
>>200
あ、すまん
A1,A2,A3
x y
の並びかと思った（そんな形の入力ありえんのに）
普通にYesじゃんこれ
2022/10/23(日) 00:45:48.66ID:8R49AjqV0
あ、、、自分のミスだった
最後のA[N]でジャスト(x,y)にたどり着くのか
勝手に最後だけ距離が未定義だと思ってた
すみませんでした！
2022/10/23(日) 00:51:07.79ID:Gmi6Wv/G0
>>201
こどふぉで役に立つかも精神で・・・
そういえば、ARCはDEとかで割と高度典型が出現することあるけど、AGC後半ってどのぐらい知識が役に立つ問題出るんだろうね
AGCはアドホックの祭典という評判だけはずっと聞いているが、後ろの問題は手をつけていないので実態は知らない
205デフォルトの名無しさん (ﾜｯﾁｮｲ 2101-i+dE)
垢版 |
2022/10/23(日) 14:02:32.86ID:kyxqVSK90
昨日のC問題が全然わからん😭
2022/10/23(日) 14:11:03.89ID:Gmi6Wv/G0
親子関係を図で書いていったら何すればいいか見通しがいいと思うよ
207デフォルトの名無しさん (ｱｳｱｳｳｰ Sa45-wDBs)
垢版 |
2022/10/23(日) 15:00:21.51ID:viPCyFgla
日本語が難しかったね
ナンバリングの法則がちょっとイメージしにくかったかも
2022/10/23(日) 15:50:26.46ID:Gmi6Wv/G0
こどふぉdiv 1だ
少ないと思ったら急にたくさん生えてきた
2022/10/23(日) 16:04:19.15ID:XEFfVvHIp
今日のこどふぉ2連続間隔15分しかないのおかしい　
210デフォルトの名無しさん (ﾌﾞｰｲﾓ MM25-I5GH)
垢版 |
2022/10/23(日) 19:45:09.56ID:lki1jgwYM
昨日のABCのD問題、
なんかランタイムエラーが5つ程。
C++でもPythonでも同じ。

配列のサイズを入力した数字の合計(プラスα)から計算した値から定数値に変えたらAC

添え字のチェックして処理を飛ばしてもWAにはならずRE

どんなエラーになったか確認したくて
テストケース欲しい…
けど、社長はテストケース公開消極派なのね。
自分でテストケース作るのは難しい
211デフォルトの名無しさん (ﾜｯﾁｮｲ 46e2-Bggx)
垢版 |
2022/10/23(日) 19:51:50.60ID:aKzhqT3I0
今だってABCの範囲だと意味があるのは5問目程度までだろうから、せめてサンプル強くして難易度下げるべき
2022/10/23(日) 20:41:45.90ID:p0c/ZXMMM
いうて自分でテスト書いて検証する力って、なんなら本旨の算数パズルよりもずっと実務寄りの能力な気がするが
2022/10/23(日) 20:54:13.16ID:E0/FzGoVd
>>210
とりあえず、限界値っぽいのを入れてみたら？

1000 -10000 -10000
10 10 10 10 10 10 10 10・・・1000個分
214デフォルトの名無しさん (ﾜｯﾁｮｲ 81bd-Bq7Q)
垢版 |
2022/10/24(月) 02:06:39.23ID:oE/P7WOq0
茶色になったばっかの新人コーダーだが、
土曜日C問題まで解いたけど若干レート下がった
時間一杯までやってしまったこともあるけど、C問題まで解いただけじゃ緑までいけないのか
215デフォルトの名無しさん (ｱｳｱｳｳｰ Sa45-wDBs)
垢版 |
2022/10/24(月) 02:22:46.20ID:Dpd/V0qca
だいたいcで茶、dで緑、eで水やね
2022/10/24(月) 02:23:04.27ID:y+IDNEc90
安定して4完できるぐらいじゃないと緑は無理じゃないかな
緑の過去問を解く練習しよう
2022/10/24(月) 11:29:28.22ID:aGKh4Pz90
なんか勘違いしてね？
2022/10/24(月) 13:29:43.19ID:go80wyV0M
chokudai視点だとARCもやっぱり典型ゲーなのか
2022/10/24(月) 15:13:18.61ID:cB4C96MB0
chokudaiに限らず、銅冠以上が解けてない問題を典型って言っちゃうのは、典型とは一体っていう感じだけど
2022/10/24(月) 15:13:43.19ID:iZicr3cKp
AVL木とか赤黒木辺りの仕組みをちゃんと理解してないと解けない問題ってある？
こういうのってやっぱり競プロ文脈だと自力で実装する必要ないのかな
2022/10/24(月) 15:56:17.71ID:aGKh4Pz90
avl木を題材にした問題は見たことあるけど仕組みの理解が必要かは疑問
せいぜい問題設定の理解が楽になる程度じゃないかなあ

その場でちゃちゃっと機能付け足せるくらい手に馴染んだ平衡二分木持ってると得するっつーか楽できる場面は結構ある
2022/10/24(月) 16:57:52.37ID:CSVgb4N80
確か赤黒木は、木の再構成を頻繁に行わないように、
木の高さが2倍になった時に初めて、再構成するのでしょ？

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

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

フェニック木やセグ木以外で、平衡二分木の実装まで要求してしまうとそこそこ重いし、深い理解を要求する問題にはあんまり遭遇しなそう
逆にいうと、セグ木でだいたいなんとかなってしまうともいえる
2022/10/24(月) 18:27:07.50ID:k0ED32Xq0
平衡二分探索木のmerge-split系の操作が難しめの問題で役に立つみたいなのたまに見るけど、その辺り詳しくない
まあ、自作平衡二分探索木があると、std::setにない機能を追加できたり何かと捗るので自分で実装するのも悪くないと思うよ
順位取得とかね
座圧セグ木でもできることが多いけど
2022/10/24(月) 18:59:23.04ID:aGKh4Pz90
オフライン性活かした実装ってダルいからそれスキップできるだけでも強い
永続系も似た用途で使えることあるね
2022/10/26(水) 14:14:56.58ID:5UZuNyz10
???「赤にいかないうちは、典型も解けていないという証拠なのでどんな問題がでても文句を言わずに解きましょう」
2022/10/26(水) 20:39:16.10ID:wSmiQUDJ0
bit系のオリジナルライブラリ作ったけどstdの方が16倍くらい早くて泣いた
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使い用のも探せばあると思う
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況