競技プログラミング総合スレ 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/20(木) 19:48:25.32

形式的べき級数の利用法として典型的なのは、数え上げのDP遷移を畳み込みとみなして高速化することかな
FFT使ってO(N^2)をO(NlogN)にする
maspyさんのブログの「数え上げとの対応付け」の記事とかが分かりやすい
同じ形の遷移をＱ回するときとかは、周波数領域表現の方で各点を累乗すればいいとか、DP遷移の「逆変換」を考えたいときがあって、それは逆関数に対応するから機械的な代数学的操作で導出できるようになったり、恩恵はいろいろ

2022/10/20(木) 19:56:58.93

解析学の知識がなきゃ理解できないという部分はなさそう
形式的べき級数の微分とかオイラーの等式とか、基礎的な知識は要求されるけど、高校数学ちゃんとやってきた人なら適宜ググればどうにかなるレベル

2022/10/20(木) 20:35:33.61

形式的べき級数を使って解く問題ですが、なんかアルゴリズムの問題としては特殊すぎませんか？

例えば、プログラミングコンテストに、整数論的なアルゴリズムを使って解くような問題が出たとしたら、
場違いな感じがしますが、それと同じような感じがします。

2022/10/20(木) 21:33:57.26

情報科学の基礎や離散数学的なアルゴリズムが守備範囲のコンテストだから特殊とは思わないかな
学究的な観点ではそれらも十分アルゴリズムのメジャー領域かと

2022/10/21(金) 08:24:36.19

競技プログラミングという名前に引っ張られすぎ
整数論とかも全然メインストリートやで

2022/10/21(金) 09:58:25.01

mod 素数数え上げのときモジュラ逆数を O(logP) で求めるのは整数論的アルゴリズム？だけどそれも場違いだと思ってる？

2022/10/21(金) 11:01:06.99

競プロ全体でもそこそこ整数論を使うけど、AtCoderだと特に出題傾向が高いよな
実装が重い有名アルゴリズムは出さないって公式で宣言してるから、結果的に考察偏重にしようと数学ばっかりになってる

2022/10/21(金) 13:46:22.49

趣味が合わないならコドフォに移るのもあり

2022/10/22(土) 00:53:27.78

学生時代はこんなもんいつ使うんだよｗ
と思ってたのに、仕事でFFT実装する羽目になった
使い道は確かに素晴らしいものの

2022/10/22(土) 01:21:13.01

FFTってライブラリに突っ込むだけじゃないの・・・・

2022/10/22(土) 13:04:38.07

可変長のビット列を扱うにはどうすればいいのでしょうか？

2022/10/22(土) 13:37:36.07

キーエンス産の問題難しいイメージあるから不安

2022/10/22(土) 13:48:45.77

>>176
vector<bool>を使いたいという話？

2022/10/22(土) 13:59:43.71

問題提供キーエンスなのか
社内にこういうのができる人員を抱えてるのはええな

2022/10/22(土) 16:48:43.35

>>178
それだと出力がtrue/falseになってしまうので、01で扱えると嬉しいです

2022/10/22(土) 17:29:32.23

>>180
vectorのboolだけ特殊化されてるのよ

2022/10/22(土) 18:12:42.91

確かキーエンスは、不可能な問題を解決する会社だから、
バリバリ理系のイメージある

Google の面接の難問、
無限格子の桂馬の位置の電気抵抗を求めよとか

2022/10/22(土) 18:22:25.60

キーエンスは営業が強くて徹底的に収益をプランニングするB2Bボッタクリ企業のイメージが・・・

2022/10/22(土) 18:28:53.32

一部の問題提供ってどうせ前半だからあんま関係ないな
前は典型をそのまま出してて噴飯ものだったわ

2022/10/22(土) 20:09:16.07

競プロってなんか意味あるの？
よく知らんけど実務とも学問とも違うだろあれ

2022/10/22(土) 20:45:00.56

パズルゲームだね
こういうパズルゲームを好きな人が競プロをきっかけに興味関心の幅を広げて情報科学の勉強につながることもあるから、役に立たないとは思わないけど、別に好きじゃないんならやらなくてもいいと思う

2022/10/22(土) 20:50:00.17

意味あるからGoogleなんて20年近くも前からコンテストやり続けてるじゃん

2022/10/22(土) 22:40:12.40

Dですが、部分和問題だと気づいたのですが、実装まで行きませんでした。

2022/10/22(土) 23:06:40.62

F、G辺りに置かれてても問題文の主旨自体は簡潔なことって結構あるんだね
普段Eくらいまでしか解けないからそこら辺の問題は歯が立たないのかなって思い込んでスルーしがちだったけど軽いアプローチくらいなら思いつくしもう少し上のレベルの問題も取り組んでいくべきか

2022/10/22(土) 23:12:40.39

ABCだったらExですら知識一発芸が結構出るから、後ろの問題だから考察難しいって感じでもないよ

2022/10/22(土) 23:24:01.65

なるほど
ABCとARCAGCで傾向結構違うのは感じてたけどABC産なら典型寄りだろうし解説見るハードル下げても良さそうな感じか

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に挑戦してればレーティング上がったのかな