競技プログラミング総合スレ 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/22(土) 23:26:14.59

Fとか脳死で最適化ライブラリにぶっこんで解けるような問題出してほしい

**デフォルトの名無しさん** (ｽﾌｯ Sda2-JIE3) · 2022/10/22(土) 23:28:05.75

D解かれすぎな気が
部分和とはいえ実装バグりやすいでしょこれ

2022/10/22(土) 23:30:21.82

ナップサックDPはABC中盤に出すぎてちょっとした変形入れてもみんな対応してくるな

2022/10/22(土) 23:35:42.74

>>191
ABCは1問30分ぐらい考えて考察生えなきゃもう解説見ていいレベルだと思うわ
ABCクラスの問題ならAtCoderでもCodeForcesでも無限にコンテストで新問が提供されるし、考える練習はコンテストでやればいい

2022/10/22(土) 23:53:18.15

D問題とけんかった・・・
XとYの行ける位置を全部セットに詰め込んで計算してたけど
4つほど不正解が出る

あと関係なさそうだけど
2 2 1
2 1
が入力としたら答えはNoだよね
同じ位置じゃ線分にならんし、90度も無理あるし

2022/10/23(日) 00:22:16.64

Ex解説見てるけどNimberなんてものがあるのか、知らなかった
というか辞書順比較とロリハって勝手に相性が悪いと思ってたけど、LCP求めて一文字分比較するだけだからロリハでも普通に高速でできるね

2022/10/23(日) 00:25:48.30

>>196
Noだね

2022/10/23(日) 00:32:57.33

LCP求める方法はいろいろあるけど、ロリハにぶたんは直感的にわかりやすくて便利

2022/10/23(日) 00:37:05.68

>>196
どういうこと？Yesでは？

2022/10/23(日) 00:39:06.13

Nimberとかちょっと前に流行った概念Exに出がちだけど次出んのいつやねんという気持ちに

2022/10/23(日) 00:43:07.21

>>200
あ、すまん
A1,A2,A3
x y
の並びかと思った（そんな形の入力ありえんのに）
普通にYesじゃんこれ

**196** (ﾜｯﾁｮｲ 0279-SGBs) · 2022/10/23(日) 00:45:48.66

あ、、、自分のミスだった
最後のA[N]でジャスト(x,y)にたどり着くのか
勝手に最後だけ距離が未定義だと思ってた
すみませんでした！

2022/10/23(日) 00:51:07.79

>>201
こどふぉで役に立つかも精神で・・・
そういえば、ARCはDEとかで割と高度典型が出現することあるけど、AGC後半ってどのぐらい知識が役に立つ問題出るんだろうね
AGCはアドホックの祭典という評判だけはずっと聞いているが、後ろの問題は手をつけていないので実態は知らない

2022/10/23(日) 14:02:32.86

昨日のC問題が全然わからん😭

2022/10/23(日) 14:11:03.89

親子関係を図で書いていったら何すればいいか見通しがいいと思うよ

2022/10/23(日) 15:00:21.51

日本語が難しかったね
ナンバリングの法則がちょっとイメージしにくかったかも

2022/10/23(日) 15:50:26.46

こどふぉdiv 1だ
少ないと思ったら急にたくさん生えてきた

2022/10/23(日) 16:04:19.15

今日のこどふぉ2連続間隔15分しかないのおかしい　

2022/10/23(日) 19:45:09.56

昨日のABCのD問題、
なんかランタイムエラーが5つ程。
C++でもPythonでも同じ。

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

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

どんなエラーになったか確認したくて
テストケース欲しい…
けど、社長はテストケース公開消極派なのね。
自分でテストケース作るのは難しい

2022/10/23(日) 19:51:50.60

今だってABCの範囲だと意味があるのは5問目程度までだろうから、せめてサンプル強くして難易度下げるべき

2022/10/23(日) 20:41:45.90

いうて自分でテスト書いて検証する力って、なんなら本旨の算数パズルよりもずっと実務寄りの能力な気がするが

2022/10/23(日) 20:54:13.16

>>210
とりあえず、限界値っぽいのを入れてみたら？

1000 -10000 -10000
10 10 10 10 10 10 10 10・・・1000個分

2022/10/24(月) 02:06:39.23

茶色になったばっかの新人コーダーだが、
土曜日C問題まで解いたけど若干レート下がった
時間一杯までやってしまったこともあるけど、C問題まで解いただけじゃ緑までいけないのか

2022/10/24(月) 02:22:46.20

だいたいcで茶、dで緑、eで水やね

2022/10/24(月) 02:23:04.27

安定して4完できるぐらいじゃないと緑は無理じゃないかな
緑の過去問を解く練習しよう

2022/10/24(月) 11:29:28.22

なんか勘違いしてね？

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

chokudai視点だとARCもやっぱり典型ゲーなのか

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で正方形の定義書いてほしいと思うのは甘え？