競技プログラミングにハマるプログラマのスレ 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/02/27(水) 15:11:09.52
>>204
アルゴリズム知らなくても算数が得意な人にはそうなるかも
2019/02/27(水) 17:03:03.74
数学系の大学生の方が有利ってのはあるな
行基本変形をしたら解ける問題が高難易度に出題されたりとかするみたいだし、線形代数などの知識は有って損がない
2019/02/27(水) 17:05:07.99
なんでkaggleと競プロってマウントに差があるの？
2019/02/27(水) 17:06:27.43
というか情報科学はほとんど数学だし、有名なプログラマーもほとんど数学とか物理専攻ダッタ
2019/02/27(水) 17:29:16.20
線形代数やったけど競プロで全然使わないわ、使う域までいけない
精々行列累乗ぐらい
2019/02/27(水) 17:34:55.49
線形代数って数学物理の得意技じゃなくて理工学系の得意技だよエアプさん
2019/02/27(水) 17:59:14.96
理工学部で線形代数やっててもxorをmod 2の連立方程式とみなして行列で扱うとか思いつかないんだよなぁ
2019/02/27(水) 18:27:14.87
全ては慣れたらできる
2019/02/27(水) 20:49:55.63
マラソンをやってるのですが、貪欲や簡単な焼きなまししかできず終わってしまいます
上位陣のコードを見てもなにやってるか理解できません
こういう場合、マラソンの能力をどうやってあげていけばいいですか？
2019/02/27(水) 22:55:46.89
>>64の日本オンサイトの詳細とリーダーボード(空)
各部門20人ずつ招待らしいぞ

https://tco19.topcoder.com/regional-events/tco19-regional-event-japan
2019/02/27(水) 23:20:01.46
マラソンerたちが書いてる記事は読んだりしてるの？
2019/02/27(水) 23:36:33.71
競プロもマラソンもレッドコーダーと自身を比較するのはあまり意味がない
2019/02/28(木) 00:55:06.60
>>213
見ているのは上位陣のコードだけ？上位陣のツイッターでの語りは見てないの？
2019/02/28(木) 00:56:43.33
マラソンも競プロも問題数をこなすことが上達への近道
頑張るしかないんだよ
2019/02/28(木) 01:21:07.65
Codeforcesのコンテストって難易度の高いほうの問題はあまり解かれないようだしテストケースガバガバで嘘解法が通ったりしないの？
220仕様書無しさん
垢版 |
2019/02/28(木) 02:37:29.22
わりとチャレンジ成功してるの見るけど境界値とかなのかな
221仕様書無しさん
垢版 |
2019/02/28(木) 18:54:02.19
>>213
上位がそのコードに辿り着く思考プロセスを知りたいね
2019/02/28(木) 21:14:05.75
3月はABCなしAGCあり
すなわち3月は過去問埋めで精進しよう月間
2019/02/28(木) 21:17:21.47
3月に精進して4月に新色で新学期デビュー
2019/02/28(木) 21:36:18.82
流石にABC挿入してくるでしょう
それより自分が水色になってから一度もARCが開催されてねえや
ARC相当の企業コンはあったけど
2019/02/28(木) 23:32:08.56
最後のARCは去年の9月末か
2019/03/01(金) 08:44:53.02
>>224
俺もそうだし、そういう人は割と多くいそう
春から夏休みにかけて始めて半年で水色になるとそうなるし
2019/03/01(金) 09:43:35.71
ＡＧＣでレートあげ！あげ！
2019/03/01(金) 14:28:45.34
かれこれ60回ぐらいコンテスト参加してるけど、参加2回目ぐらいの頃のAGCが今までで一番パフォーマンス高いわ
2019/03/01(金) 16:17:48.78
AtCoder地頭要素強いから精進の効果がなかなかレートに現れにくいんだよね
2019/03/01(金) 17:37:49.38
だから僕はいつまでも灰色
2019/03/01(金) 17:56:10.17
灰→茶という最初の一歩の時点で
ABCのAB早解きかC遅解きくらいは求められるから
相当人を選ぶコンテンツには違いない
2019/03/01(金) 18:08:26.25
＞いつまでも灰色

