競技プログラミングにハマるプログラマのスレ 22

**仕様書無しさん** · 2019/12/02(月) 20:50:54.40

プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)やCTFなどを楽しんでる競技プログラマ(競プロer)の雑談スレ
競プロイベントや競プロ問題や有名競プロerや競プロでよく使うアルゴリズム等について語りあったり、競プロ関連の質問相談なんでもおｋ
競プロ初心者でググっても解説読んでも分からないことがあったらスレの競プロの先輩方に訊いてみるのも手だよ(分かりやすい解説サイトとか書籍とか教えてくれるかもしれないよ)
次スレは>>950

# オンラインジャッジ・コンテストサイト
## 日本語
yukicoder https://yukicoder.me/
AtCoder https://atcoder.jp/
AIZU ONLINE JUDGE (AOJ) http://judge.u-aizu.ac.jp/onlinejudge/
## 英語
TopCoder
Single Round Match (SRM) 関係リンク集 http://codeforces.com/blog/entry/21879
Marathon Match (MM) https://community.topcoder.com/longcontest/?module=ViewPractice
※TopCoderは初参加までの手順が煩雑です。まずはググってみて、それでも分からなかったらスレで聞こう！
Codeforces http://codeforces.com/
CS Academy https://csacademy.com/
Project Euler https://projecteuler.net/ 和訳 http://odz.sakura\.ne.jp/projecteuler/

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

**仕様書無しさん** · 2019/12/02(月) 20:51:54.57

テンプレ続き

# 高校生・大学生対象コンテスト
情報オリンピック https://www.ioi-jp.org/
ACM-ICPC http://icpc.iisf.or.jp/

# その他便利なサイト
コンテスト・カレンダー
https://competitiveprogramming.info/calendar
http://clist.by/
AtCoder Problems http://kenkoooo.com/atcoder/
オンライン整数列大辞典 https://oeis.org/?language=japanese
WolframAlpha https://www.wolframalpha.com/
Spaghetti Source
旧: http://www.prefield.com/algorithm/
新: https://github.com/spaghetti-source/algorithm
競技プログラミングwiki http://wikiwiki.jp/kyopro/
AOJ-ICPC http://aoj-icpc.ichyo.jp/
competitiveprogramming.info https://competitiveprogramming.info/
競プロSlack https://competitiveprogramming.info/slack
OnlineJudgeHelper (オンラインジャッジ補助スクリプト) https://github.com/nodchip/OnlineJudgeHelper
Google翻訳 https://translate.google.co.jp/

**仕様書無しさん** · 2019/12/02(月) 20:52:33.31

テンプレ続き

# 書籍
プログラミングコンテストチャレンジブック (蟻本)
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (AOJ本, TLE本, 渦巻本)
最強最速アルゴリズマー養成講座 (チーター本)

# 日本人競技プログラマ
Twitter 競技プログラマリスト
https://twitter.com/kinaba/lists/topcoder-jp
https://twitter.com/kobae964/lists/atcoder
TopCoder Single Round Match (SRM) のランキング
https://community.topcoder.com/tc?cc=392&;sc=&sd=&cc=392&module=AlgoRank&nr=200&sr=
TopCoder Marathon Match (MM) ランキング
https://community.topcoder.com/longcontest/stats/?module=CoderRank&;cc=392
Codeforces ランキング
http://codeforces.com/ratings/country/Japan
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account)

**仕様書無しさん** · 2019/12/02(月) 20:54:18.31

**仕様書無しさん** · 2019/12/02(月) 20:54:41.30

テンプレ続き

# 関連スレ
【したらば】プロコン・競プロ・ハッカソン・CTFなどについて語り合う掲示板
https://jbbs.shitaraba.net/internet/13109/
TopCoder
https://mevius.5ch.net/test/read.cgi/tech/1333159918/l50
プログラミングのお題スレ Part9 [無断転載禁止]c2ch.net
https://mevius.5ch.net/test/read.cgi/tech/1480579110/
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3c2ch.net
https://mevius.5ch.net/test/read.cgi/tech/1466315249/l50
【会津】パソコン甲子園2004【若松】
https://mevius.5ch.net/test/read.cgi/tech/1094308951/l50
CTFについて語るスレ [無断転載禁止]c2ch.net
https://medaka.5ch.net/test/read.cgi/sec/1476430177/l50

