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

**仕様書無しさん** · 2020/02/08(土) 11:04:05.90

プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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/proj
※前スレ
競技プログラミングにハマるプログラマのスレ 22
https://medaka.5ch.net/test/read.cgi/prog/1575287454/

**仕様書無しさん** · 2020/03/19(木) 14:05:07.58

にきあ君は競プロ辞めちゃったんだよな

**仕様書無しさん** · 2020/03/19(木) 16:37:22.97

Topcoderでマラソンマッチ116が今日から始まったらしいぞ
期間は1週間くらい

https://www.topcoder.com/challenges/30119681

マラソンマッチの始め方の記事
https://qiita.com/phocom/items/da0f8123f7a8d5201cbf
マラソン記事まとめ記事
http://threeprogramming.lolipop.jp/blog/?p=1164
マラソンメタ戦略の記事
https://kimiyuki.net/blog/2018/11/22/tools-and-tips-for-marathon-matchs/

**仕様書無しさん** · 2020/03/19(木) 17:16:08.83

コロナのせいでヒマだし少しやってみるか…

**仕様書無しさん** · 2020/03/19(木) 19:58:19.29

3/19 23:35 Codeforces Global Round 7
3/20 10:00 SRM 781
3/20 13:00 Kyoto University Programming Contest 2020 Spring
3/20 21:20 yukicoder contest 241
3/21 21:00 AtCoder Grand Contest 043
3/22 13:00 Kick Start Round A
3/22 21:00 AtCoder Beginner Contest 159

**仕様書無しさん** · 2020/03/19(木) 20:47:52.18

chokudai記念結婚AGC絶対出たくねえ

**仕様書無しさん** · 2020/03/19(木) 21:02:23.01

この増田かなり共感した、お前らこういう気持ちになったらどうしてるの?

競技プログラミングが好き、AtCoder社が苦手。
https://anond.hatelabo.jp/20200317211716

**仕様書無しさん** · 2020/03/19(木) 21:17:07.75

作品は好きだが作者は嫌いみたいなアレだろ
俺自身は流してる
記事と違って俺は社長のが嫌いだけども

**仕様書無しさん** · 2020/03/19(木) 21:28:37.57

>>718
>>720
なるほどありがとう

**仕様書無しさん** · 2020/03/19(木) 21:30:04.02

小説とか漫画とかだと著者の人格を知ってしまって作品を嫌いになるってのはある程度分かるんだよな
でも競プロだとあんまそういうの関係無くないか、自分もchokudai氏はあんま好きでは無いけど別にいい
コンテストに運営の人格とかほぼ関係無いしそもそも問題作ってんのはwriterだし
それでも辛いってんなら止めたらいいのでは、AtCoderだけじゃなくてCodeforcesとかあるし

**仕様書無しさん** · 2020/03/19(木) 22:05:08.68

某記事を書いてる人も能力はすごいのにTwitterが気持ち悪すぎて失望した
能力がすごいのに人として終わってる人が多い

**仕様書無しさん** · 2020/03/19(木) 22:12:10.28

自分にとって受け付けないだけで「人として終わってる」と評するのも中々だな

**仕様書無しさん** · 2020/03/19(木) 22:29:19.08

たしかに、物語の作者が嫌いなことよりAtCoder社員が嫌いなことの方が救いはあるな
問題に作者の思想が透けて見えたりってことは少なくとも俺はあまりない(し、そもそもwriterが社員であることはほぼない)から

**仕様書無しさん** · 2020/03/19(木) 22:31:14.73

ABCのサンプルに寒いTwitterの馴れ合いが入ってる時は流石に吐き気がしたけど、そういうのさえなければ…

**仕様書無しさん** · 2020/03/19(木) 22:38:14.11

chokudaiはRT晒しするのが嫌だな

**仕様書無しさん** · 2020/03/19(木) 22:53:07.95

言いたい事があるなら直接言えばええやん

**仕様書無しさん** · 2020/03/19(木) 23:08:50.50

年1行事なのに解説を公開しない
パソコン甲〇園
参加者への敬意が全くないよね

**仕様書無しさん** · 2020/03/19(木) 23:15:58.87

しつこいね

**仕様書無しさん** · 2020/03/19(木) 23:21:31.99

>>736
ツイッターでの解説じゃ不満なの？
https://twitter.com/pc_koshien
https://twitter.com/5chan_nel (5ch newer account)

**仕様書無しさん** · 2020/03/19(木) 23:31:41.72

でもchokudaiの方がrating高いからな
副社長は…

