競技プログラミング総合スレ 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/11/02(水) 14:13:37.34

組合せ最適化第6版の和訳が出るぜ

2022/11/02(水) 18:02:49.90

https://github.com/yosupo06/library-checker-problems/issues/895
ガウス整数環での素因数分解
A+Biとしたときに|A|,|B| <= 10^9でも十分高速でできる
数論の知識が豊富なら再発明は困難でもなさそう、ABC-Gぐらいの問題っぽい？ARC/AGCタイプではない
結構知識を使うので考える過程でいろいろ勉強になった

2022/11/02(水) 18:08:47.53

コルテ和訳助かると思いつつも、17600円となかなか高い
第2版が値下がりしたりしないかな

2022/11/02(水) 19:34:08.80

コルテの本は競技プログラミングに役に立ちますか？

2022/11/02(水) 19:34:56.79

役に立ちます

2022/11/02(水) 19:39:08.78

>>368
ありがとうございます。
高度な本で競技プログラミングにも役に立つというのはいいですね。
高度な内容を理解するのが主目的で、おまけとして競技プログラミングも強くなる。

2022/11/02(水) 21:32:43.80

そうです

2022/11/03(木) 17:08:06.46

昔のARCの問題は正直今のARCの練習には微妙な気がするな
何が一番近いんだ

2022/11/04(金) 10:20:19.80

数ヶ月触って思ったけど競プロって実際の開発には結びつかんね
まぁ割りと勉強的には面白いからいいけど

2022/11/04(金) 10:56:39.54

俺はライブラリとか便利ツール作る過程で色々学んだけど元々開発経験ある人だと逆にそういうことはないか

2022/11/05(土) 00:18:45.61

ARCも昔（3年程度前）の問題やってるとdiff一色分ぐらい今より高く評価されている印象だから、昔の問題解くんなら自分のレート+400～+800ぐらいの問題解いてるとちょうどいい思考練習になると思う

2022/11/05(土) 00:41:37.71

開発って点だと自動judgeツールとか、ライブラリ整備とかは一応スキルアップにつながりそう
さらに突き詰めて、競プロ用にトランスパイラ作ってる人もたまに見る気がする
けど、こういう作業って決定的な競プロの実力向上につながるわけではないので、なかなか微妙な立ち位置だよね
まあ開発方面の技術につながる楽しみ方も一応あるということで

2022/11/05(土) 11:34:34.69

Qiitaに珍しくいい記事があったとしてその人を雇いたいと思えるか？
競プロのレートなんてそれ以下なんだな

2022/11/05(土) 14:54:25.86

>>374
diffの基準が違うと感じることはもちろんあるが、もっと根本的に問題の傾向変わってないか？
writerの差か

2022/11/05(土) 20:59:06.56

さあ、緑をめざすぞ
茶色到達したってことは4完以外だとレート下がるんだろうか

2022/11/05(土) 22:41:58.78

Qiitaで記事書いてるのは社内ドキュメントとか残してくれそうで歓迎

2022/11/05(土) 22:42:19.35

いや、一個前の順列とか知らんし、Dはiが2,3番めだと思ってた。酷いｗｗ
下手したら２完だたｗｗｗ
検索しても全然出てこないからB問題まで解ければ十分だの

2022/11/05(土) 22:43:11.47

Cムズすぎる🥲

2022/11/05(土) 22:43:16.24

久しぶりに順調に6完できた…

2022/11/05(土) 22:45:59.83

C問題は、C++ならライブラリ使えるから簡単すぎるけど、ライブラリ使わない前提とすると、C問題にしてはかなり難しいような

2022/11/05(土) 22:47:11.30

クソインフレおもんねーわ
結局ガキの頃から脳みそ鍛えてないとｃとかで時間とけて終わるな
ワイのレートは頭打ちや

2022/11/05(土) 22:49:20.41

F問題方針合ってたのにBITも有理数用のライブラリも作ってないせいで実装間に合わなかったけどやっぱり作っておくべきか
三連続で有理数ライブラリ使える問題出題されてるし

