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

2021/07/28(水) 21:58:48.02

!extend:checked:vvvvv:1000:512
↑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/

※前スレ
競技プログラミングにハマるプログラマのスレ 62
https://medaka.5ch.net/test/read.cgi/prog/1626625368/

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

2022/09/28(水) 16:47:43.15

大槻のAtCoder入門を図書館から借りてきましたが、やさしすぎますね。

2022/09/28(水) 17:47:31.56

>>883
左の円の色とか円の中のゲージがdifficulty

2022/09/28(水) 18:08:29.44

>>885
ありがとうございました。マウスのポインターを円の上に持っていったら表示されました。

2022/09/28(水) 21:41:22.84

大槻のアルゴリズムとデータ構造の本に、クラスカルのアルゴリズムの計算量が、
O(|E| * log(|V|)) であると書いてあります。

なぜ、 O(|E| * log(|E|)) と書かないのですか？

2022/09/28(水) 22:01:47.27

文脈が分からないけど、単純グラフって仮定があるんなら|V|^2>|E|だからってことで深い意味はないと思う
強いて言えば|V|の方がlogのお得感が出るとか？

2022/09/30(金) 12:34:13.21

大槻のAtCoder入門という本に、頂点の数 N、辺の数 Mのグラフの構造の入力の受け取る処理に
O(N + M) の計算量が必要だと書いてあります。

O(M) が正しいと思いますが、どうですか？

2022/09/30(金) 12:34:55.30

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

2022/09/30(金) 12:35:34.42

辺の数がゼロのグラフとか

2022/09/30(金) 13:36:02.20

入力長はO(M)だけどvectorの確保にO(N)かかりそう

2022/09/30(金) 14:19:09.50

本当にグラフの構造情報を受け取るだけであればO(M)でいいけど、後続の処理で結果的にはO(N+M)かかることがほとんど
ただ、たとえばN=10^100, M<=10^5みたいなパターンの問題も考えうるから、O(N+M)よりはO(M)の方が正確かな、特に他に但し書きがないのであれば
かなり自明な話なので、そこのO(N+M)の記述で混乱して問題を解くのに支障が出る人はいない気がするけど

2022/09/30(金) 14:35:51.41

すべて入力から受け取る必要があるならそら入力にO(N+M)かかるやん
入力の辺は重複しないみたいな条件がついてるなら、O(N^2)あるいはO(M)になったりする

2022/09/30(金) 20:10:13.70

>>891-894
ありがとうございました。

明日の午後9時からの「AtCoder Beginner Contest 271」に参加予定なのですが、
何問くらい解けるのが平均的なんですか？
100分しか時間がないのでおそらく2,3問しか解けないと思っています。

2022/09/30(金) 20:13:19.02

大槻の『AtCoder入門』という本を図書館から借りてきて第5章の中級編の最後まで読み終わりました。
そこまでの問題であれば、時間がかかったものが多いですが、すべて独力で解けました。

2022/09/30(金) 20:23:47.23

そうなんだすごいね

2022/09/30(金) 20:30:00.67

大槻って呼ばれてるの違和感しかない

2022/09/30(金) 22:00:39.59

東大出身のNTTなら敬称は殿だろね。
本もたくさん出してるし。

2022/09/30(金) 22:11:04.33

参加者の過去の成績や練習量はすべて公開されています
実力のある参加者は大量の問題を解いています
自分の成績が今ひとつでも気を落とさないことです

2022/09/30(金) 22:17:34.52

例えば、大槻の『AtCoder入門』という本の上級編の1問目の「abc115_d」の問題ですが、独力で解けました。
基本的なアイディアはすぐに浮かんだのですが、パスするのに1時間もかかってしまいました。
そして、練習を重ねてもこの時間を短くすることは難しいのではないかと思います。

2022/09/30(金) 22:20:59.94

あと一つ質問ですが、問題の解答(AC)を、計算時間の短い順にソートすると、上位の
解答の計算時間が異常に短いです。

ソースを見ても、アイディアは同じなのになぜあんなに速くできるのでしょうか？