>>1からここまでテンプレ

**仕様書無しさん** · 2019/12/06(金) 01:15:24.19

乙

**仕様書無しさん** · 2019/12/06(金) 01:51:16.26

こどふぉに出るとやっぱ生活壊れるね

**仕様書無しさん** · 2019/12/06(金) 03:53:06.70

age

**仕様書無しさん** · 2019/12/06(金) 08:16:36.39

学生で競プロerとか名乗ってる連中って結局意味不明なスラング連呼しつつ他所様に喧嘩売り散らして自分が頭良いと思い込んでるだけの発達ガイジ集団やろ

キラキラスタートアップ(笑)ならまだしもマトモなとこは絶対採れへんわこんなん
精神年齢が低すぎて開発業務は無理無理

**仕様書無しさん** · 2019/12/06(金) 08:40:26.08

職業プログラマもCくらいサクサク解けるやつ揃えないと会社の業績に関わるぞ

**仕様書無しさん** · 2019/12/06(金) 08:41:30.36

フレームワークの新機能とか詳しくなるより大事やろ

**仕様書無しさん** · 2019/12/06(金) 19:20:46.56

今日なんかコンテストあるの？

**仕様書無しさん** · 2019/12/06(金) 19:50:01.17

AGCレベルはいらんけどせめてABC前半レベルは要るだろ
プログラムのpも分からん奴なんてエクセルしかできんやん

**仕様書無しさん** · 2019/12/07(土) 18:28:23.38

HTTFやらかしか？

**仕様書無しさん** · 2019/12/07(土) 22:32:07.55

writerがchokudaiじゃなかったらもっと叩かれてるだろうな

**仕様書無しさん** · 2019/12/07(土) 22:43:46.09

何かしらの手段を毎回考えているなｗ
＊＊なお、あくまで考えるだけで現実には生かされない模様

**仕様書無しさん** · 2019/12/08(日) 00:08:45.56

マラソンどうでもいいから言語アップデートしてくれ

**仕様書無しさん** · 2019/12/08(日) 00:32:30.90

こんなところに高校生はいないだろうがJOI二次予選がんばってね

**仕様書無しさん** · 2019/12/08(日) 04:54:54.29

まじで早く言語アップデートしてくれないかな
最新の機能バリバリ使ってるわけでもないコードがCEで弾かれるのすげえだるい

**仕様書無しさん** · 2019/12/08(日) 10:26:12.58

初心者は最新分からないから後回し。というのありそう

**仕様書無しさん** · 2019/12/08(日) 10:39:52.86

c++は最新だろうが誰も分からんが他はそうでもない

**仕様書無しさん** · 2019/12/08(日) 10:59:29.71

そろそろmath.gcd使わせてほしいな

**仕様書無しさん** · 2019/12/08(日) 11:07:12.08

チョクダイ仕事遅い

**仕様書無しさん** · 2019/12/08(日) 22:36:52.91

前回との落差が酷い
大変かもしれないけど難易度のバランス調整もうちょっと頑張ろ？

**仕様書無しさん** · 2019/12/08(日) 22:40:52.61

>>24
今まさに同じこと書き込もうとしてたわ
前回あれで今回これかよ

**仕様書無しさん** · 2019/12/08(日) 22:43:55.92

Dは行けたけどCが分からんかった

**仕様書無しさん** · 2019/12/08(日) 22:48:42.33

C普通に全通り試せばいいだけなのか

**仕様書無しさん** · 2019/12/08(日) 22:53:14.22

E, bitset無しだとキツすぎない？
それ想定なんかな

**仕様書無しさん** · 2019/12/08(日) 22:55:30.05

Rateの反映早いな

**仕様書無しさん** · 2019/12/08(日) 23:02:05.55

>>24-25
3完茶色勢なのであまり感じないんだけど簡単だったってこと？

**仕様書無しさん** · 2019/12/08(日) 23:07:30.07

この前はFが600点に相応しくない一方で今回のCは400とは行かないが300にしては難しかったわ

**仕様書無しさん** · 2019/12/08(日) 23:09:42.72

前回の方が割と簡単だったような