**仕様書無しさん** · 2020/03/19(木) 23:44:06.61

本日もレーティングバトル日和です

**仕様書無しさん** · 2020/03/19(木) 23:51:40.27

女晒すとか顕示欲の塊

**仕様書無しさん** · 2020/03/20(金) 00:08:52.56

誕生日だから許してください

**仕様書無しさん** · 2020/03/20(金) 00:36:04.12

真理を窮める
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10151253300

**仕様書無しさん** · 2020/03/20(金) 00:54:33.71

アレとアレがアレなのを想像すると草

**仕様書無しさん** · 2020/03/20(金) 01:25:16.65

ぐろふぉに参加してないFAKE野郎は俺たちです

**仕様書無しさん** · 2020/03/20(金) 10:00:58.39

彼女とか住所とか性の価値観だとか、そろそろ発言控えた方が良い気がする…

**仕様書無しさん** · 2020/03/20(金) 14:40:24.81

性の価値観て何

**仕様書無しさん** · 2020/03/20(金) 14:52:46.99

上の増田には同意だけど、そもそもAtCoderがコンテンツ単体として弱すぎるから
社長が広告塔になって何とか規模をキープしてるんだよな
結局、TOP1,2共に人格がアレなのが露見して上手くいってないけど

**仕様書無しさん** · 2020/03/20(金) 14:54:26.03

くだらない話してないでKUPCやろうぜ

**仕様書無しさん** · 2020/03/20(金) 17:00:00.55

>>748
リアルタイムの参加者7000人ってうまく行ってないと言うのか？減ってるなら分かるけど増えてるし…
経営戦略が上手いのか単純に日本語のコンテストサイトなら誰が運営しててもそうなったのかは簡単には結論出ないと思うけど

**仕様書無しさん** · 2020/03/20(金) 17:12:49.60

数字は嘘をつかない
https://catr.jp/companies/78574/32888

**仕様書無しさん** · 2020/03/20(金) 17:14:19.87

数字は嘘をつかない
https://catr.jp/companies/78574/32888

**仕様書無しさん** · 2020/03/20(金) 17:20:36.46

東レだかから金もらったのに何も事業拡大しないし出来ない
しかも利益藻落ちてる経団連と自民党の縮小バージョンだなw

**仕様書無しさん** · 2020/03/20(金) 17:38:23.43

https://jp.quora.com › naze-roshia-h...
なぜロシアは競技プログラミングに強いのに、アメリカほどIT産業が発達していないのですか ...

**仕様書無しさん** · 2020/03/20(金) 17:48:14.76

>>753
担当者なのか出向者なのか知らんが、がんばってほしいな

**仕様書無しさん** · 2020/03/20(金) 17:53:44.02

>>751
売上の話にすり替えないでくれよ
コンテンツとしての話だろ？

**仕様書無しさん** · 2020/03/20(金) 18:18:38.06

３/20-24は春合宿オープンもあるんだな
https://contests.ioi-jp.org/joi-sp-2020/index.html

**仕様書無しさん** · 2020/03/20(金) 18:33:40.77

AGC043 4-7-9-12-14-21

**仕様書無しさん** · 2020/03/20(金) 21:50:52.69

>>757
C++限定なんだな

**仕様書無しさん** · 2020/03/21(土) 00:02:52.80

>>755
100ワニと同じ道を辿りそう

**仕様書無しさん** · 2020/03/21(土) 00:45:50.02

人が増えたら本、グッズ、有料コンテンツはあるだろうな

**仕様書無しさん** · 2020/03/21(土) 00:50:22.47

何でもいいからもっと金儲けしてコンテストを増やせ

**仕様書無しさん** · 2020/03/21(土) 00:53:39.61

金で海外の writer 引っ張ってこれればコンテスト増やせそう

**仕様書無しさん** · 2020/03/21(土) 03:37:06.61

言うは易く行うは難し

**仕様書無しさん** · 2020/03/21(土) 05:06:08.08

海外writer増やしたいけどAdminとの意思疎通にかかる手間が国内writerと比べてめちゃ大きいみたいなこと言ってた気がするな

**仕様書無しさん** · 2020/03/21(土) 05:50:52.20

ソース気になる

**仕様書無しさん** · 2020/03/21(土) 08:15:44.49

誰が悪いって話じゃないけど
この手の話、ツイッターでの呟きが主だからソースの提示が困難なんだよな

**仕様書無しさん** · 2020/03/21(土) 10:52:33.00

>>767
公式Twitterとか公式ページでいろいろ書いて欲しいんだけどな
個人垢や生放送はお気持ちばかり