ありえん
いつまでも茶色ですらありえん
2019/03/01(金) 18:40:17.57
お前ら青ぐらいあるの？
緑は恥ずかしくねーよなんて言われても劣等感結構ある…早く水色になりたい
2019/03/01(金) 18:46:22.44
文系の妻ですら無精進で茶色になれるというのに
2019/03/01(金) 19:07:56.65
topcoderなら青なんだがな

atcoderの方が難しいらしいし、換算すると緑くらいかな
2019/03/01(金) 19:18:29.08
ちなみにAtCoder副社長は緑と茶の間くらいだったりする
2019/03/01(金) 19:48:31.70
RCOハーフマラソン
予選トップページにはuwiさんの名前があるのに本戦トップページにはないね
2019/03/01(金) 20:17:20.27
>>236
副社長って有名なコーダーなの？
239仕様書無しさん
垢版 |
2019/03/01(金) 20:24:56.40
https://akensho.hatenablog.com/entry/2018/06/02/000100
2019/03/01(金) 22:49:41.82
ABC生えた


3/2(土) 14:00 第3回 RCO日本橋ハーフマラソン 本戦
3/2(土) 14:00 第3回 RCO日本橋ハーフマラソン 本戦 (オープン)
3/3(日) 21:00 AtCoder Beginner Contest 120
3/9(土) 21:00 AtCoder Grand Contest 031
3/16(土) 21:00 AtCoder Grand Contest 032
241仕様書無しさん
垢版 |
2019/03/02(土) 00:26:03.46
灰色の人
競技プログラミングやる前に検索する力を身につけたほうが良いのでは?
2019/03/02(土) 00:26:51.00
1時間半後からCodeforcesでQ#コンテストだよ
2019/03/02(土) 00:30:35.69
灰色の人たちはこれらを何も参考にせずに全完できるまで練習した？

AtCoder Programming Guide for beginners (APG4b)
https://atcoder.jp/contests/APG4b

Introduction to Programming I
http://judge.u-aizu.ac.jp/onlinejudge/topic.jsp?cid=2
2019/03/02(土) 04:03:25.82
ただのUnionFindはすらすらかけるけども
頂点に重みつけたりだとかポテンシャル持たせるとか永続させるとかになると手が止まる
どうすりゃいいんだ
2019/03/02(土) 04:15:44.58
ライブラリ化しとけば良いじゃん
2019/03/02(土) 04:45:42.39
>>242
touristも参加しているぞ
2019/03/02(土) 18:58:59.45
>>244
そういうのを予備知識なく実装できるのは雲の上の人
わかるまで人のコードをみて勉強するといいよ
2019/03/02(土) 23:07:49.35
灰色の僕
明石高専の人達が水色で嫉妬
僕は20代後半
2019/03/02(土) 23:13:03.15
灰色や茶色なら、
if for とかのプログラミング入門とか
標準入出力を知ればクリア