2022/11/05(土) 22:53:52.95

>>385
BITと逆元使うだけじゃん
そんなもん理屈わかってれば実装簡単なのに何を言い訳してるのやら

2022/11/05(土) 22:57:52.72

この難易度4完で3000位以下って…
しんどいよぉ

2022/11/05(土) 23:08:34.55

Cわりと簡単に解けたけど証明できなかったから提出するとき一番ドキドキしたw

2022/11/05(土) 23:12:16.55

これ意外と非自明な事実かもしれないから書くけど、有理数をmodとって整数で表せって問題は徹頭徹尾有理数を使わないで正しい答えを出せる

2022/11/05(土) 23:14:04.30

一応、素数modであることが必要かな？

2022/11/05(土) 23:16:02.54

>>383
ライブラリなしなら結構頭使う方かもね
ARC-Aとかにありそう
ライブラリ前提の問題として配置したんだとするとちょっと微妙な気がするなあ

2022/11/05(土) 23:17:34.26

>>391
お前らC++使えよ？っていうちょくからのお達しだろうな

2022/11/05(土) 23:24:55.55

>>386
その二つ自体はそうなんだけど、分母はK^2になるから分子の情報だけ持てば良いっていうのを見落としてたせいで有理数の四則演算をしようとして実装が大変なことになったんだよね
初心者ですまん

2022/11/05(土) 23:24:57.65

chokudaiはC#やkotlinも推してるからC++一強がいいとは思ってなさそうだけど、現実的にC++前提の作問が多くなるのはしょうがないところがある
他言語使いも、競プロerがC++でよくやる処理と同等のことができるようなものを用意しておいた方がいいかなあ
逆に、遠慮なく多倍長整数がバンバン出てくるような制約にしていいと思ってるんだけどね

2022/11/05(土) 23:35:04.99

30半ばのおっさんなんだけど初めて数ヶ月、C問題が解けたことが今まで数えるほどしかない(´・ω・｀)
お前ら天才すぎだろ

2022/11/05(土) 23:38:00.58

こんなん安倍晋三でも全完出来るだろ

2022/11/05(土) 23:38:56.42