**仕様書無しさん** · 2019/12/08(日) 23:12:08.06

>>28
言語によるかもしれないが、C++ならシンプルなループは無茶苦茶早い

>>30
今回は難しめ
というか前回が相当簡単だったんで、差がすごい

**仕様書無しさん** · 2019/12/08(日) 23:20:04.25

パフォ見れば分かるでしょ
今回は2完でも緑パフォ行く

**仕様書無しさん** · 2019/12/08(日) 23:41:35.22

>>33
そうなのか有難う。Cは前回のが簡単だったから逆だと思ってた

>>34
なるほど。パフォとか気にしたことなかった
調べたら4連続で緑パフォだったけどあと何回で茶色出れるんだろう…

**仕様書無しさん** · 2019/12/08(日) 23:53:10.74

自分はパフォ800を10回以上積み重ねて緑になった記憶
1200以上出せれば直ぐ緑なんだろうな
最近飽きてやってない

**仕様書無しさん** · 2019/12/09(月) 00:47:57.36

DはC++勢がWA連発してるね
ある意味良問

**仕様書無しさん** · 2019/12/09(月) 00:49:29.95

>>37
なんでC++だとWAなんだ？

**仕様書無しさん** · 2019/12/09(月) 04:37:03.82

なんだろう、オーバーフローかな
確かにpythonなら何も気にせず書いても大丈夫そう

**仕様書無しさん** · 2019/12/09(月) 07:56:35.49

>>36
そんなに回数必要なのね
ABC出る時間をD～E解くための勉強に使った方が良さそう

**仕様書無しさん** · 2019/12/09(月) 17:31:11.62

PAST、大丈夫か？

**仕様書無しさん** · 2019/12/09(月) 17:54:00.77

ABC深夜に告知出す感覚で9000円コンテストの告知出されても困る
周知もあんまりされてないし受験させたいターゲットに届いてないんじゃないの

**仕様書無しさん** · 2019/12/09(月) 18:12:03.86

そもそも受験させたいターゲットに初回を受けてもらおうとしてなさそう
(何回かやって整ってから、みたいな雰囲気を感じる)

**仕様書無しさん** · 2019/12/09(月) 19:08:03.56

リアルタイム受験と通常受験が分かれてるけど大丈夫か？

**仕様書無しさん** · 2019/12/09(月) 19:27:19.64

学生向けかな
お受験は大学までで卒業した

**仕様書無しさん** · 2019/12/09(月) 21:30:06.89

8800円か割と高くね？

**仕様書無しさん** · 2019/12/09(月) 21:46:32.83

君も1500問解いて暖色になろう

**仕様書無しさん** · 2019/12/10(火) 01:33:12.04

今週末もABCやってくれないかな…

**仕様書無しさん** · 2019/12/10(火) 06:47:27.59

最近黄色が寒色に見えてきた

**仕様書無しさん** · 2019/12/10(火) 08:05:05.93

初AtCoderだったんだがABまでしか解けなかった

**仕様書無しさん** · 2019/12/10(火) 09:06:29.85

>>50
プログラミングに慣れてればcまではいけるから頑張って

**仕様書無しさん** · 2019/12/10(火) 09:40:02.36

今回のCは入出力に癖ありだからしゃーない

**仕様書無しさん** · 2019/12/10(火) 09:44:17.04

AtCoderの黄色はちょっと中性色寄りかなあ、寒色ではない

**仕様書無しさん** · 2019/12/10(火) 11:19:14.34

黄色とかダサいよ浅葱色とかに変えたら？

**仕様書無しさん** · 2019/12/10(火) 11:39:19.54

学がねえから葱にしか目が行かねえ

**仕様書無しさん** · 2019/12/10(火) 12:00:08.97

五時間
アホすぎて草不可避ｗ
アルゴはデザインできても
試験はデザインできないもんだねえ
近い将来時間短縮されるのが見えるわなｗ

**仕様書無しさん** · 2019/12/10(火) 13:18:10.85

確かにレート毎の色を伝統色にしたらオシャレかも

**仕様書無しさん** · 2019/12/10(火) 18:59:27.38

とうとう日立x北大マラソンは50人超えたな

**仕様書無しさん** · 2019/12/10(火) 20:37:26.15

おめでとう