計算時間のコンテストではないので、レーティング上は、あまり重要ではないと思いますが、
気になります。

2022/09/30(金) 22:53:54.54

解ける問題数については、三問解ければまずOKで、あわよくば四問解くことを目標にするぐらいじゃないかな
初回参加だとC問題解けない人の方が多そうな気がするし四問解ければなかなかだと思うよ
ABCは毎週開催されるようなものだし、一回一回の結果を気にしない方がいい、特に最初は
レートには直近10回程度の結果が反映されるから、今回失敗しても続けてればすぐにその影響を消せる
あと、参加回数が少ないとレートがめちゃくちゃ低く算出される仕組みなので、パフォーマンスを自分の成績指標として見よう

2022/09/30(金) 23:07:02.91

平均的な話をすると、どうなんだろう
AtCoderから競プロ始めた人だったら一から二完の間じゃないかな、そもそもプログラミング初心者も多いし
あと、上級者のコードが速いのは、再帰関数を非再帰にするとか、キャッシュ効率をよくするとか、入出力を高速化するとか、コンパイラのオプションを変えるとか、そういう細かい工夫の積み重ねだと思う
C++だったら別に意識しなくても問題ない気がするけど、Python使いだったら再帰を非再帰にするとか入出力高速化ぐらいはやっとくと、ABC-E問題以降楽そう

2022/09/30(金) 23:13:27.03

つけくわえるとABC-Dまではかなり典型度の高い定型的な問題が多いので、練習すれば解答時間は縮められる方の問題だと思うよ

2022/09/30(金) 23:17:37.45

レートでいうと100で上位50%みたいな感じだった気がするし、平均的なひとだったら最初は2完で上出来かね
強い人だと初参加でも3完か4完らへんをやってパフォ1000超えてるのが珍しくないけど

2022/09/30(金) 23:53:23.95

こどふぉもやりたいけど23時半から2時間ってのが微妙だな～
眠くなっちゃうんだよなぁ

2022/10/01(土) 00:16:22.62

社会適合者⁉

2022/10/01(土) 00:18:46.82

末尾再帰で最適化できる言語もある

2022/10/01(土) 00:23:21.36

schemeだけちゃうんけ？仕様で定められてるのは

2022/10/01(土) 00:31:45.72

再帰だとPyPyよりもCPythonのほうが早いらしいけど、なんでそうなるのか気になる

2022/10/01(土) 20:55:59.80

ヒューリスティックコンテスト向けのおすすめ本ってあります？

2022/10/01(土) 22:48:49.05

A, B, Dしか解けませんでした。
Cはソートして、巻番号が小さい順に見ていって抜けている巻を、巻番号がもっとも大きな2巻を売って買う
ということを繰り返せば良さそうでしたが、実装が面倒だと思い飛ばしました。

2022/10/01(土) 22:50:22.12

Cは二分探索を使う解法にすれば実装がクソ軽いよ

2022/10/01(土) 22:50:52.66

>>903-906,909-911
ありがとうございました。

2022/10/01(土) 22:52:49.49

>>914
ありがとうございます。考えてみます。

2022/10/01(土) 22:52:51.85

Cはにぶたんが楽だったな
愚直にシミュレートしたら3wa,2wa,1wa,1wa…って感じになったぴえん

2022/10/01(土) 22:53:56.43

>>917
おれもシミュレートしたけどWAを潰しきれなくて、二分探索にしたら瞬殺できてなんか悲しかった

2022/10/01(土) 23:00:56.33

8月から競プロ始めて現在レート337の雑魚

Dは楽だったけどCでwa出してしもうた。。
明日のレギュラーも参加するか

2022/10/01(土) 23:08:50.61

(N-最初に持っている本で読む本の数)/2 >= (これまでの不足している本)で判定すれば別に二分探索もいらないと思うけれど

2022/10/01(土) 23:11:38.80

Exってこれ典型なのかな？
解説見てみたらどことなくARCの難問っぽいけど

2022/10/01(土) 23:20:11.35

ABCのDまでは安定して解けるようになったけどEになった途端全然安定しなくなるのシンプルに過去問解き進めるしかないかな

