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

■ このスレッドは過去ログ倉庫に格納されています
1仕様書無しさん
垢版 |
2019/01/28(月) 00:11:47.31
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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/

>>2-10あたりにテンプレ続く
※前スレ
競技プログラミングにハマるプログラマのスレ 17
https://medaka.5ch.net/test/read.cgi/prog/1540997394/
2019/04/04(木) 23:51:03.76
今ICPC WFやってるのね
東大すごいじゃん
553仕様書無しさん
垢版 |
2019/04/05(金) 05:32:51.09
東大3位おめでとう！

上位のCFレートやばいな
https://codeforces.com/blog/entry/66365?#comment-503857
2019/04/05(金) 09:56:10.86
>>551
そうですね。
そのくらいのレベルの問題を解きたいというのと全完したいというのがあります
555仕様書無しさん
垢版 |
2019/04/05(金) 16:37:17.27
水色や青色のレベルのコーダーが全完可能な問題セットになることのあるコンテストでABC以外か
2019/04/05(金) 17:21:22.57
codeforces div3 かSRM div2
2019/04/06(土) 00:24:43.58
>>542
年齢制限はオンサイト参加資格の話で、オンラインのラウンドは多分年齢制限ない
つまりごく一部の人を除いて関係ない
2019/04/06(土) 00:29:21.96
じゃあ息子と娘も参加させるわ
2019/04/06(土) 15:13:14.68
qual通過
2019/04/06(土) 18:25:46.30
Tシャツ欲しかったなあ…
2019/04/06(土) 19:07:01.99
今日はAtCoder水色以上の競プロerは20時半からのCodeforcesのratedコンテスト
AtCoder緑色以下の競プロerは21時からのAtCoderのABC
2019/04/06(土) 19:10:30.94
CodeForcesやTopCoderSRMのコンテストは事前登録が必要だから気をつけて
2019/04/06(土) 23:06:54.95
こどふぉは5分前着席とは知らなんだ
2019/04/06(土) 23:10:01.84
こどふぉは間に合うようにスタンバイすれば5分前着席になるから
2019/04/06(土) 23:38:57.55
C++ 入門書のおすすめっていまはどれがいいですか？
C++11とか14とかよくわからんです、
C++のバージョンアップで使える書式がふえたってことでしょうか？
2019/04/06(土) 23:39:54.71
GCJは今からでも参加登録間に合うよ
今回のqualは通貨しやすい
2019/04/06(土) 23:41:08.92
C++本の入門用なら10年ぐらい前の本でも大丈夫でしょうか？
2019/04/07(日) 00:02:45.98
一つも自分で調べてないヴァカにつけるレスなし
2019/04/07(日) 00:30:42.35
>>565
ハゲの本でいい
2019/04/07(日) 00:31:17.12
atcoderしかやらないならatcoderのc++のバージョンに合わせたらいいんじゃね
2019/04/07(日) 05:58:06.02
昨夜のABCのB問題難しすぎわろた…
まだ茶色にもなってないんだけど、他の人のコード見てもわからんわこんなんｗｗｗ
2019/04/07(日) 08:40:43.37
>>571
解説ＰＤＦは分かる？

注文の順番による時間の違いは、最後の料理を何にするかだけって事で
2019/04/07(日) 11:00:42.15
予選終了
2019/04/07(日) 11:19:28.52
interactiveな問題は相手が対話を終了している場合に入力を待ち続けるとTLEになるんだな
当たり前なことに気づかなかった
2019/04/07(日) 12:17:44.74
天下のgoogle様なのにUIがひでえ
2019/04/07(日) 18:30:22.62
qual通過したけど、Round1のA, B, Cはどれかに出ればいいの？それとも全部に出て順番に勝ち上がっていく感じ？
2019/04/07(日) 18:45:43.19
各sub-roundで上位1500人がRound2に進出できて、一度通過したらその後のsub-roundは参加できない。
感覚だけど1A,1Bの通過難易度は同じくらいで1Cはやや緩い
2019/04/07(日) 21:23:30.02
なるほど、ありがとう
2019/04/07(日) 22:31:24.25
>>556
codeforces div3ってeducationalより簡単なのか
今度解いてみよ
2019/04/07(日) 22:56:05.97
SRM div2 hardをコンスタントに解けたら普通に黄色相当だよ