アルゴリズムとか関係ないな
2019/03/02(土) 23:29:34.86
そもそも明石高専行ってる奴そこそこ優秀だから
凡人のおっさんが負けるのも仕方ないよ
2019/03/02(土) 23:32:03.32
>>249
実際最大値を求める方法とかは知らないと解けないと思う
定義通りに実装するとO(n)になるし
2019/03/02(土) 23:32:36.86
>>251
誤射
O(n^2)
2019/03/02(土) 23:38:20.11
最大値求めるのにO(N^2)ってどうやんの
O(NlogN)しか分からないっていう初心者はいるかもだけど
2019/03/02(土) 23:40:21.96
そもそも高校生で赤とかいるから…年齢とレートを並べるのは駄目よ幸せになれない
2019/03/02(土) 23:46:10.42
灰色って最大値をO(n)で求める方法も知らなきゃ書けない人種なのか
FizzBuzzを空で書けない人間とほぼ同種やん
2019/03/02(土) 23:50:33.86
クイックソート最悪ケースじゃないよな？
定義通りって愚直に全要素探すだけならO(N)だし
257仕様書無しさん
垢版 |
2019/03/03(日) 00:41:02.95
この前灰パフォとっちゃったんだけど多分灰の人間は競プロじゃなくただのプログラミングをやってんだと思う
例えばこの前のABCで文字列比較じゃなくよく知らない標準ライブラリのyyyyMMddフォーマッターを使おうとしたり
違うかな
2019/03/03(日) 00:41:49.84
最大値をO(N)で求めるのは動的計画法
259仕様書無しさん
垢版 |
2019/03/03(日) 00:54:20.05
配列の最大値のことをいってるの？
o(n^2)の発想がよくわからん
普通に1回ループ回せば終わらね？
2019/03/03(日) 01:06:09.41
Aの最大値 = Aの要素であって、Aの任意の要素より大きいか等しい
これを素直にやるとO(n^2)
2019/03/03(日) 01:11:39.61
ああなるほど、確かにO(N^2)だわな
授業で習ったmax(A, B, C, ...)=max(A, max(B, max(C, ...)))しか出てこなかったわ
2019/03/03(日) 01:20:56.57
//入力略a[0],…,a[n-1]に値が入ってる

int mx=a[0];

for(int i=1;i<n;i++){
mx=max(mx,a[i]);
}
--------------------------------

int mx=-1;
for(int i=0;i<n;i++){
bool f=true;
for(int j=0;j<n;j++){
if(a[i]<a[j])f=false;
}

if(f){
mx=a[i];
}
}

この二つって結果かわるの？
2019/03/03(日) 01:21:30.24
スペースも消えるのか…？
2019/03/03(日) 01:22:15.74
ていうか検索してmaxelementにたどり着けないのか
2019/03/03(日) 01:25:04.00
というかアルゴリズム考える競技ではあるけど
用意されてるものは使うって考えもってないのはもったいない気がする
2019/03/03(日) 01:26:39.14
「c++ 配列　最大値」で検索することができないって
本気で心配になるんだけど、普段の生活どうしてんの？
2019/03/03(日) 01:33:57.92
言い過ぎた。ごめんなさい。
2019/03/03(日) 01:59:29.64
検索能力が劣る人も世の中には存在するから……
「配列の一番大きい値を求めるにはどうすればいいですか」とか検索をかけている可能性もありそう
このケースならこれでも答えには辿り着くけど、設問をコピペされたら流石に答えでないわな
2019/03/03(日) 02:35:03.21
君ら生まれた時からSTLマスターしてたり検索の仕方知ってたりするのかね
2019/03/03(日) 02:41:33.29
なるほど、qiitaの辞典みたいなまとめも
個別に調べられない人間には重宝してるのか
2019/03/03(日) 07:35:25.07
最大値でループ一回ってのが思いつかない時点で異常

