X
競技プログラミングにハマるプログラマのスレ 11 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
0001仕様書無しさん
垢版 |
2017/06/22(木) 22:18:06.15
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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にテンプレ続く
0145仕様書無しさん
垢版 |
2017/06/29(木) 20:02:02.28
どう見てもオンラインジャッジであって
それ以上何が知りたいのかエスパー使いじゃないから不明
0147仕様書無しさん
垢版 |
2017/06/29(木) 22:07:59.95
>>142
強い人らの名前が連なっているけど
スコア的に早々にみんな利用を止めているという感じ？
問題の質か何かが悪かったのか
0148仕様書無しさん
垢版 |
2017/06/29(木) 22:21:49.12
あんたさんってニートじゃなくて大学生だったのか…
0150仕様書無しさん
垢版 |
2017/06/29(木) 22:43:14.85
>>142,147
ICPC WFの問題がそこで同時(?)公開されるから、パラレルで解くときに使うところ
0155仕様書無しさん
垢版 |
2017/06/29(木) 23:14:44.03
touristがいて勝ち目が薄いからchokudaiは棄権した？
0157仕様書無しさん
垢版 |
2017/06/29(木) 23:55:09.36
AtCoderの知名度を上げる必要があるのかもしれんが
炎上で知名度を上げるやり方は個人的には好きじゃない
0158仕様書無しさん
垢版 |
2017/06/30(金) 00:13:23.28
「本の内容が難しくて理解できない」→「著者にとっての想定読者ではない」→「想定読者になるには何を勉強したらよいのか？」
0159仕様書無しさん
垢版 |
2017/06/30(金) 00:14:25.46
エロコンテンツへの言及は知名度意識してそう
彼女募集は本心(あからさますぎ)
元カノ話は仲間内の下ネタのつもりで常識のなさが露見(永遠にネタにされる元カノｶﾜｲｿｽ)
0165仕様書無しさん
垢版 |
2017/06/30(金) 04:00:46.24
システムテストを待つよりは早く間違いが分かるからHACKされてよかったじゃねーか
0167仕様書無しさん
垢版 |
2017/06/30(金) 04:03:22.14
hack時間中に普通にEditorial出たりするいいんじゃないの
0168仕様書無しさん
垢版 |
2017/06/30(金) 04:10:34.51
つまり正解分からなかった人でも不正解コードを探して潰せるHACK体験が出来るのか
0172仕様書無しさん
垢版 |
2017/06/30(金) 04:53:34.51
step_by_step氏は黄色コーダなのにunratedなのにHACKしまくるのはどんな理由からなんだろうか
0174仕様書無しさん
垢版 |
2017/06/30(金) 05:05:43.88
HACKしまくってるstep_by_step氏とsatyaki3794氏はもしかして自動ツールでHACKしまくってる感じか
0176仕様書無しさん
垢版 |
2017/06/30(金) 08:54:50.64
某氏、怒りのアカウント作ってらっしゃったのね
0178仕様書無しさん
垢版 |
2017/06/30(金) 17:09:19.57
20時からSRM
0179仕様書無しさん
垢版 |
2017/06/30(金) 17:49:30.71
えっちいことにオープンな間柄だったからといって
別れた後まで暴露していいと本気で考えてるなら怖い
0181仕様書無しさん
垢版 |
2017/06/30(金) 19:03:37.21
*****
Topcoder,Codeforces,AtCoder,CSAcademy,CodeJam,CodeFestival

****
CodeChef,HackerCup,ProjectEuler,CodinGame,BestCoder,CodeVS
OnlineJudges(for ICPC by University)(e.g. AOJ,PKU,UVaOJ,URIOJ,etc...)

***
HackerRank,LeetCode,HackerEarth,SamurAIcoding,yukicoder,CoderByte
OnlineJudges(e.g. SPOJ,etc...)

*
paiza,CodeIQ
0189仕様書無しさん
垢版 |
2017/06/30(金) 23:50:01.36
競プロが普及してるのは偏差値の高い学校ばかり
0190仕様書無しさん
垢版 |
2017/07/01(土) 00:22:59.42
yukicoderいつもより少し順位がいいと思ったら
参加者が少なかったでござる
0193仕様書無しさん
垢版 |
2017/07/01(土) 00:44:12.77
こどふぉのEducationalのHACKの時間が終わったらHACKのケースがテストケースに追加されてリジャッジされたりするの？
0195仕様書無しさん
垢版 |
2017/07/01(土) 09:08:02.73
こどふぉはHackがあるから発覚しやすいだけで
yukicoderやAtCoderも実はジャッジ解間違ってましたなんてことがあるのかもね
0199仕様書無しさん
垢版 |
2017/07/01(土) 22:51:40.68
コンビネーションって再起つかわざにパスカルの木っ計算できる?
0200仕様書無しさん
垢版 |
2017/07/01(土) 23:01:29.91
パスカルの木で組み合わせを計算するのは、メモリ食うのと、時間計算量もかかるので、nが小さいときに限られると思う。