**仕様書無しさん** · 2019/12/11(水) 19:07:57.27

お前らpast受けるの？

**仕様書無しさん** · 2019/12/11(水) 19:15:37.51

受ける人いるんか？

**仕様書無しさん** · 2019/12/11(水) 19:20:26.17

土日はこどふぉでお腹いっぱい

**仕様書無しさん** · 2019/12/11(水) 19:31:23.34

日経オープンさん…

**仕様書無しさん** · 2019/12/11(水) 19:44:30.54

日経コン決勝が予定されたコンテストに書いてないの仕事なめてるな
デザインいじってるの優先順位がおかしい

**仕様書無しさん** · 2019/12/11(水) 19:50:13.77

チョクダイ仕事しろ

**仕様書無しさん** · 2019/12/11(水) 20:46:20.71

高橋君と青木君はツイッターでイキって競プロの知名度を上げることが仕事だから

**仕様書無しさん** · 2019/12/11(水) 21:57:04.44

天下一 Game Battle Contest(β)
https://tenka1.klab.jp/2019-obt/
2019年12月21日(土) 14:00～18:00

**仕様書無しさん** · 2019/12/11(水) 22:19:05.83

ABCのC.D解けるようになるまでどれくらい時間掛かった？過去問やっとけば良いんかな

**仕様書無しさん** · 2019/12/11(水) 22:35:52.55

>>68
Cはプログラミング経験３か月の俺が初挑戦でも解けた
Dは過去10回分ぐらいやったら６割ぐらい解けるようになった

**仕様書無しさん** · 2019/12/11(水) 22:43:16.08

>>69
サンクス
Dを10回で6割解けるの凄いな

**仕様書無しさん** · 2019/12/11(水) 22:57:50.29

>>70
数学の知識がある程度あったから
それもあるかも

**仕様書無しさん** · 2019/12/12(木) 03:16:32.89

初参加でABC全完が難しくない時代があったね

**仕様書無しさん** · 2019/12/12(木) 19:05:36.89

日経コン決勝のページ出たけど中身ガバガバで草

**仕様書無しさん** · 2019/12/12(木) 21:34:04.26

>>68
Cは最初からほぼ100%できたけどDを30%解けるようになるまで半年
数学知識なし、過去問は土日数時間だけのパターンだけど

**仕様書無しさん** · 2019/12/13(金) 13:24:16.58

競プロ歴半年でC50問くらい埋めたけど最近のC解けなかったな

**仕様書無しさん** · 2019/12/13(金) 14:16:07.20

Cは制約から計算量読めば解けるよ

**仕様書無しさん** · 2019/12/13(金) 22:02:51.01

蟻本に載ってる区間スケジューリング問題の貪欲法の証明が上手く理解出来ないんですけど何か良い解説などってありますか……？
初歩的な段階の質問ですみません。

**仕様書無しさん** · 2019/12/13(金) 23:42:38.90

良い解説かは知らないけど本質は抑えられてる
http://www.prefield.com/algorithm/misc/interval_scheduling.html

**仕様書無しさん** · 2019/12/14(土) 01:53:44.14

証明ちゃんと納得しようとしてるの偉いな
俺は最初適当に貪欲で出来るんだへーって言ってた気がする

**仕様書無しさん** · 2019/12/14(土) 03:24:25.46

Twitter見ると意外とpast受けるやつ多いな

**仕様書無しさん** · 2019/12/14(土) 04:58:26.93

>>78
返信遅くなりましたがありがとうございます！
自分なりに整理した感じとしては
①選べるものを順番に見て、終了時間が一番早い仕事(仮にW1と呼びます)を選んだ場合
　=今回のアルゴリズムを適用した場合、
それがW1の終了時間(T1)までの中で一番仕事の回数が多くなる方法である
（仮にT1までに2回以上の仕事が出来る場合、どう考えても終了時刻はT1より前になるため
　『終了時間が一番早く選ぶ』というアルゴリズムに矛盾しているため)
②上記の理由及び終了時刻が早い方が多くの仕事を選べるので、
　時刻が被ってるものは今回のアルゴリズムを使ってどんどん遡っていけば
　最終的には最多の仕事を選べる。
みたいな理解でよいのでしょうか？
勉強不足なので雑な理解＆説明になっているかもしれませんが……。