**仕様書無しさん** · 2020/03/21(土) 11:51:45.22

>>760
N日後の担当者
3億とともに切られるか、稼いで戻って出世するかの気になる

**仕様書無しさん** · 2020/03/21(土) 15:43:19.94

それよりも過去問サイトかqiita君の買い取りがありそう

**仕様書無しさん** · 2020/03/21(土) 16:00:22.62

日本の競プロerはTwitterばっか使ってるけど外国人はどこで喋ってるんだ？

**仕様書無しさん** · 2020/03/21(土) 16:30:03.63

馴れ合いが無いんじゃね

**仕様書無しさん** · 2020/03/21(土) 16:36:43.98

こどふぉ

**仕様書無しさん** · 2020/03/21(土) 16:47:22.16

学校でしょ

**仕様書無しさん** · 2020/03/21(土) 16:52:34.01

ほらよ、お喋りしてこい

Competitive Programming Community Discord (5800+ Members): Discussions hub!
https://codeforces.com/blog/entry/52778

**仕様書無しさん** · 2020/03/21(土) 16:59:49.64

このスレの歴史で一番有用な情報じゃん

**仕様書無しさん** · 2020/03/21(土) 19:30:25.92

>>774
Twitter見ていると
競プロ布教由来の学校内（友人、部活、サークル、授業、研究室）での繋がりのコミュニティ
オンサイト決勝や競プロer同士のオフライン交流会（合宿、勉強会、もくもく会、食事会、飲み会、その他イベント）で繋がったコミュニティ

つまりコミュ強の集合

俺ら5ch勢はコミュ障の集合

**仕様書無しさん** · 2020/03/21(土) 19:32:34.32

海外競プロerも俺らのような陰キャやコミュ障が多いと考えれば海外にまともなコミュニティは無い

**仕様書無しさん** · 2020/03/21(土) 19:35:52.35

>>775
ロシア勢も中国勢も
日本勢と同様に非英語圏であり英語は苦手なはず

そんな英語で母国語のような気楽な言葉書いて交流なんて無理で
文法お硬い文章やグーグル翻訳した文章で楽しい交流なんて出来るわけもない

**仕様書無しさん** · 2020/03/21(土) 19:56:58.88

母国語でも話が通じない人はいるし母国語でなくても十分なコミュニケーションを取れる人もいる

**仕様書無しさん** · 2020/03/21(土) 20:25:11.72

前者はただのコミュ障で後者はコミュ強

**仕様書無しさん** · 2020/03/21(土) 20:26:19.81

君らAGC043出るかい？

**仕様書無しさん** · 2020/03/21(土) 20:32:10.18

安価つけてレス出来ないやつはコミュ障

**仕様書無しさん** · 2020/03/21(土) 21:55:07.98

いつも気持ち悪い冗談で話題にするくせに、ワニの件はマジレスかよ…

**仕様書無しさん** · 2020/03/21(土) 22:00:12.21

木構造の勉強してるんですが、簡単な（単純な））典型問題とかないでしょうか？
ABCのD以上だと幾つか見つかるんですが自分には難しすぎるので

**仕様書無しさん** · 2020/03/21(土) 22:19:07.49

電通さんのビジネスは悪くは言えないでしょうなあ、という観点が拭えない

**仕様書無しさん** · 2020/03/21(土) 22:32:12.07

エアプだから適当言うけど
AOJのコースにあるALDS1にある木構造のトピックや
yukucoderやcodeforcesだとタグで問題を探せるし
CSAcademyは結構細かく分類されてるし

**仕様書無しさん** · 2020/03/21(土) 22:35:43.09

>>785
AOJカテゴリー別問題集でtreeのタグ付いてるやつやれば？

**仕様書無しさん** · 2020/03/21(土) 22:41:03.55

HackerRankも大雑把ではあるけど分類はされてるよね

**仕様書無しさん** · 2020/03/21(土) 22:43:23.85

LeetCodeは典型揃ってるみたいな話なかったっけ？

https://leetcode.com/tag/tree/

**仕様書無しさん** · 2020/03/21(土) 22:56:44.91

おすすめはALDSだな
Dが難しいならまずは木構造そのものに慣れた方がいい

**仕様書無しさん** · 2020/03/21(土) 23:03:11.44

>>787-791
AOJとcodeforcesは調べてたんですが、もう少し簡単な問題がないかと思い質問しました
ちなみに http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_B が解けないレベルです
（ALDS1のソートとかは幾つか解けました）

yukucoderとLeetCodeは知らなかったので調べてみます。ありがとうございます

