競技プログラミング総合スレ 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/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終わってエンジンかかってきたな

2022/11/17(木) 22:32:50.54

AGCの告知2週間前とかにされるんだな

2022/11/17(木) 22:56:08.64

今年で3回目のAGCか
だいぶ開催数減ってきちゃったね

2022/11/17(木) 23:01:38.63

一時的なもので外国人に協力してもらえばなんとかなるのか、本当に問題が枯渇してこれからどんどんAGC作問が厳しくなっていくのか気になるところ

2022/11/17(木) 23:11:25.50

Agcあとは年末に2回やれば及第点にはなるか

2022/11/18(金) 04:56:12.51

AGCの問題傾向よく分からん

2022/11/18(金) 15:45:59.95

こどふぉdiv.1ははなんだかんだ生えてるがインドは生えなくなったしどこも問題枯渇してるんだろう

2022/11/19(土) 15:26:42.45

opencupとかどういう質の問題が出てくるんだろうね
漏れ出てくる話を見る限り、割と知識バンバン使いそうな印象でAGC的な感じじゃなさそうだけど
AGC的傾向が唯一のものではなくて、そこで問題を食い合ってたら大変だなと

2022/11/19(土) 16:00:48.74

うんち！

2022/11/19(土) 16:13:20.32

Dまでにダイクストラを使った問題を2年くらい見てない気がする。やるだけになりがちなので出ない。

2022/11/19(土) 16:55:11.41

そりゃ直球でダイクストラをやる問題なんて中々出ないでしょ　ダイクストラに一手間加えたものは結構DEくらいで見かける気がするけど

2022/11/19(土) 17:01:35.33

どのコンテストの話なのかambiguousだ

2022/11/19(土) 21:53:02.57

opencupはかなりあらゆる問題が出るし難易度が高すぎて質とかよくわからん

2022/11/19(土) 22:40:57.03

E問題
やり方思いついたけど時間間に合わんかった
マジで悔しい

2022/11/19(土) 22:42:42.99

同じく。Dまでが難しく時間かかるから解けそうでも足りない。
問題数増やすなら通りやすくしてほしい。

2022/11/19(土) 22:42:46.42

G無理すぎ

2022/11/19(土) 22:45:13.42

6完
G真ん中先にとって対称に取れればいいけどそうじゃないときが分からん

2022/11/19(土) 22:47:01.65

B問題を読み間違えたのもあるけど一時間使ってしまった😭
Cが定型問題っぽかったのに残念すぎる…

2022/11/19(土) 22:47:25.31

ちなみに俺が考えたE問題の解き方として

横移動するときに、移動前の列と移動後の列の差分を計算して行くっていうやり方なんだけど

これじゃアウトなんだろうか。300っていう制約があったから計算量的に足りる気がしたのだが

2022/11/19(土) 22:47:36.14

Grundy数と真似っ子の複合でなかなか教育的な問題

2022/11/19(土) 22:49:01.60

https://imgur.com/a/Q2WBP15

Dまではノーミスでできた。
緑に近づけていたらいいな

2022/11/19(土) 22:51:20.76

Fまではだいぶ素直でABCらしい回だった気がする　
問題文やたら長かったけど

2022/11/19(土) 22:57:02.19

EとFの難易度が釣り合ってたのも久しぶりな気がするな
数ヶ月前のD辺りに似たような問題あった気がするし逆に置かれてたらFの方が解かれてそう

2022/11/19(土) 23:06:18.86

>>508
ちゃんと実装すればいけるんじゃない？
計算量増やさないようにする縦移動が少しめんどくさいので、二次元累積和の方が実装は簡単な気がする

2022/11/19(土) 23:06:20.86

ってか競技プロって実務で役立つ説ってどうなんでしょう
atCoder初めてはや３ヶ月だけど、
IT業界２年目で実務で、皆が重いって言ってる内容とか全然重く感じない

競プロによる基礎体力があるからでしょうか（願望）

2022/11/19(土) 23:07:43.19

Fは素直だったね
確かにABC-Fはたまにかなり素直なDPが来る印象

2022/11/19(土) 23:09:38.17

プレッシャーの中で頭使いながら速くコード書く練習してるから基礎体力をつける的な意味では十分役に立つんじゃないの？って思うね

2022/11/19(土) 23:10:56.74

引退します
https://i.imgur.com/fZw65ga.png

2022/11/19(土) 23:13:26.30

だよね
ただ、それ以外のサーバー知識とかlinux周りとかはやっぱり経験者の方が強いわ

でも、10年以上IT業界にいる人よりもSQLをかけたりするんだよね

こういうのって、職人の世界で言ういわば力持ちで、広く浅い（？）知識もってる人より偉くなりにくいのかね？どうなんだろう

2022/11/19(土) 23:17:05.43

>>514
BからC問題くらいまで解けるようになる価値はめちゃ高くて最も役に立つ帯域だと思う

2022/11/19(土) 23:19:13.45

>>514
おれも業務経験ガッツリ積んでから競プロやってるけど、競プロの知識が業務に役立つことほとんどないよ

例えばデータベースでは全レコード数をNとして、検索速度はO(logN)やO(1)らへんに落とし込むのがもともと当たり前だし、役立った気はしない
強いていうなら実装から見積もりができるようになったから、計算量やばいコードの見分けがつきやすくなったぐらいだけど、そんなことが役に立つ機会ほとんどない
なぜかというとオンメモリにたくさんデータを入れることがないからだろうな。1台の計算機でがんばるよりも、どうやってスケーラブルにするかってのが重要だし

アクションゲームのフロントエンド側とかだったら、オンメモリでいろんな幾何学的処理するからもっと役に立ちそう

