競技プログラミングにハマるプログラマのスレ 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/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人くらいしか参加者来ないのに毎回サーバの準備して問題作ってってやれるんですか？

空虚さ感じないんですか？
2019/03/05(火) 20:51:23.63
その過去問を見て勉強する者の数は膨大
未来永劫に増加しまくり
2019/03/05(火) 21:08:50.04
>>304
趣味に空虚さ感じるものなの？
盆栽なんていつか枯れるし金と時間かけるだけ空虚な趣味なの？
囲碁や将棋はプロになれないなら空虚な趣味なの？
ソシャゲなんてただのデータだしいつかサービス終了するから空虚な趣味なの？
ツイッターも５ｃｈも永遠に続くサービスじゃないし書き込みなんて空虚じゃないの？
2019/03/05(火) 21:59:25.30
>>306
いや、topcoderは会社だぞ……？笑
2019/03/05(火) 22:48:55.08
Div1Hardってなんで高々10人くらいしか解かないのに毎回サーバの準備して問題作ってってやれるんですか？

空虚さ感じないんですか？
2019/03/05(火) 22:54:47.33
不毛な煽りにいちいち付き合うなよ…
2019/03/05(火) 23:04:26.40
>>308
いや、上位層の順位って hard の出来で決まってるとこあるじゃん……？笑

hardは解けなくてもチャレンジできるし、存在意義かなりあるよ
なくなったらゲーム性変わる
2019/03/05(火) 23:46:18.97
ABC/ARC/AGCは赤字コンテストって言ってたけど空虚なの？
2019/03/06(水) 00:10:14.68
>>311
空虚だね
数年後にはSRMより回数減ってると思うよ
2019/03/06(水) 00:29:08.46
数年後にtopcoderは存在してないだろう
2019/03/06(水) 03:41:34.17
トップコーダーのカレンダー見てるんだが、TCO19 algorithm round 1A とか 1B とかいうやつは普通に誰でも参加できる rated コンテストだと思ってオーケー？
2019/03/06(水) 06:59:56.00
どちらともratedだが年齢制限が違ったような
SRMは13歳以上
TCO Algorithmは18歳以上
2019/03/06(水) 07:05:23.95
>>315
ありがとう
2019/03/06(水) 08:12:28.02
去年は18歳未満や次Round進出確定者などの当該Roundに参加資格ない人がratedも楽しめるように
TCO AlgorithmのRoundと同時に同じ問題のFunRoundも開催されてる

https://www.topcoder.com/tc?module=MatchList
例えば
TCO18 Fun 1A 04.21.2018
2018 TCO 1A 04.21.2018
318仕様書無しさん
垢版 |
2019/03/06(水) 19:20:06.86
今夜21時からSRMだぞ！人権SRMだ！

さらに日本人同士で東京オンサイト出場権の獲得競争だぞ！( 詳細 >>64 >>214 )

お前ら！東京で会おうぜ！
319仕様書無しさん
垢版 |
2019/03/06(水) 19:38:39.47
このオンサイトはSRMとMMそれぞれから日本人が20人招待されるんだぞ！もっと盛り上がれよ！
2019/03/06(水) 19:49:47.75
>>313
chokudai的には企業向けコンテストへの興味の方が強そうだしなぁ
2019/03/06(水) 19:54:42.86
>>319
マラソンのコンペティター日本に20人もいないだろって感じなんだが
322仕様書無しさん
垢版 |
2019/03/06(水) 20:48:17.59
トップコーダーやっぱりやり方がいまいちわからんな
2019/03/06(水) 22:21:00.26
>>321
SRMのアクティブ日本人213人
MMのアクティブ日本人78人

どちらも20人以上はいる

ソース
https://community.topcoder.com/stat?c=country_avg_rating
https://community.topcoder.com/longcontest/stats/?module=CountryRank
2019/03/06(水) 22:53:38.48
>>323
アクティブで78人もいるんだな
でも20位らへんの人らは相当レベル低そう
2019/03/06(水) 23:54:42.51
イエローコーダー様たちをレベル低そうだなんて貴様何様のつもりだ！
2019/03/07(木) 00:40:14.51
>>324
彼らのレベルを低いと思える君ならMMで東京オンサイト権獲得も余裕だろう
2019/03/07(木) 01:21:57.99
それは余裕だと思う

行かないけどね
2019/03/07(木) 04:48:38.22
AGCが23時になるとか聞いてない
2019/03/07(木) 05:43:41.23
MMのレートは参考にならない
さすがにレッドは強いと思うが
2019/03/07(木) 06:06:01.60
>>329
その週空いてるか、で強さ決まるよな
2019/03/07(木) 06:39:45.20
>>319
SRM/MMだけじゃなく
Development/Design/QA+F2Fからも各20名ずつ
Development/Design/QA/F2Fは日本人参加者ほとんどいないから
プログラマーならDevelopment参加で余裕で行ける
2019/03/07(木) 06:50:36.03
>>64>>213のTCOリージョナルの順位は何故かCodeforcesで発表されている
https://codeforces.com/blog/entry/65731
2019/03/07(木) 15:49:39.44
そろそろセグ木を覚えて次のステージへと進みたい
334仕様書無しさん
垢版 |
2019/03/07(木) 16:36:03.80
上級者はセグ木を秒で実装できるってマジ？
2019/03/07(木) 17:33:55.73
過去にＡＣしたコードをコピペね
2019/03/07(木) 18:09:00.89
セグメントツリーってSRMじゃDiv1 med 以上でしか使わんだろ
2019/03/07(木) 20:09:02.03
セグ木の次のステージってなんぞ
2019/03/07(木) 20:21:24.65
平衡二分木じゃない？
2019/03/07(木) 23:02:30.30
蟻本中級の知識問題を処理できるレベルになりたいって意味では
2019/03/07(木) 23:30:18.32
短いコンテストでよく出る蟻本知識ってどんなだろうな
典型過ぎるものはもはや出んからなぁ

二部マッチングとかはできてほしいね
でもこれは初級なのかな
2019/03/08(金) 16:00:22.81
土日コンテストとかやる気出してきたな
2019/03/08(金) 17:56:26.33
次のＡＧＣは２３時からかよ
2019/03/08(金) 20:09:18.24
開始時刻 コンテスト名
3/9(土) 21:00 AtCoder Beginner Contest 121
3/10(日) 13:00 早稲田大学プログラミングコンテスト2019
3/10(日) 23:00 AtCoder Grand Contest 031
3/16(土) 21:00 AtCoder Grand Contest 032
2019/03/08(金) 20:38:12.81
毎月これくらい出してほしい
2019/03/08(金) 21:48:57.64
どうして急にやる気出してきたんだ？
2019/03/08(金) 22:24:20.89
今までは企業コンが多かっただけでコンテストの頻度はそんな変わってなくない？
2019/03/08(金) 23:43:01.89
AtCoderって一年通した平均のコンテスト回数はちょうどいいんだけど、疎密があるのが難点
2019/03/09(土) 13:44:24.47
開始時刻 コンテスト名
3/9(土) 21:00 AtCoder Beginner Contest 121
3/10(日) 13:00 早稲田大学プログラミングコンテスト2019
3/16(土) 21:00 AtCoder Grand Contest 032
3/23(土) 22:00 AtCoder Grand Contest 031
2019/03/09(土) 13:46:50.93
なんでAtCoder公式サイトを見れば分かることをいちいちこっちにコピペしてんの？
2019/03/09(土) 13:47:47.28
atcoderの同人気質を感じる
2019/03/09(土) 14:09:17.93
AGC延期しちゃったのか
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。