全完9人しかおらんやないかーい(´・ω・`)

2022/11/05(土) 23:39:37.36

最近c問題むずいね
以前はdiff 200くらいが目安いうてた気がするけど

2022/11/05(土) 23:41:52.73

紙に(1,2,3,4,5)の順列でも書き出してにらんでれば規則性がわかるだろ

2022/11/05(土) 23:46:13.55

Cは普通にむずいと思うよ
進学校で高校数学まともに勉強してた層の中の上の方がコミュニティ作ってるから基準歪んでるけど
競技と言いながらあまり相対評価に囚われちゃいけないタイプの娯楽

2022/11/05(土) 23:46:43.80

まあサンプルが親切だったね
出力例2を眺めてたらわかった

2022/11/05(土) 23:47:47.38

というかコドフォdiv2のA,Bあたりによくある実験してたら規則性が見えてくるやつだからまあ妥当なんじゃないですかね(証明できるとは言ってない)

2022/11/05(土) 23:52:24.78

Gは形式的べき級数で楽しようとして負の二項定理？っぽいところで詰まってしまったから、これも覚えておこう

2022/11/05(土) 23:57:57.35

>>394
たしかに1000ビットとかくらいの整数の演算を要求してたまにはC++erを殺してほしい

2022/11/06(日) 00:38:46.41

>>395
30歳すぎたら酒飲んだりなんか食べながら気軽にやるのが吉

2022/11/06(日) 01:50:28.89

今回のE問題みたいなやつで、解説でDFSじゃなくてBFSが書かれてるのなんで？
最短経路が不要ならDFSでいいと思うんだけど

2022/11/06(日) 01:54:17.29

競プロ力ってWebとかシステムってよりかはゲームとかの方向な気がする。

2022/11/06(日) 10:05:08.85

>>406

2022/11/06(日) 10:53:13.10

DFSでもいいと思うよ
人によるけど、BFSの方が実装しやすいだけ
Pythonなど一部の言語だと、再設定しない限りDFSでは再帰上限でREになるから解説に書きづらいというのもある

2022/11/06(日) 11:08:07.55

本当にどっちでもいいんだけど、おれもこういうときはなんとなくBFSで実装するようになってきたな
そもそも競プロの探索問題だと、DFSよりBFSを利用することのほうが多くて、BFSが手癖になってきたかな

2022/11/06(日) 12:52:40.41

昨日のEx、F2行列操作の高速化か
こういう細々としたテク、ライブラリ化サボっちゃうしコンテスト中に思い出せる瞬発力もないんだよなあ

2022/11/06(日) 14:27:17.74

ARC/AGCが補充されないけど、来月にはさすがにAGC生やすのかな？
赤が競えないサイトってAtCoderの思想的にまずいような
ARCは今年それなりに多かったし、息切れされても困るから無理に生やさなくてもいいと思うけど（そもそも今どういう内部状況か全然知らんけど）

2022/11/06(日) 14:32:15.66

DFSのが書きやすいと思うけど、確かに再帰って言語によって計算コストに癖があるからDFSよりもBFSの方が安定なのかもね
10^6のサイズのグリッドで2次元配列使うから、遅い言語だとやや定数倍気をつけないといけないタイプ

2022/11/06(日) 14:45:26.72

BFSはキューを使います。
DFSは再帰を使わない場合スタックを使います。
再帰を使わないとして、BFSのほうがDFSよりも実装が簡単ですか？

2022/11/06(日) 14:49:15.37

同じです

2022/11/06(日) 15:12:24.54

今回みたいにただ連結判定するだけならBFSもDFSも同じようなもんだけど、木DPでやるような再帰を活かした+αの処理を非再帰化してスタックで実現しようとするとややめんどい

2022/11/06(日) 16:02:50.42

JavaだとDequeとQueueはあるがStackは古の非推奨クラスなのでBFSの方が楽

2022/11/06(日) 16:24:36.10

別解なんていくらでもあるんだから、BFSとDFSの差くらいで
「なんでこっちの解法じゃないの？」なんて悩んでたらすごく楽しいことになるぞ！

2022/11/06(日) 16:46:02.52

Dequeはスタックとしても使えるのでは

2022/11/06(日) 19:54:28.41

どっちみちお尻から取ってくるか前から取ってくるかの違いじゃろい

2022/11/07(月) 22:41:09.69

今日本語圏で一番知見が集積しているのってLibrary Checkerかな
英語圏、ロシア語圏、中国語圏に似たようなものはあるんだろうか

2022/11/07(月) 23:20:15.29

中国語やロシア語には競プロで使うやたらマニアックなアルゴリズムをまとめたページあるよ

2022/11/08(火) 16:11:47.32

中国の方はまとめた辞典みたいなサイトがあったよな
前スレにあった気がする
ロシアの方は知らないんだけど、どんなやつ？

2022/11/08(火) 16:12:34.40

しかし、赤diffとか解いてる感じでもARCは昔の方が簡単な気しかしないんだが、割と違う意見あるんだな

2022/11/09(水) 11:07:25.04

赤になりやすくなったという文脈であれば問題の難易度とはまた別の話だけどな

2022/11/09(水) 14:15:51.41

あるdiff帯に限定して問題を抽出するとすれば、その難易度はそれぞれの問題の出題時期におけるそのレート帯への到達難易度と大体相関するやろ

2022/11/09(水) 15:00:23.18

時代とともに同じdiff帯の問題の難易度が徐々に上がるのは当たり前で、だからといってある色への到達難易度が上がるわけではない、環境だって変わってるんだから

2022/11/09(水) 15:23:24.57

それは同じ傾向の典型問題がずっと出題され続けている場合に適用できる話だが、ARCは傾向が変わっているわけでそうとも言えない
ARCの昔の問題は今となっては典型となっているので、簡単に感じる、という話なら分かるんだが、どうも昔の方がアドホックで難しいと考えている人がいるのが自分の感覚だと意外だったってことが元々言いたかったことだな

2022/11/09(水) 15:48:45.39

まあ、到達難易度に関しては、最大限リソースを競プロにぶち込んだときにその色になれる確率の話か、その色になるための平均的なコストの話か、でも全然違うから、その辺り明示しないと無限にややこしくなりそうだな
典型性が高まってるんであれば、前者の難易度は下がってるかもな

2022/11/09(水) 16:48:50.58

> 昔の方がアドホックで難しいと考えている人がいる

これは俺も同意できないけどソース何？まあ言いたくなければ別にいいけど

2022/11/10(木) 21:53:35.79

ICPC終わったね
MIT強いな
PurdueとSwarthmoreもそれなりの順位につけてるし、アメリカ結構来てる？

2022/11/10(木) 21:57:56.30

ARCが昔と今でアドホックさに変化があるという印象はなくて、これもどちらかというとwriter依存な気がする
少し前のmaroon回はアドホックだったようなイメージ

2022/11/10(木) 23:05:12.88

というかカーネギーメロン大学も強いな

2022/11/10(木) 23:13:57.97

ARCは難易度もアドホックさも時期によってばらばらなイメージある

2022/11/11(金) 00:03:33.94

MITってMYDのワンマンチームかと思ってたから意外や

2022/11/11(金) 01:28:27.41

Benqが次出るときどういうチームになるのか気になるわ

2022/11/11(金) 11:36:15.83

CTFを勉強しようと以前アカウント作ったんだけど、難し過ぎてpicoCTFからやってたら最初のサイトを忘れた。。。
アカウント申請にもサイトを解析しないとダメでそれはクリアしてアカウント作ったんだけどどこか分かる？

2022/11/11(金) 18:24:09.39

>>437
HackTheBoxでした。
スレ汚しすいません。

2022/11/11(金) 19:04:07.17

数列AのLCMを10^9+7のmodで取る問題が有るんだけど、
答えが合わないのは
gcd(l, Ai)とgcd(l % 10^9+7, Ai)は異なるということ？

って自分で確かめれるか。
家帰ったら確かめよ

2022/11/11(金) 19:24:41.27

じゃあレスすんな

2022/11/11(金) 19:39:51.72

ツッコミどころが多すぎるけど例えばl=10^9+8の場合とかを考えてみればすぐ分かるしそのレベルだと高校数学の復習をしてからの方が成長出来そう

2022/11/11(金) 22:17:47.19

gcd(1,2)=1
gcd(1+10^9+7,2)=2

2022/11/11(金) 22:20:21.87

しかし、その部分でひっかけ？をするのと多倍長整数扱わせたい以外の意図を感じない珍しい問題だ

2022/11/11(金) 22:24:57.86

整数をZ/pZで扱うのは一種のハッシュ化だけど、gcdやlcmみたいな数論的性質がうまいこと保存されるハッシュ化ってなんかあるんかね

2022/11/11(金) 22:49:25.23

ふと思ったんだけど、競技プログラミングってすぐに結果が出るじゃん。
だから、出来た!!って達成感がすぐに味わえる。
それに対して、何かをつくるってすごく時間かかるから
達成感を感じるまでにすごく時間がかかる。
FFS理論の拡散性/保存性と関係ありそうだなって感じた。
FFS理論については俺もよくわかんないんで説明しないけど
競技プログラミング好きは拡散性が高く
何かをコツコツ作るのが好きな人は保全性が高い見ないな。

2022/11/11(金) 23:06:55.29

それはあるだろうね
FFS理論はよく知らないけど、自分は刺激がないと興味関心の対象がすぐ移るから、結果やフィードバックがすぐ返ってくる競プロが性にあう

2022/11/11(金) 23:35:15.66

>>443
というかこれおそらくだけどN<=10^5, A_i<=10^9とかで素因数分解させて素数ごとに指数max取らせるのが想定解みたいな問題だろうから、なんかすごい的外れなこと言ってたわ

2022/11/11(金) 23:40:03.89

レベル感的にはA_i<=10^5の方がそれっぽいか

2022/11/12(土) 19:57:29.12

競技プログラミングの鉄則のB07の問題が解けません。
これがなぜ不正解なのかわかる方いらっしゃいますか(ヘッダ省略してます）？
int main()
{
int T; // 閉店時刻、出力行数
int N; // 従業員の人数

cin >> T >> N;

// 各従業員の出勤時刻を入力して、
// 時刻毎の人数差分表を作成する。
int L,R; // 出勤時刻、退勤時刻
int diffList[500009]; // 前の時刻との人数差分リスト
for(int i = 0; i < N; i++) {
cin >> L >> R;
// 出勤時刻には人数が１人増える
diffList[L]++;
// 退勤時には人数が１人減る
diffList[R]--;
}
// 各時刻の働いている人合計を出力する
int total = 0;
for(int i = 0; i < T; i++) {
total += diffList[i];
cout << total << endl;
}
return 0;
}

2022/11/12(土) 20:20:29.60

>>449
配列初期化してなくね
真面目に初期化するかグローバルに置くか static つけるか std::vector 使う（オススメ）か

2022/11/12(土) 20:31:37.25

>>450
配列のみグローバル領域に置いたら正解になりました！！
ありがとうございました！！

2022/11/12(土) 22:41:09.26

5完
F,G無理無理無理

2022/11/12(土) 22:41:38.34

DのWAが１時間以上もとれない、コンテスト難しくなりすぎ・・・

2022/11/12(土) 22:41:46.87

またCとけんかった
自分ではいけたと思ったのに(´・ω・｀)

2022/11/12(土) 22:43:20.71

EとFGで崖ある回キツいわ
Dでバグって2WAした時点で追いつける可能性が大幅に減って困ってた

2022/11/12(土) 22:44:23.30

Aの傾向の変わり具合もそうだけど今日のCって少し前ならDにあってもおかしくない気がするしインフレしてるんだな

2022/11/12(土) 22:44:29.50

競プロ初心者だが、D問題とけなかった。
長くなるが次のコードの何がいけないのか教えてほしい

2022/11/12(土) 22:46:35.73

2回に分ける
n, m = list(map(int, input().split(" ")))
t = {}
origin = list(map(int, input().split(" ")))
sums = sum(origin)
numbers = set()
for i in origin:
if i in t:
t[i] += 1
else:
t[i] = 1
numbers.add(i)
numbers = list(numbers)
numbers.sort()
numbers += numbers
start = 0
goal = -1
now_max = -1
now_sums = 0
last = None

2022/11/12(土) 22:46:51.30

while True:
goal += 1
if goal >= len(numbers):
break
if start is not None and goal - start + 1 > n:
break
mod_m = numbers[goal] % m
if last is None:
start = goal
now_sums = mod_m * t[mod_m]
last = mod_m
elif (last + 1) % m != mod_m:
last = mod_m
now_max = max(now_sums, now_max)
start = goal
now_sums = mod_m * t[mod_m]
else:
now_sums += mod_m * t[mod_m]
last = mod_m
now_max = max(now_sums, now_max)
print(sums - now_max)

2022/11/12(土) 22:55:47.75

見づらいですね。
画像にしました。
https://imgur.com/a/Jy5RJoL

2022/11/12(土) 22:58:40.53

アカウント知られることに抵抗がないなら提出ページのリンク貼った方が見やすいと思うよ
こんな感じに
https://atcoder.jp/contests/abc277/submissions/36407734

2022/11/12(土) 23:01:52.30

>>461
ですね。サンクス
https://atcoder.jp/contests/abc277/submissions/36450032
こちらになります。

2022/11/12(土) 23:11:22.38

>>462
コード全然見てないから見当違いかもしれないけど、自分も殆ど同じテストケースでWAが出てソート済みの数列が全て差分1以内で連続してるパターン(0 1 2 3 4的な)でのミスが原因だったからこのパターンにも対応出来るようにしたらACになるかもしれない