プログラミングの入門書に一度は目を通すべき
2019/03/03(日) 08:41:05.90
「全国統一模試」やってるのと実質的にはおなじことなので
おっさんでこの世界に飛びこんで来た人はそのころのことを思いだせばよい
2019/03/03(日) 08:50:33.94
学校なんかだと(調べて答えなさいと言われたものを除いて)
与えられた課題を検索して答えるのは悪としてその方法についても一切触れないから
検索能力の著しく低い人がそこそこいるんだろう
後は「検索して答えを出した」と「ちゃんとやった」が結びつかない人々
2019/03/03(日) 09:54:31.00
検索してそれを自分の知識にすることが重要なんだろ
2019/03/03(日) 10:12:47.67
最近のABCdrafearさんのばっかりだな
他に作問する人いないのかなぁ
2019/03/03(日) 12:38:07.36
赤色の人はABCの問題作りたいと思わなそう
2019/03/03(日) 12:44:58.26
オレンジの人で作問したい人あんまりいないのかな
2019/03/03(日) 20:18:02.64
競プロ強くても作問能力が高いとは限らないからね
2019/03/03(日) 20:59:38.35
個人の発想は有限ですし
2019/03/03(日) 21:44:32.30
難易度低めの速解き回
2019/03/03(日) 22:17:14.49
コンテスト終わってないのにそういうこと言うなって……
2019/03/03(日) 22:46:21.77
参加者多いな
2019/03/03(日) 22:55:31.37
unionfind使って逆順にすればいいのわかったけどそこから何やればいいかわからなかった
c愚直に文字列でやろうとしてTLEして方針転換した時には遅かったし最悪
2019/03/03(日) 23:25:11.85
前回のC300点と差がありすぎ
2019/03/03(日) 23:55:00.96
union find持ってない人は、spaghetti sourceあたりからコピペで
2019/03/04(月) 00:07:49.90
大学でdisjoint setって習わないの？
2019/03/04(月) 00:08:41.74
データ構造貼るだけの奴おもしろくないから嫌い
2019/03/04(月) 00:11:36.39
やっぱ制限時間あるなかでやるの楽しいな
公式でバチャコンやってくれんかな
2019/03/04(月) 00:26:25.07
>>286
情報系だったけど講義ではやらなかったよ
2019/03/04(月) 00:35:49.68
うちもやってないわ
簡単なデータ構造とグラフと動的計画法教えられた後はOSとかコンパイラ作らされた記憶
年々教えること変わってるらしいからもしかしたらやってる年あるのかもしれんが
2019/03/04(月) 00:44:00.27
競プロローカルなのかー
2019/03/04(月) 00:49:33.87
限られた講義時間の中で教える優先度考えたらそりゃなあ
2019/03/04(月) 00:57:50.43
クラスカル法もやらないのか？
2019/03/04(月) 01:20:08.08
クラスカルとプリムはやったがアルゴリズムの正当性だけ教えて連結性判定の効率的な実装方法は教えてなかった記憶
2019/03/04(月) 01:49:56.31
ところでUnion-Findは「データ構造をマージする一般的なテク」でもできます
296仕様書無しさん
垢版 |
2019/03/04(月) 02:06:09.20
今回の放送で出てた根の親を（-要素の数)にするやつってrank管理する奴の完全上位互換じゃね
分かりやすいしサイズ取れるし
2019/03/04(月) 02:21:50.09
わかりやすさ重視するなら親を指す配列とサイズの配列の２つ持った方がよくね
初期値-1のUnionFindは正負で値の持つ意味変わるし
298仕様書無しさん
垢版 |
2019/03/04(月) 14:16:38.04
ツイッターみてたら昨日のb読み間違えてる奴多すぎて草
私もです
2019/03/04(月) 18:21:53.40
入出力例1だけ見ても間違いに気付かないからなw
昨日は何も考えずに約数を列挙してソートしたが、よく考えたら牛刀割鶏だな
2019/03/05(火) 17:28:28.16
無限ループのスクリプトを組んだ厨房が逮捕だってさ
これからはTLEするごとに警察が飛んできたりして…
2019/03/05(火) 18:19:31.88
無限ループによるTLEだとしたらチェックが甘過ぎるから仕方ない
2019/03/05(火) 19:58:16.34
無限ループを書いたことを無いものだけが石を投げなさい
2019/03/05(火) 20:17:34.04
無限ループをサブミットしたことはないから石投げて良いすか
頭蓋骨割ってやるよ
2019/03/05(火) 20:18:24.88
マラソンマッチってなんで高々100人くらいしか参加者来ないのに毎回サーバの準備して問題作ってってやれるんですか？

空虚さ感じないんですか？
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況