階乗と逆元とを計算しておく方式がオススメ。
0201仕様書無しさん
垢版 |
2017/07/01(土) 23:08:02.93
パスカル使っても今回は10^10オーダーのサイズの配列が必要になるから解けない
C(a,b) = a! / (b!(a-b)!) = a! * (b!)^-1 * ((a-b)!)^-1 だから階乗とその逆元の配列を事前に計算しておけばO(1)でできるよ
0205仕様書無しさん
垢版 |
2017/07/01(土) 23:15:02.38
何が分からんのか
1. C(a,b) = a! / (b!(a-b)!)
2. a! / (b!(a-b)!) = a! * (b!)^-1 * ((a-b)!)^-1
3. 階乗とその逆元の配列を事前に計算しておけばO(1)
0207仕様書無しさん
垢版 |
2017/07/01(土) 23:42:52.33
すっごーい！
0208仕様書無しさん
垢版 |
2017/07/01(土) 23:47:52.10
JOI予選がAtCoderであるらしいけどこういう場合はお金取るのかな
0209仕様書無しさん
垢版 |
2017/07/02(日) 00:17:28.72
Eは解答の方法でもx毎にO(n)かかるので、O(n^2)かかるような・・・orz
0213仕様書無しさん
垢版 |
2017/07/02(日) 01:10:33.71
210はDと勘違いしている
Dならkごとにコンビネーションの計算2回だからO(n)
EもO(n)かO(n log n)
0215仕様書無しさん
垢版 |
2017/07/02(日) 02:05:21.89
>209
>213
Eは、前処理で累積和の計算をしておけば、x毎にO(1)で済むから、O(N)
累積和の前処理は、操作前の明るさと操作後の明るさで張られる2次元平面上の、重み付けされた三角形が対象。
1つずらした位置との重み付けした三角形との差分を取ると、
重み付けした線分上（操作後の明るさ一定の方向）の累積和と、重みなしの三角形の累積和があれば良いことになる。
重みなしの三角形の累積和は、さらに差分をとると、水平方向と垂直方向の、決まった範囲の和に分解できる。
これらの前処理は、O(N+M)で出来る。
なので、全体でO(N+M)
0216仕様書無しさん
垢版 |
2017/07/02(日) 02:21:08.68
touristのチーム破って優勝とかantaさん&hogloidさんチームつええな
0219仕様書無しさん
垢版 |
2017/07/02(日) 02:40:20.85
the name of 'anta', a young Japanese hobbyist programmer from Japan who is some kind of a legend.
0220仕様書無しさん
垢版 |
2017/07/02(日) 03:03:43.56
システムテストのないAtCoder形式だと誰が優勝なのかのワクワク感が薄い気がする
0221仕様書無しさん
垢版 |
2017/07/02(日) 03:14:13.58
個人的にはhackも凍結も嫌いだからAtCoder形式がベスト
0222仕様書無しさん
垢版 |
2017/07/02(日) 03:21:34.36
AtCoder形式は
最初に全完した人がペナルティあればその時間分の逆転劇もあるけど
順位凍結前に全完したなんて事案あったし
エンターテイメント性には欠ける気がする
0223仕様書無しさん
垢版 |
2017/07/02(日) 03:25:02.94
どこに面白みを感じるかは個人差あるからエンターテイメント性に欠けるは言い過ぎました
すみませんでした
0224仕様書無しさん
垢版 |
2017/07/02(日) 03:28:38.36
横並び同時スタートで着順で勝敗が決するのは
陸上競技の走るタイプのやスピードスケートや水泳や競馬や競輪やモータースポーツ
そしてAtCoder
0225仕様書無しさん
垢版 |
2017/07/02(日) 03:33:32.37
コドフォやSRMみたいにシステムテストあるほうがマイノリティな気がする
0227仕様書無しさん
垢版 |
2017/07/02(日) 05:08:37.30
「できない」と「する必要のないところでしなくていい」は違う
全然符合してないし自分の読解力も恨むべきかと
0231仕様書無しさん
垢版 |
2017/07/02(日) 09:50:34.86
りんごさんとあんたさんは笑ってる写真みたことない
0233仕様書無しさん
垢版 |
2017/07/02(日) 13:10:12.67
競技プログラミングの問題解くとき本参考にしてる？
0237仕様書無しさん
垢版 |
2017/07/02(日) 19:23:12.88
>>215
>>235
前処理は１度だけで良いのか。txt
0238>>233
垢版 |
2017/07/02(日) 20:14:48.22
競技プログラミング初心者なのですが、参考書籍見ながら解いてもいいのか教えてください…
0241仕様書無しさん
垢版 |
2017/07/02(日) 20:44:24.47
>>238
個人的な意見だけど

実際に問題解くときはある程度は考えることが大事だと思う
ただ単にコピーしてるだけじゃ身に付きにくいし

そういった時間外にそういう本を読んで内容を実装して動きを確認するのはありかな
0242仕様書無しさん
垢版 |
2017/07/02(日) 20:46:40.49
もしかしてコンテスト中にググったり調べたりしちゃルール上マズかったりすんのか？
俺今まで結構調べながらやってたよ・・・
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況