コドフォはいろいろと細かいから分からん
2019/04/08(月) 04:47:17.40
二部探索とか三部探索ってさ、探索領域の左端と右端のどっちを返すべきかたまに分からなくなるんだよな
だからおおよその領域を探索アルゴリズムで決めてからその周辺を総当たりしてる
こんなバカ他にいますか？
2019/04/08(月) 05:18:56.00
たまにやるけど
2019/04/08(月) 11:35:24.24
>>581
整数ならめぐるちゃん式でなんとかならん？
https://twitter.com/meguru_comp/status/697008509376835584
https://twitter.com/5chan_nel (5ch newer account)
2019/04/08(月) 12:06:29.78
>>583
半開区間で持つようにはしてるけど

たとえば
[left, right)
で持つようにしてたら最後に返すべきなのは必ず left だ、ってこと？
2019/04/08(月) 12:28:50.24
>>584
結論としてはそう
このコードの関数solve()は満たすべき条件を表しているので、
solve()がtrueになるときに代入される変数を返せばいいと思えばわかりやすいかな
2019/04/08(月) 18:06:12.85
そうじゃないだろ
めぐる式の利点はleftとかrightで持つんじゃなくてok, ngで持つようにして返す値は最小値最大値に限らずokを返せばいいっていうところだって
2019/04/08(月) 18:12:26.67
あと実数の三分探索は十分な回数のループ回してたらどっち返してもいい、誤差の範囲に収まるから
588仕様書無しさん
垢版 |
2019/04/08(月) 18:56:34.29
巡る式はok,ngで変数持つから最終的にどっち使えば良いかが分かりやすい
2019/04/08(月) 20:34:29.90
ちょっと違うけど、たまにこんがらがって配列の添字が頭の中で爆発しちゃう
2019/04/08(月) 21:01:46.46
めぐる式は関数にしたとき絶対ok絶対ngな値とokな条件書くだけでよくなる、二分探索の隠蔽だと思ってる
2019/04/08(月) 21:22:54.58
>>586,588,590
なるほど ok, ng で区間を持てるように条件式の方を工夫せよ、という意味ですね

>>587
整数の三分探索 (つまり不連続関数上の探索) って厳密にはワークしませんよね？
つまり>>581のようにするのが正道と思って良いですか？
2019/04/08(月) 21:29:07.01
整数の三分探索はそもそも不要
傾きを見て二分探索すればいいから
2019/04/09(火) 00:47:07.31
日本人が1000人以上参加して1000人以上通過してる


Google Code Jam 2019 Qualification Round Stats
https://codeforces.com/blog/entry/66435
2019/04/09(火) 06:31:47.81
>>592
三分探索で絞ってからその周り舐めた方が簡単に書けね？
2019/04/09(火) 06:49:14.56
>>593
chokudaiさん日本人のみランキング699位/1198人中
2019/04/09(火) 09:59:26.81
めぐる式にぶたん有名だけど、lower_boundとかSTLでどうにかならない問題あるの？
2019/04/09(火) 10:38:01.08
（工夫すれば）ないよ
2019/04/09(火) 17:37:18.64
>>594
隣と差分取って正負見るだけだし、二分探索のほうが収束速いよ（定数倍だけど）
2019/04/09(火) 19:19:19.67
>>596-597
単調増加、単調減少することは分かっているが、関数の評価には時間がかかる、という場合がある
その場合、全部先に計算してコンテナに入れて lower_bound しようとは思えない
2019/04/10(水) 02:46:21.79
lower_boundの条件式の戻り値覚えられないんだよねえ
2019/04/10(水) 07:41:48.12
その都度ググったらええやろ
そのうち覚える
2019/04/10(水) 08:35:20.25
>>583
めぐるちゃん式の3枚目のsolve(mid)が分からないんだが、
これは一定値以下ならtrueを返す関数solveがどこまでならtrueを出すかを二分探索で求めて、最後はokがtrueを返す最大値、ngはfalseを返す最小値になるってことで合ってる？
あと(ng, ok]ってng<okになる場合を仮定してる理由がわからん
話題引きずってすまん
2019/04/10(水) 11:13:09.40
solveはtrue/falseを返す関数だったら何でもいい
二分探索はtrue/falseの境界を効率良く探索するアルゴリズムで
true, true, true, false, false, .... なら[ok, ng)型（最大値を求めるパターン）
false, false, false, true, true, ... なら(ng, ok]型（最小値を求めるパターン）
そのどっちのパターンでもめぐる式なら常にokを返すだけでいいから迷わなくていいよね
っていうのがめぐる式の優れている点
2019/04/10(水) 12:56:40.74
solve(okの初期値)とsolve(ngの初期値)は呼ばれないというのも覚えておくといい
605仕様書無しさん
垢版 |
2019/04/10(水) 20:16:18.33
初期値を-1とnにしてmidを取ると絶対にmidが[0,n-1]になるのがポイントなきがする
2019/04/12(金) 05:10:28.06
>>593
2014年〜2017年のqualが日本人700人くらいだから競プロ人口が激増しているのは確実だな