2022/10/01(土) 23:21:52.81

というかCの制限時間が4秒だったのってどういう想定？二分探索でもシミュレーションでも割と余裕ある気が

2022/10/01(土) 23:25:52.82

確かにCの制限時間よくわからないね
set使うと結構定数倍重くなるのかな？

2022/10/01(土) 23:28:08.04

パスの復元じゃなくDpの値にそのままパスぶっ込むのでもokにしたかったとか？

2022/10/01(土) 23:28:38.05

ABC-Eは典型90の内容抑えれば結構戦えるレベルな気がするなあ
あとEDPC埋めとかね

2022/10/01(土) 23:28:53.28

入力が 3 × 10^5 コ以上あるときは、解法に関係なく少なくとも3秒以上になってるような気がする

2022/10/01(土) 23:31:02.64

2*10^5でもいい気がするけど、それだと速い言語で二重に走査するだけのO(N^2)回とかが通ったりすることがあるのかな

2022/10/01(土) 23:35:23.86

てか2*10^5でO(N^2)が2secで通るんなら、3*10^5のO(N^2)も4secあれば通りそう
あとは初心者が筋の悪い入力受け取りをしていたときにそこのオーバーヘッドで落ちるのを予防するとかかな

2022/10/01(土) 23:35:36.10

あ、dじゃなくcか

2022/10/01(土) 23:47:22.98

HEX

2022/10/02(日) 00:22:19.74

サンプルでWAを出すやつはこれを使え～
https://greasyfork.org/ja/scripts/433152-atcoder-easy-test-v2

2022/10/02(日) 01:34:13.68

なんか文句いってたら数え上げとXORの頻度が減った気がする。このあたりほんとアルゴリズムと関係ないので燃やすべし。

2022/10/02(日) 01:44:55.64

G問題がちょうど数え上げ+XORだったけど
組合せ論嫌うのもよくわからないね

2022/10/02(日) 01:45:17.65

あ、Fだった

2022/10/02(日) 01:55:00.10

>>934
数年前はこの類が毎週出てて違和感しかなかった、統計学でも数理最適化でも観測範囲内で組合せ論は二項係数くらいしか役に立ってないハズ

2022/10/02(日) 01:58:26.63

競プロは役に立たない

2022/10/02(日) 02:03:38.75

C、線形で解こうとしたんだけど、謎の1WAが出て困ってる
同じ1WAの人結構いたけど、みんな二分探索に切り替えてACしてる
https://ideone.com/yD7l3P
誰か教えて欲しい

2022/10/02(日) 02:06:44.15

「競プロは自分にとって離散数学パズルだ」ってりんごさんが言ってるし、整数論とかやるのと同じような立ち位置じゃないかなあ
そもそも初等組合せ論の考え方は初等確率論の基本なんだから、役に立たないというのも違うと思うしね
今回はGも数え上げ問題だったわけだけど、DP遷移部分について俺は幾何分布の考え方をイメージしたね

2022/10/02(日) 02:10:22.92

>>937
そう、別に個人的にはそんなに嫌いじゃないんだけど、好む層の魂の元が中学入試あたりで、自然数の各桁の和とか数学的に大した意味もないトピックがやたらドヤドヤしていたのがちょっと不快。プログラミング、アルゴリズム、情報科学というより、IQ高めの算数エリートの娯楽という感じ。

2022/10/02(日) 02:12:42.56

>>938
貯めてるsellが足りないときに貪欲に大きい方の本を売ってるけど、そこで順当にいけば読めるはずだった本売ってるんじゃない
一冊残しておいた方がいい場合とそうじゃない場合がある

2022/10/02(日) 02:17:08.77

>>940
魂の元が中学入試なのはまあそうって感じ
俺も算数パズルや離散数学よりも比較的連続最適化とかの方が好きっちゃ好きだから分からなくもない
まあでもCSでは離散数学は基礎教養だし、離散数学と中受算数は親和性高いよね

2022/10/02(日) 02:24:07.54

>>941
ありがとう ACできた
シミュレーションしながらsellを貯めていくのはダメで、sellをシミュレーションの前に計算するようにしたら通った

