競技プログラミング総合スレ 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/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になるかもしれない

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

>>460
0からM-1が全部埋まってるときにバグる
あとnow_max = max(now_sums, now_max)のインデントがズレて更新がおこなわれていないとか？

2022/11/12(土) 23:16:22.82

cもdも座圧unionfind で芸のない出題だなと思いました

2022/11/12(土) 23:18:14.12

あーDはunionfindでもできるね
そっちの方が実装方針としては楽かも

2022/11/12(土) 23:25:56.09

ABC-Eってかなりの頻度で頂点を増やして最短経路問題を解く形の問題が出てる気がするね

2022/11/12(土) 23:28:46.84

>>463-464
サンクス

ああああ・・・なるほど

if start is not None and goal - start + 1 > n:
⇒
if start is not None and goal - start + 1 > m:
にしたら通った。。。悔しい。。

2022/11/12(土) 23:30:43.24

>>464
よくみたらnow_max = max(now_sums, now_max)の更新はloop中でちゃんと行われてるね
失礼

2022/11/12(土) 23:32:16.43

33にもなってこんな連投してんのか

2022/11/12(土) 23:32:41.23

D問題、公式解説でO(NlogN)で実行できるって書いてたけど
自分の実装もそうだけどO(N)でできるんじゃないのかな。

2022/11/12(土) 23:33:21.48

>>470
IT初心者で夢中になってるので、すみません。。

2022/11/12(土) 23:33:43.49

2-SATとproject selectionってやっぱ似てるよなと最近思う

2022/11/12(土) 23:38:09.22

座圧でソートが必要なときと必要じゃないときがあるけど、そこがボトルネックで死ぬことは少ないので、あまり気にされるタイミングがない

2022/11/12(土) 23:42:34.37

むしろジジイもキッズも連投しまくれ

2022/11/12(土) 23:54:16.97

Ex、ARCで中盤で出てもおかしくない問題がちょくちょくある気がするけど、ABCで出ちゃったからARCでは一年ぐらいは出なそうだな感もある

2022/11/13(日) 00:09:53.81

Fが水色くらいになるようにしてほしいですね

2022/11/13(日) 00:17:24.95

Fは青ぐらいがよくない？

2022/11/13(日) 00:23:17.33

EとFを同じ配点にするなら、同じdiffを目指してほしい

2022/11/13(日) 00:36:57.60

それも一理あるけど、GとExは同配点ながら明らかに難易度差があるような作りになってるし、配点と難易度を一致させることがマストとは考えられていないと思う
そもそも広く競プロを見れば点数がなくて完数で評価するコンテストもあるし
個人的にはB～Gで灰から黄まで一色ずつ出現するぐらいが丁度いいABCかなあと思っている

2022/11/13(日) 02:01:31.35

DE緑でFG橙は流石に崖が過ぎる

2022/11/13(日) 08:36:37.58

Fは青黄でも十分に解ける問題だった

2022/11/13(日) 13:29:16.33

Fは個々のステップ自体は難しくないから素直にやれば青でもできるものだと思うが、橙diff出た要因はなんだろうな
TLが若干厳しかったのが効いてるんだろうか

2022/11/13(日) 13:45:12.57

自分はすぬけ君の地下鉄旅行を思い出すのに時間がかかって間に合わなかった

2022/11/13(日) 14:19:52.10

確かにハブ的なものを作って辺の数のオーダーを落とすという典型は微妙に有名じゃないのか

2022/11/13(日) 16:09:21.76

Cの嘘解法、これを思い付くほうが想定解思い付くよりずっと難しいだろみたいなところがあるな

2022/11/13(日) 16:10:36.90

Cの嘘解法、これを思い付くほうが想定解思い付くよりずっと難しいだろみたいなところがあるな

2022/11/16(水) 02:30:47.15

httf提出したあ

2022/11/17(木) 19:51:39.15

AGC 生えてるけど冷える気しかしない

2022/11/17(木) 22:29:51.89

ARCも入ってるし、ICPC終わってエンジンかかってきたな