754人 https://www.go-hero.net/jam/17/regions
735人 https://www.go-hero.net/jam/16/regions
710人 https://www.go-hero.net/jam/15/regions
727人 https://www.go-hero.net/jam/14/regions
2019/04/12(金) 05:16:25.98
2012年〜2013年も700人前後だな
2012年〜2017年までの6年間ずっと700人程度しか出てなかったGCJに2019年に一気に300人も増えたのは驚くべき事態
2019/04/12(金) 05:49:03.04
競プロバブルかよ
2019/04/12(金) 05:55:31.99
まだバブルって程じゃないと思う
今の倍くらいまでは増えると思ってる
2019/04/12(金) 06:16:37.05
世界的にはそんな増えてない印象なんだよな
611仕様書無しさん
垢版 |
2019/04/12(金) 08:18:05.87
お前ら喜べ！
CSAcademyで明日の19時05分から3時間のdiv1相当のratedコンテストがあるぞ！！
CSAでの久々のratedだ！歓喜しろ！！！

https://csacademy.com/contest/fii-code-2019-final-round-online-mirror/summary/

FIICode Final Round [CSAcademy online mirror &#8212; rated]
https://codeforces.com/blog/entry/66473


ABCと時間が重なっているって？今回のCSAはdiv1相当だからAtCoder緑以下は出なくてよし！
612仕様書無しさん
垢版 |
2019/04/12(金) 08:24:36.02
今夜は21:20からyukicoderのコンテストあります

https://yukicoder.me/contests/219
2019/04/12(金) 08:35:59.70
コンテスト予定

今日
21:20 (2h) yukicoder contest

明日
10:00 (2h30) Google Code Jam - Round 1 A
19:05 (3h) CSAcademy - FIICode Final Round mirror (rated div1 all)
21:00 (1h40) AtCoder - ABC124 (rated ~1199)
23:05 (2h) Codeforces - Round #551 (rated div2 ~2099)

明後日
11:30 (1h30) LeetCode - Weekly Contest 132 (rated all)
20:00 (4h) AtCoder - square869120Contest #6


開催中
残り3日 CodeChef - April Challenge 2019 (rated all)

3日後
4/15 24:00 [4/16 0:00] (2h) TopCoder - SRM 755 (rated all)
2019/04/12(金) 08:47:41.94
>>611
うれション
615仕様書無しさん
垢版 |
2019/04/12(金) 10:26:50.72
コンテスト三昧だな
2019/04/12(金) 16:26:36.33
>>611
finalのmirrorだから
AtCoder青色の人でも苦戦しそう…
2019/04/12(金) 17:53:04.20
競技プログラミングの欠点は初心者が灰色から抜け出しにくいこと。
文系も入ってくるのにハードルが高い。
競技プログラミング参加者はそれでいいと思っていて
参加させやすくしようという意識が低い。
2019/04/12(金) 17:56:09.28
未経験者は本当に自分がエンジニアへの転職を目指すべきかよく考えてほしい - paiza開発日誌
https://paiza.hatenablog.com/entry/2019/04/12/%E6%9C%AA%E7%B5%8C%E9%A8%93%E8%80%85%E3%81%AF%E6%9C%AC%E5%BD%93%E3%81%AB%E8%87%AA%E5%88%86%E3%81%8C%E3%82%A8%E3%83%B3%E3%82%B8%E3%83%8B%E3%82%A2%E3%81%B8%E3%81%AE%E8%BB%A2%E8%81%B7%E3%82%92%E7%9B%AE
2019/04/12(金) 18:31:14.32
>>617
コンテストに出るだけでも偉い！とか茶色でも十分凄い！とかポジキャン？してるのはそれに対する苦肉の策だろうな
2019/04/12(金) 18:45:28.04
灰色から抜け出せないのは流石に本人の問題だろ
それを競プロの欠点っていうのはおかしいわ
2019/04/12(金) 20:18:09.62
文系だから青色は難しいというならわかるが、灰色抜けだせないってのは言い訳にならんよ
2019/04/12(金) 20:30:55.68
そうじゃなくて、競技プログラミングは競技プログラミングを知ったときから参加できず、
入門書なり数学なり回り道をしてから出ないと参加できない。
知識ゼロの奴らはくるなとか、
本人の努力不足と切り捨てているやつもいるしな。
2019/04/12(金) 20:32:40.29
標準入出力とか
与えられた数値の素早い取得とかの問題を作ればいいのに。
それができる前提の問題からがビギナー問題だからな。
2019/04/12(金) 20:33:18.36
できる奴らはハードルが高いという事がわかってない。
まさにできるやつはできないやつの何がわからないのか理解できない問題。
2019/04/12(金) 20:35:19.78
APG4bとかけんちょんさんの記事とか既に初心者向けのコンテンツは十分充実してるじゃん
何が不満なの？
2019/04/12(金) 20:50:05.55
知識ゼロは話にならんよ
練習せずに試合に来るやついないだろ
競技なんだからちゃんと練習しとけ
paizaとかABCの過去問とかなんぼでもただで練習・予習できるだろ
つべこべ言わずにやれ
2019/04/12(金) 21:18:01.90
このスレだけでも今の風潮がよくわかるよね
2019/04/12(金) 21:18:52.56
SRMのチャレンジフェーズで他人のソースコードコピペして手元で実行してるクソ野郎どれくらいいると思う？
2019/04/12(金) 21:39:36.29
コピペを悪いことだと思っていたり。
入門向けコンテンツが充実していると思いこんでいたり。
自分の目線からということが理解できてない人が多いね。
2019/04/12(金) 21:40:06.99
私の常識は世界の常識と
2019/04/12(金) 21:41:19.30
はっきり言いたいけど、コピペはいいことだよ。
2019/04/12(金) 21:43:00.72
まず問題として、全ての提出プログラムが異なっていなければならないというのは
もうすでにレベルが高いということがわかってない。
もう初心者の気持ちをすっかり忘れてしまっている状態。
2019/04/12(金) 21:43:59.56
自分ができるから、自分が苦労してきたから、
お前たちも同じ道を通れとは傲慢でしかない。
2019/04/12(金) 21:54:14.78
一連のレスは全部同一人物なのか？
初心者はプログラミングするなといってるのではないんだから、好きにプログラミングして自分のスキルを上げればいいだけのことだろう。
別に初心者が参加できなくても、プログラミング自体の間口を狭めている訳ではないぞ。

初心者だけどぼくも試験受けて点数もらって満足したい！とか、ただの自己満足でしかない。
適切な問題作るのも手間のかかることなんだから、他人に求めるのは虫が良すぎるかと。自分達で自分達のレベルにあった問題を作って評価しあう競技会を作ってもいいんだよ。
2019/04/12(金) 22:03:55.96
競技プログラミングは英語の試験で言えば英作文
いきなり英作文を解かせる先生がいるか？
まずはABC、発音、単語、熟語、文法と順を追って学習すべきなのに。
競技プログラミングの入門あたりにはそこらがごっそり抜けている。
他で頑張ってからこいと言う始末。
そりゃ競技プログラミングの人口は増えないよな。
2019/04/12(金) 22:12:49.74
>>629,631-632
SRMはあえてコピペできない仕様になってるんだが。。。
エアプが露呈したな笑
2019/04/12(金) 22:18:58.72
>>636
どこにSRMでとかいてあるんだ？

そもそもSRMを知らねーし。
途中で割り込んできてSRM上の話限定で
話してたかのような流れ作るのやめろ。
2019/04/12(金) 22:22:18.55
競技プログラミングで誰かが提出したプログラムを見て
それをコピペして提出しても問題ないという意味だがな。

そもそも動作確認しましたという意味で
提出してもなんの問題もないと思っている。
それは個人の実力の問題だからな。

なにか勘違いしてくるやつがいるとおもうが
公式ではだめだが、オンラインジャッジのヤツデ
提出するのならコピペで提出しても問題ないという意味だ。
そもそも通るかどおかのテストケースは自分の手でやるのは面倒だしな。
2019/04/12(金) 22:24:01.25
>>636
かってにSRMの話限定でのコピペ問題にしているのはお前。
2019/04/12(金) 22:25:33.75
>>636
詐欺師の手口じゃん。
2019/04/12(金) 22:32:08.90
本質でない話の中心から外れて、枝で引っ掛けさせるような。
2019/04/12(金) 22:38:26.06
小学生でもプログラミング教育が始まっているといのに
3割程度の競技人口増加で喜んでいる。
本来ならば、10倍、百倍になっていてもおかしくない。
なぜ増えないかと言うと、入口が極端に狭いからだ。
上に書いてあるように、英作文の問題は豊富だが
単語や熟語の問題がまったくない。
入門者用の問題が全く揃ってないのに、
古参の人たちはこれで十分だとのたまう。
全くお話しにならない。
2019/04/12(金) 22:41:25.95
文系さん一人で発狂してるね
2019/04/12(金) 23:12:05.54
ただの競プロアンチか、アンチはアンチスレ行ってね
645仕様書無しさん
垢版 |
2019/04/12(金) 23:34:08.60
うわー各種資格試験に毒された人だー
2019/04/13(土) 00:05:42.53
ABCのA問題で躓くような人は根本的にプログラミング向いてないから他で頑張ったほうがいいよ
2019/04/13(土) 00:47:06.96
>>642
名前しか書けないような受験者をカウントして100倍になったと言ったところで、それが競技プログラミングが普及したということにはならんだろう。むしろバカな水増しアピールでしかない。
まっとうに取り組む参加者が3割り増えたなら、それは着実な進歩だよ。

君のレスを見てると、結局のところ｢僕が参加できないのがヤダヤダ｣という不満にもっともらしく理由をつけようとしている(上手くいってはいない)だけにしか見えない。
2019/04/13(土) 00:51:56.94
>>642
人口が増えない理由としては、難易度がどうこうというより、単純に知名度が低いとか、多くの社会人にとって継続的に時間をとることが難しいとかだろう。
現在の難易度で入り口が極端に狭いと感じるなら、問題の方が難しすぎるのでなくお前さんがスタートラインの遥か後方にいるというだけのことだ。
2019/04/13(土) 01:50:07.92
APG4bとABSじゃ不満なの？
2019/04/13(土) 03:19:34.53
ちくわ大明神
2019/04/13(土) 03:25:49.36
この手の荒らしって何故かゴミみたいな比喩よく使うよね
まあでも入口が狭いって主張には否定できない部分もあって
プログラミング以前の、例えば「方程式x-a＝0を解け」ってだけの数学の問題でも文字で表される定数が答えに出てくる高校数学だから、高校数学が全く分からないって人は門前払いになるはず
ただ、そこの教材までAtCoder社が提供し出したらもはや競プロの会社ではなくなるよね
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況