2022/10/02(日) 09:47:36.55

重複する本は∞巻目ということにしてからシミュレーションしてもうまくいくよ

2022/10/02(日) 11:05:00.45

小数点の精度はどうすりゃいいのか未だに分からん
興味がないねんな…

2022/10/02(日) 12:40:51.35

米田の新しい本を買いました。
PASTの公式本とどちらを先に読むか迷っています。

2022/10/02(日) 12:43:27.85

大槻のAtCoder入門という本は買わなくて正解でした。
図書館で借りて読めば十分な内容です。

2022/10/02(日) 14:48:02.40

>>944
確かにその方が実装綺麗にまとまるね

2022/10/02(日) 16:15:35.42

正解です

2022/10/02(日) 16:49:02.85

>>946
大槻さんの本で初級用の知識は入ったんだろうから問題集に移ることをオススメする。

2022/10/02(日) 16:56:26.21

>>950踏んだけど立てられなかったから誰か立ててくれ

2022/10/02(日) 17:44:45.80

次スレ
https://itest.5ch.net/mevius/test/read.cgi/tech/1664700238/l50

2022/10/02(日) 17:58:33.59

>>952
助かったありがとう

2022/10/02(日) 20:39:28.28

AHC、他の人の解法を参考に自分のを高速化しただけで60M超えてつらい
自分が高速化だと思ってコンテスト中やってたことが逆効果になってただけだったし

2022/10/02(日) 21:43:51.33

今ランキング見てるけど日本人多いんだね
まだまだこの国も未来がありそう（他人事）

2022/10/02(日) 22:03:53.70

こどふぉのランキング見てると中国がスゲェ

2022/10/02(日) 22:36:17.43

コンテスト中に呟いちゃいけないんだろうけど

1時間以上Aを考えてるがわからん

2022/10/02(日) 23:16:35.86

匿名の書き込みでも普通にやめた方がいい
そのぐらいなら大丈夫だと思うけど、それを見てまだラインがわからない人が勘違いしてさらに際どいことを書き込んでしまう危険性が

2022/10/02(日) 23:26:55.10

わかった。少なくともコンテスト終了後に呟くようにする

今日のAわからなかった。。
どうやっても10^10**5がmで割り切れるかを10^5回するし

ゾロ目数に規則性はあるっちゃあるけど、ないから
全くわからんかった

2022/10/02(日) 23:30:32.52

桁数大きい整数がある整数の倍数になるみたいな問題は類題があるから、それで早解き出来た人も結構いるかも

2022/10/02(日) 23:58:17.51

D、平衡二分探索木のsplit-mergeみたいなのでどうにかできないかなというのは自分も少し考えたけど、反転と組み合わせてそういう操作ってできるんだっけ

2022/10/03(月) 00:21:39.73

Aって出力形式変えたらN, M<=1e18 とかで解けたりしない?

2022/10/03(月) 00:31:17.62

上から全探索だとO(N)はかかっちゃいそう
(10^N - 1) % M自体はO(log(NM))で計算できるけど

2022/10/03(月) 00:36:30.02

N<=10^18,M<=10^5ならグラフ作ってBFSとかでいけそう

2022/10/03(月) 00:38:27.23

というか別にグラフ作る必要もないか
f(x) = (x-1)/10を作用させ続ければO(M)で解が見つかるか、不能判定ができるという話

2022/10/03(月) 00:58:09.84

解説に書いてあるくね？

2022/10/03(月) 01:04:26.18

というか10^(10^5)なんて数を扱う事あるのかｗｗｗ

https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1463346279
＞1m3に10個程度の原子（ほとんど水素）なら10^79となります。多めに見積もっても10^80は妥当なところだと思います。宇宙の半径130億光年であっても1桁増える程度です。

2022/10/03(月) 01:32:24.69

解説読んでなかったわサンクス本番(10^n-1)/9とEulerの定理方針が最初に見えたんだけど300点なことを思い出して引き返せた

2022/10/03(月) 01:35:16.73

累乗modの問題だしオイラーの定理で高速化できるか
頭固かったわ

2022/10/03(月) 03:00:23.71