**仕様書無しさん** · 2019/12/14(土) 07:54:43.19

みんなお金持ってるなー

**仕様書無しさん** · 2019/12/14(土) 10:25:43.44

俺もそれよく分からん認識だったから書いてみたけど一緒だった

最初にやる仕事を選ぶことを考える
終了時間が一番早い仕事W1[s1,e1]とそうでない任意の仕事W2[s2,e2]を考えた場合
1.1+[0,s1)または(e1,Inf)で出来る仕事の中で被らず最も多くできる仕事の数
2.1+[0,s2)または(e2,Inf)で出来る仕事の中で被らず最も多くできる仕事の数

最初にやる仕事を選ぶって言ったので
1.1+(e1,Inf)で出来る仕事の中で被らず最も多くできる仕事の数
2.1+(e2,Inf)で出来る仕事の中で被らず最も多くできる仕事の数

e1<e2なので1の方がいい
後は再帰

**仕様書無しさん** · 2019/12/14(土) 10:54:34.98

>>81
>>78の証明と蟻本のとは証明方法が違うからどうしても蟻本のやり方を理解したいなら>>78は邪魔かもね
実際の蟻本のやり方では、1の段階ではまだ仕事を行う回数が一番多くなるってことには触れていない。
それは2の段階で証明されることだから。1の段階で証明したいのは「i番目に行うタスクを最も早く終わらせる選び方」だということ
貪欲法の説明そのままのようだけど、それだけ

それが証明できれば、貪欲法より多くのタスクを実行できる選び方が存在しないことも証明できる

**仕様書無しさん** · 2019/12/14(土) 12:00:05.50

past５時間って結構つらいな

**仕様書無しさん** · 2019/12/14(土) 12:12:56.34

エキスパート取ろうと思ったら一問しか間違えられないのか

**仕様書無しさん** · 2019/12/14(土) 12:14:09.90

例題見るとABCレベルの問題が並んでる感じか？

**仕様書無しさん** · 2019/12/14(土) 12:16:21.31

†赤†です
エキスパートです

どっちがかっこいいかよ

**仕様書無しさん** · 2019/12/14(土) 12:18:03.83

past参加者はatcoder支援したい金ある社会人が大半じゃないかな。
時間あって金ない学生はそこまで受けるメリットない。

**仕様書無しさん** · 2019/12/14(土) 12:20:29.48

>>87
少なくとも例題は過去のABCから持ってきたものだね
ちょくだい曰くエキスパートが青確実ってレベルらしいから本番も同じ傾向でしょう

**仕様書無しさん** · 2019/12/14(土) 12:45:46.90

これ、期間過ぎたら問題と解説公開してくれるんだよな？

**仕様書無しさん** · 2019/12/14(土) 12:50:19.50

今週はABCないんか

**仕様書無しさん** · 2019/12/14(土) 12:53:21.28

うーんやっぱ８８００円は痛いわ
受けるの辞めとこ

**仕様書無しさん** · 2019/12/14(土) 12:56:08.88

今日は20:05からこどふぉがある
PAST受けない人はこっちに出よう

**仕様書無しさん** · 2019/12/14(土) 12:56:20.89

青確実ねえ。まずはABCDでパフォ1200出す練習せねば

**仕様書無しさん** · 2019/12/14(土) 12:58:05.20

>>94
atcoderしか受けたことないんだけど基本的にatcoderと変わらない？

**仕様書無しさん** · 2019/12/14(土) 13:01:43.40

ひどすぎてクソワロタ
これで金とるんか

**仕様書無しさん** · 2019/12/14(土) 13:03:33.31

問題文が英語で、問題の作風は違うみたいだが、入出力や提出方法なんかはおんなじだね

**仕様書無しさん** · 2019/12/14(土) 13:04:59.60

・問題文が英語
・C++で入力高速化しないと厳しい問題がある
・プリテスト（本番中のテスト）が非常に弱い
くらい。ハックとかは気にする必要がない

**仕様書無しさん** · 2019/12/14(土) 13:43:22.11

今日のwriterは信頼できるし人権時間だし出ない理由はないぞ

**仕様書無しさん** · 2019/12/14(土) 15:35:51.61

>>98
日本語版もあるよ