**仕様書無しさん** · 2020/03/21(土) 23:09:05.61

yukucoderはスペルミスでyukicoderな、すまんこ

**仕様書無しさん** · 2020/03/21(土) 23:19:53.48

>>792
ALDSって教科書の例題みたいなもんで、それより簡単な問題はほとんどない
だからまずは教科書とか解説ブログとか他人の提出コードを参考にしてALDSを解くのを勧める

**仕様書無しさん** · 2020/03/21(土) 23:40:02.73

AGCのパフォ
もう見れてる人いるけどどう見るの？

**仕様書無しさん** · 2020/03/21(土) 23:42:49.61

https://ac-predictor.azurewebsites.net/

**仕様書無しさん** · 2020/03/21(土) 23:44:54.34

>>792
これの解答見てもわからないレベルなのか，解法が思いつかなかっただけなのか
前者なら全般に知識が足りなそうなので，aoj埋めとかatcoder埋めとかしてアルゴリズムに慣れたほうがいいと思う
後者ならaojのtreeタグが付いてるのを簡単なやつから解いていけばよさそう

**仕様書無しさん** · 2020/03/21(土) 23:45:32.80

>>796
ありがとう！

**仕様書無しさん** · 2020/03/21(土) 23:49:21.82

A - Range Flip Find Routeって、
bfsやdfsでは解けないんでしょうか

**仕様書無しさん** · 2020/03/22(日) 00:04:16.38

距離0→距離1→とやっていけばできそうだけど
ダイクストラ法(0-1BFS)を使うのと変わらないかも

**仕様書無しさん** · 2020/03/22(日) 00:10:24.16

やっぱAGCはたのしいな

**799** · 2020/03/22(日) 00:11:12.98

>>800
ありがとう

**仕様書無しさん** · 2020/03/22(日) 00:31:31.69

問題は面白いんだけど勝てねえ
勝てるという意味ではARCやこどふぉの方が楽しい

**仕様書無しさん** · 2020/03/22(日) 09:20:49.60

>>794
そうなんですね…もう少し解説ブログとかを調べて読み込んでみます

>>797
前者でした。木問題に限らず埋めていった方がいいという事ですね、やってみます

どうもありがとうございました

**仕様書無しさん** · 2020/03/22(日) 13:01:57.85

>>792って全方位木DPか木の直径の性質を使う奴かだからちょっと難しい気はする
DFS一発で解けるような問題からやったほうがいいかなあとか思った

**仕様書無しさん** · 2020/03/22(日) 18:41:35.11

>>805
普通に全頂点間の距離を求めるだけでは

**仕様書無しさん** · 2020/03/22(日) 18:45:06.31

>>806
グラフのn=10000でΘ(n^2)は厳しそう

**仕様書無しさん** · 2020/03/22(日) 18:53:57.54

10^4で2乗オーダーこわい

**仕様書無しさん** · 2020/03/22(日) 18:55:08.16

>>807
10^8ならいけると思ったけどよく考えたらlognもつくか

**仕様書無しさん** · 2020/03/22(日) 19:03:11.81

>>809
logどこ

**仕様書無しさん** · 2020/03/22(日) 19:12:05.68

>>810
LCA求めるとこ

**仕様書無しさん** · 2020/03/22(日) 19:33:56.68

どこでlcaつかうねん

**仕様書無しさん** · 2020/03/22(日) 19:34:17.51

やるにしても全頂点からDFS/BFSするだけでしょ
LCAがO(1)という話もあるけど

**仕様書無しさん** · 2020/03/22(日) 19:57:56.84

>>811
LCAで任意の二点間距離がlognで求まる的な？

**仕様書無しさん** · 2020/03/22(日) 20:23:24.69

直径求めたら直径の2点とのどっちからからの距離が任意頂点の高さでしょ

**仕様書無しさん** · 2020/03/22(日) 21:21:08.02

>>814
それ
この問題なら必要なかった

**792** · 2020/03/22(日) 22:36:05.53

>>805
もし「DFS一発で解けるような問題」ご存じでしたら教えてほしいです
ALDSも一工夫必要な問題が多くて、解説読んでるんですが中々理解が進まないので…

**仕様書無しさん** · 2020/03/22(日) 22:38:08.43

見落としてる例外がどこかわからない
こういうのができないから昔から数学が苦手なんだよなぁ

**仕様書無しさん** · 2020/03/22(日) 22:42:44.39

外部からの攻撃で草

**仕様書無しさん** · 2020/03/22(日) 22:50:12.83

ここの住人の仕業か？