競技プログラミングにハマるプログラマのスレ 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/
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社が提供し出したらもはや競プロの会社ではなくなるよね
2019/04/13(土) 04:04:51.73
そもそも英作分みたいな色んな能力が求められるのE問題以降だし、そういう青以上のスキル求めてる会社ってほんの一部だよ
2019/04/13(土) 05:36:04.66
atcoderに限った話してる時点でお察し
どう見てもchokudaiとかのアンチです
2019/04/13(土) 08:04:15.35
AtCoder社は試験しかつくってないからな

グダグダ言ってる人は塾がほしいって言ってるんだろ
手取り足取りハメこんで金絞りとってほしいと言ってるんだ
2019/04/13(土) 10:54:49.79
AtCoderの話なら、そもそもこれ以上人数は増やせないしな
この前の4000人参加の時にジャッジが2分詰まってたし
ジャッジサーバーも金掛かるから、現状じゃこれ以上来られても困るだろ
656仕様書無しさん
垢版 |
2019/04/13(土) 12:43:59.99
企業から金貰って企業コン増やせ
2019/04/13(土) 13:52:43.84
企業コンが増えたら問題難易度が上がるけどな
企業が欲しいのは強い人材であって、灰や茶で停滞するような学習意欲の無いゴミじゃないから
2019/04/13(土) 14:02:32.61
30歳の赤コーダーって転職有利なの？
2019/04/13(土) 14:12:19.91
AGCレベルの企業コンはほとんど無いし、企業コンが増えたらトップ層的には問題難易度下がるんじゃね
強すぎる人材は逆にあまり求められてないという
2019/04/13(土) 19:23:48.12
競プロの面白さの本質が理系や高学歴にしか理解し得ないと思ってるので
入り口を広くすることは根本的な解決にならないと思う
まあそれでもABCなんかで例えば「N要素の数列が与えられます」を
「N個のデータが与えられます」と言い換えるみたいなのはあってもいいかもしれないけど
(「数列が与えられる」って、初めて見たら面食らわない？)
2019/04/13(土) 20:02:30.70
Google Code Jam 2019 Round 1A Stats
https://codeforces.com/blog/entry/66518

通過した154人の皆さんおめでとうございます
2019/04/13(土) 20:11:29.65
>>660
データというより数列のほうがより意味が厳密で紛れが無いのでそこは変えないでほしいな
数学の言葉に最初から落とされているほうが翻訳のコストが減らせるのでそういう意味でも好ましい
2019/04/13(土) 20:56:11.27
プログラミングとか言ってるが実態は数学ゲーム
もっと窓口狭くてもいい
2019/04/13(土) 21:53:32.80
今回のＡＢＣは珍しくどれも優しい問題で全完できた
2019/04/13(土) 22:51:47.11
全完おめでとう
2019/04/13(土) 23:27:13.83
自力で解いたはずなのに解説の意味がわからないこと、あると思います
2019/04/13(土) 23:42:51.56
解説のコードなら頑張って読むけど、人のコードなんて基本的に読みたくないからな
2019/04/14(日) 01:08:13.40
HackのあるCodeforcesやSRMでは他人のコードを見ないと得点稼げない
669仕様書無しさん
垢版 |
2019/04/14(日) 03:04:39.23
簡単すぎて早解きゲーになってるやん
2019/04/14(日) 04:18:47.62
bitDPでパスを列挙するとき、既に訪れた頂点の集合 S と最後に訪れた頂点 i について i に至るまでのパスの数として dp[S][i] と状態を持つのが基本だ

このとき、どの始点から出発したかという情報を後で使いたいならば、dp テーブルの次元として新たなものを追加するしかないよな？
言い換えると、dp[S][i] から「頂点 j から出発して頂点 i に至るパスの数」を知ることは不可能だよな？
2019/04/14(日) 04:21:27.29
>>668
コピペして手元で実行してるとしか思えない爆速ハッカーもたまにいるけどな
2019/04/14(日) 08:00:04.97
>>670
それはそう
2019/04/14(日) 12:29:49.84
手元で実行したらいけないの
2019/04/14(日) 12:45:09.88
hackのコピペってどうやるの？
2019/04/14(日) 12:45:37.88
>>673
ウーン、あえてコピペできないUIになってるからなぁ
でもコピペを禁止するルールは案外なかったりして
SRMのルールなんか一回たりとも読んだことないからあったらスマソ
2019/04/14(日) 13:44:22.67
SRMは知らんがCodeforcesではHackのためにコピペしたり機械的に読み取ったりするのは禁止されてる（ECRは別）
コードを写経して手元で実行するのはOK
2019/04/14(日) 23:24:40.58
SRMでも禁止されてるよ
2019/04/15(月) 20:20:13.23
海外のコンテストの英語の問題文を読むのがつらい。
chromeの翻訳もMathMLが崩れて読みにくいし、どうすればいい？
2019/04/15(月) 21:15:01.08
英語力を上げる一択だろ常識的に考えて
2019/04/15(月) 21:23:06.04
英語力は必須か。
TopCoderやCodeforcesをやってる人多いけど、英語ができる人は多いんだな。
2019/04/15(月) 22:58:09.46
海外コンテストに30回以上も参加すると英語問題文に抵抗はなくなってきた
2019/04/16(火) 02:34:30.80
「TCO19 algorithm round 1A」ってただの SRM div1 相当の難易度の rated イベントだと思って良いですか？
2019/04/16(火) 03:08:47.92
TCOのRound1はDiv2より少し難しいくらいのはず
2019/04/16(火) 03:31:20.27
>>683
div1より楽なんですか？
だったらやるっきゃないですね
2019/04/16(火) 23:36:50.95
昨日のSRM、div2mとdiv1eが同じだったんだな
いつもこんくらいの難易度だったらdiv1eの早解きできるのに
2019/04/17(水) 19:46:41.64
ようやくABCの配点が変わるのか
今までDに300~450ぐらいのを全部押し込んで来てたし良い改変
2019/04/17(水) 20:03:04.75
古いコンテストの問題を現在の難易度基準での配点表示できるUserScriptが望まれる
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況