atcoder.jp/contests/abc137/tasks/abc137_d

この問題の解答を作ったのですが、一部の入力例に対してしかパスしません。
どこにバグがあるか分かる人はいますか？

解答は以下です：
ideone.com/uZ1cUa

2022/10/03(月) 03:42:55.31

>>970
のバグが分かりました。

大槻の『AtCoder入門』ですが、結局、独力で解答を見ずにすべての問題を解けました。

2022/10/03(月) 03:45:23.53

>>949
ありがとうございました。
>>950
問題集ってPASTの問題集ですか？
米田の本はまだ見ていないのですが、売れ行きはいいですよね。

2022/10/03(月) 03:49:30.34

ideone.com/z97s8q

バグの修正を上のようにしました。

パスしなかった入力を見ることができれば、バグ修正もやりやすいでしょうが、
実際には見ることができません。

みなさんはどうやって、バグ修正していますか？

2022/10/03(月) 03:55:00.31

大槻の『AtCoder入門』ですが、普通の「アルゴリズムとデータ構造」の本に書いてあるようなことは
ほとんど書いていない変な本ですね。

競技プログラミングで「アルゴリズムとデータ構造」の知識をほとんど必要としない問題用の本ですね。

2022/10/03(月) 04:48:16.87

うんち

2022/10/03(月) 05:17:41.51

その本はプログラミング経験もアルゴリズムの学習経験も皆無に近い人(中高生も含め)がatcoderのC問題あたりを解けるようにして、本当に簡単なアルゴリズムを触れるようにするぐらいのレベルのもの
not for youだな
というかそもそも大多数の競プロ本はアルゴリズムとデータ構造の教科書を志向していないから

2022/10/03(月) 05:24:09.62

デバッグは自分でテストケース作ってやるのがいい
実は過去コンテストのテストケースを見に行くことはできるが、競プロコンテスト本番のデバッグ力を鍛えることができないからオススメしない

2022/10/03(月) 08:54:28.68

>>976-977
ありがとうございます。

過去問の入力データを見に行けるんですね。
解答を見るのと、解答を見ずに入力データは見るというのだったら、後者のほうが勉強になると思います。
独力で正解を作るのがベストだとは思いますが。

2022/10/03(月) 08:55:09.57

テストケースを作るのは非常に大変だと思います。

2022/10/03(月) 10:07:34.75

乱数で入力を発生させ、計算量的に悪いけど簡単に思いつけて実装できる部分解法で正しい出力を出せばいいわけで、そんなハードル高いものじゃないぞ
上位層はコンテスト中にちゃちゃっとやってると思う

2022/10/03(月) 10:14:59.33

独力で頑張ってるようで応援してるよ
典型的なアルゴリズムも自分で思いつけるようなものなのか興味ある

2022/10/03(月) 19:13:46.77

>>980-981
ありがとうございました。

>>980
「計算量的に悪いけど簡単に思いつけて実装できる部分解法」
これは思いつきませんでした。ありがとうございました。

『競技プログラミングの鉄則』を今読んでいて第2章の累積和の途中まで読み終わりました。
確かにレベル的にはそれほど高くない本だとは思いますが、勉強になったことがありました。
・問題で添字が1始まりの問題ではプログラムでもそれに合わせて1始まりにすると分かりやすくなる。
・使用メモリ量については寛大なので無駄遣いしても全く構わない。
・1つのfor文でまとめて処理できる場合でも、複数のfor文に分ける（それでもオーダーは変わらない）と、分かりやすくなることがある。
・
for (int i = 0; i < N; ++i) {
□□cin >> A >> B;
□□ここに処理を書く。
}

とできる場合でも、

for (int i = 0; i < N; ++i) {
□□cin >> A[i] >> B[i];
}

とまずすべての入力を受け取ってしまってから、後で処理を書いても良い。

2022/10/03(月) 20:26:59.27

https://twitter.com/intent/favorite?tweet_id=1516784253656506369
@rui314
さん
あれはSAPIXとか鉄緑会と同じカルチャーだと思う。
https://twitter.com/5chan_nel (5ch newer account)