どの問題が重いって言われてるのか知らんけど灰や茶が重いとか言ってもアテにならんし、ABCは他の競プロコンテストと比較すると圧倒的に実装が軽いしどういうことだろうな？

2022/11/19(土) 23:23:26.36

>>508
自分はそれで通したよ

2022/11/19(土) 23:23:39.51

>>520
514だけど、重いって言ってるのは実務でだよ

かなり細かい場合わけが必要だから時間がかかるっていう実装を頼まれて、3日とか想定してたのを30分くらいで終わらせた

スケーラブルにするのも大事だけど、細かい部分を見る目は大事なんじゃないかね？って思う時はある

今elasticsearch触ってるけど、細かいスコア計算の部分とかそういうのを把握するっていう意味で理数的な競プロの考え方はすごく役に立ってると感じる

2022/11/19(土) 23:24:31.32

>>521
やめろおおおおおおおおお

俺のやり方が間違ってたって思えれば時間間に合わなくてもあきえあめがつくのに。。
やっぱりそうか。。。
悔しい

2022/11/19(土) 23:25:42.08

基本的にはオンラインパズルゲームでしかないから競プロが実生活に役立ったら美味しいくらいに捉えて楽しむのが賢明で、役に立つことを期待して取り組むもんでもないってずっと言われてると思う
まあABC-B、Cくらいの指示に従って愚直にコードを書く問題は業プロの基礎体力に直結する気がするからスラスラ解けるのと解けないのでは全然違う気もするけどね

2022/11/19(土) 23:27:48.07

>>522
たしかにソロバン経験があると暗算が早くなるのと似たような感じで
競プロやってれば数学的/論理的な思考はだいぶ早くなるだろうね

2022/11/19(土) 23:30:38.86

>>524
業プロにワロタ
いやさ、今メンバーをプロジェクトにアサインする問題が会社にあって、

該当メンバーがコードの読み書きが全然できないって客先から怒られてたりするんだよね

だから、競技プログラミングのA問題を解けるかどうかで判定してみるのはどうだろうっていうことを提案しようと考えてた
解けるかどうかっていうよりもそれを解くときの姿勢とか、調べる気持ちとかがあるかどうかってそこで見極めることができる気がする

B問題でもいい気はするけどB問題以降はガチ勢っぽいイメージ俺は持ってるからメンバーのアサイン判定には不向きかなって

2022/11/19(土) 23:31:26.81

ABC-Cあたりがごく普通の業務で出て来る可能性があり、なおかつかなり個人差がある領域だと思ってるけど、そこが速いと捗る
その部分が進捗のボトルネックになってしまう人もいるので

2022/11/19(土) 23:33:39.83

自分は競プロできないからどうのみたいな考え方はそんなに好きじゃないけど、さすがにプロのプログラマーだったらABC-Aは解いてほしいかなあ

2022/11/19(土) 23:34:14.93

>>526
なんか普通にやたらレベルが低そうで笑えないな
とりあえず学歴フィルターしたら？

2022/11/19(土) 23:37:35.70

思うんだけど、
競プロって計算量オーダー云々っていうよりも

データの構造とかハッシュテーブル的なものをちゃんと理解しているかどうかだと思う
そういうあたりを正確に理解してれば、計算量なんて悪いパターンになることを知ってれ場何とでも対策できる

プログラム書く上においていろいろな構造を正確に頭の中で描けるかっていうことを図るいみで競プロは非常に有効だと考えてる

2022/11/19(土) 23:38:35.53

愚直に(全探索とかをして)コードを書いても制限を超過しないっていう点でABC-B(と一部のC)くらいまでは確実に業務に直結すると思うよ
たまにプログラミング関係なしで簡単な算数・数学っぽい問題も混じってるけど

2022/11/19(土) 23:39:20.45

>>529
俺自身が29歳までトラック運転手の高卒だし、学歴フィルターはできない
アサインチームがOJT目的であまりにもポンポン案件入れてしまうので、業務チームが火を噴いていることは事実
だから、A問題を解いてみてが一番いいと思う

2022/11/19(土) 23:39:40.71

>>530
そうだね、情報系学科を卒業してないなら、教養としてせめて競プロ経験しててくれ、って感じはあるかもしれない

2022/11/19(土) 23:46:23.51

頭の中で、配列、ハッシュテーブル、stack、queueのイメージぐらいできてもいいかもね
std::setは平衡二分探索木を忠実にイメージしようとか考えだすとめんどくさいけど

2022/11/19(土) 23:49:47.51

>>531
算数・数学も最低限の教養として必要だと思う

そもそもにして式を立てられないんだったら数字を使う業務にアサインできないと思うし、統計的な考え方ができるかできないかも大事だと思う
競プロで出てくる数学ってD問題までに限って言えば高くても高校レベルだから、漸化式を立てるとかそれくらいはやってほしいって思う

2022/11/19(土) 23:52:10.43

>>513
二次元累積和

覚えやす

2022/11/20(日) 00:02:59.31

Ex、解けてるの一人だけか
相変わらずNyaanさんの解説は読み応えある

2022/11/20(日) 00:36:46.56

>>517
サンプルを試しましょう…

2022/11/20(日) 01:05:14.62

A, Bが解けねえ奴には流石に知的労働は即座に辞めろと言わざるを得ない(´・ω・`)

2022/11/20(日) 01:10:14.63

>>532
ABCコンテストで試すより、それだったらPASTかPaizaのほうがいいかもね

2022/11/20(日) 02:11:59.36

Wとw間違えて3分ぐらい無駄にしたんだけどおすすめのフォントない？

2022/11/20(日) 02:43:28.01

problems見たらEが緑下ってコンテストのレベル上がった気がする。灰色コーダーは普通に優秀。

2022/11/20(日) 02:48:57.41

なわけねーだろハゲ