X
競技プログラミングにハマるプログラマのスレ 15
■ このスレッドは過去ログ倉庫に格納されています
0001仕様書無しさん
垢版 |
2018/05/14(月) 06:43:50.62
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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あたりにテンプレ続く
※前スレ
競技プログラミングにハマるプログラマのスレ 14
http://medaka.5ch.net/test/read.cgi/prog/1517756393/
0504仕様書無しさん
垢版 |
2018/07/14(土) 08:51:20.84
今日のDiv2のD問題ってどうやったら計算量へらせるんや･･･
0506仕様書無しさん
垢版 |
2018/07/14(土) 23:31:05.88
およそ90分かけてBをACったところでオワタ
なんでみんなさくっと解けるん...
0513仕様書無しさん
垢版 |
2018/07/15(日) 19:59:41.30
https://clist.by
このコンテストリスト
英語の問題文のないコンテストもごくたまに並んでたりするけど
もしかするとお願いすればyukicoderのコンテストもリストアップしてもらえたりするのかな
0514仕様書無しさん
垢版 |
2018/07/16(月) 09:27:04.49
日本語しか問題文のないyukicoderはどうだろう？？？？
0515仕様書無しさん
垢版 |
2018/07/16(月) 23:20:44.11
みなさんはAtCoderとyukicoder以外ではどこのコンテストに参加してますか？
0516仕様書無しさん
垢版 |
2018/07/16(月) 23:44:00.38
srmとcodechefとcodeforcesはatcoderできる前にやってたけど今は時間が遅すぎだし、英語の解釈だけでだいぶ損するし、コーナーケースにハメさせようという問題が多くて勉強にならん
0519仕様書無しさん
垢版 |
2018/07/17(火) 09:33:01.77
AtCoderとyukicoder以外に、AOJも日本語
0520仕様書無しさん
垢版 |
2018/07/18(水) 07:45:52.80
>>2の競プロSlack数ヶ月ぶりに覗いてみたが
プロたちしっかりとチェックしてるんだね
それとhmehtaに続きTopCoderのt-macらしき人物が…TopCoderの運営側の人間が増えている…
0521仕様書無しさん
垢版 |
2018/07/18(水) 10:13:41.35
競プロたのしい
0523仕様書無しさん
垢版 |
2018/07/18(水) 22:45:09.60
超わかる！
0524仕様書無しさん
垢版 |
2018/07/19(木) 14:22:41.85
スキルアップのためにやってみようと思ったら数学とかやってないと結構難しそうなやつだな
0525仕様書無しさん
垢版 |
2018/07/19(木) 14:48:30.67
最低限の数学は真っ先に身につけるべきスキルなので頑張って
0526仕様書無しさん
垢版 |
2018/07/19(木) 15:05:46.89
競プロで使う数学って何で勉強すればいいの？
エレガントな問題解決とか？
0527仕様書無しさん
垢版 |
2018/07/19(木) 15:35:09.80
最小公倍数、最大公約数
順列組合せ
確率
とかかな？
0531仕様書無しさん
垢版 |
2018/07/19(木) 21:42:16.49
Noiminのパフォーマンスは、すごい乱高下をしてるってことかな？？？
0532仕様書無しさん
垢版 |
2018/07/19(木) 21:55:42.50
>>529
実験に協力しようかと思ったがレート1200までかー、1200は余裕で超えちゃってるからなー、つれーわー
まさかここでレートの高さが仇になるとはなー、かーっ
0533仕様書無しさん
垢版 |
2018/07/20(金) 00:33:57.07
7/20 10:00〜 TCO18 Algo R3B
https://topcoder.com/community/events/

7/21 01:00〜 ICFPC2018
https://twitter.com/ICFPContest2018
https://icfpcontest2018.github.io

7/21 21:00〜 AtCoder ABC103
https://abc103.contest.atcoder.jp/
https://beta.atcoder.jp/contests/abc103

7/22 02:00〜 FHC2018 Round1
https://www.facebook.com/notes/1029173677098533/

7/23 0100〜 CodeChef Cook-off
http://www.codechef.com/COOK96

7/26 01:00〜 CodinGame Legends of Code and Magic
http://www.codingame.com/contests/legends-of-code-and-magic

7/27 00:05〜 Codeforces Round #499 (div1/div2)
http://codeforces.com/contests/1010
0537仕様書無しさん
垢版 |
2018/07/20(金) 08:46:33.64
>>532
地獄のなんとかってやつか。
ワシは次のABCでレンジに入れそうだから行ってくる
0538仕様書無しさん
垢版 |
2018/07/20(金) 09:44:40.26
touristと比較して脳みそが使えてませんね。って材料になるのが目に見えるぜ
0539仕様書無しさん
垢版 |
2018/07/20(金) 09:49:27.74
touristと比較される600-1200のレートを持つ人ってすごいな
0542仕様書無しさん
垢版 |
2018/07/20(金) 18:52:08.26
ICFPCってコドフォだとあまり人気なさそうだね
2010,2011,2013のときのブログ記事しか見つけられなかった
0551仕様書無しさん
垢版 |
2018/07/20(金) 22:01:05.91
Codeforcesで告知されるプログラミング禁止の数学コンテストMathMash

数学徒たちをMathMashに誘い込みそこからさらに競プロへ誘い込む
そんなことが出来たらいいなと思いました

MathMash Round 25 が今夜2:00から

http://codeforces.com/blog/entry/60718
0553仕様書無しさん
垢版 |
2018/07/20(金) 22:40:16.89
>>549
ぱっと見典型的なスケジューリング問題っぽいけど
マラソン的に面白い問題になるんだろうか？（知らんけど）
ググってよさげなアルゴリズムパクるだけで終わったりしないんかな
0554仕様書無しさん
垢版 |
2018/07/20(金) 22:59:03.33
そりゃアスプローバって会社は生産スケジューラソリューションを取り扱っているのだから…
0556仕様書無しさん
垢版 |
2018/07/20(金) 23:12:33.45
＞受賞プログラムの著作権（著作権法第27条および第28条に
規定する権利を含む）を主催者に移転し、著作者人格権を行使しないものとします。

なんか気持ち悪いな
0557仕様書無しさん
垢版 |
2018/07/20(金) 23:27:50.91
AtCoderでは著作権の移転はないね

https://beta.atcoder.jp/tos
知的財産権
1. 本サービスに対して投稿されたプログラムの所有権と著作権は、そのプログラムを作成したユーザに帰属します

3. ユーザ自身が作成した著作物を本サービスを通じて掲載した場合、弊社が宣伝告知等に利用することを許諾するものとします。また、かかる使用に際して、当該ユーザは著作者人格権を行使しないものとします
0559仕様書無しさん
垢版 |
2018/07/20(金) 23:44:39.83
例え著作権を奪っても、何人からも著作者人格権は奪えないだろ

奪えない権利を発動しないよう要求するってどうなの？ 教えて法律に自信ニキ！
0561仕様書無しさん
垢版 |
2018/07/20(金) 23:54:57.90
著作者人格権を行使するなって要求を呑みたくなければコンテストに参加しなければいいだけだろって話ではなくて、要求そのものが違法か合法かどうかか
0562仕様書無しさん
垢版 |
2018/07/21(土) 00:00:38.68
「著作者人格権 行使」でググるとプロコンに限らず、文書やイラストなど作品を投稿するコンテスト等や業務的な依頼などでも問題視されている？
0563仕様書無しさん
垢版 |
2018/07/21(土) 00:13:17.87
手抜きコードでボイコットや。ワイはレート800だから真面目にやるが使い物になるまい
0565仕様書無しさん
垢版 |
2018/07/21(土) 00:23:11.69
規約が日本語で書かれているとちゃんと読む人たち(GoogleCodeJamやCodeforcesで規約を読んで参加しているのですか？)
0566仕様書無しさん
垢版 |
2018/07/21(土) 00:26:59.58
約30分後から72時間のコンテストが始まりますね！
チーム参加の方々もぼっち参加者の方々もみなさん頑張ってくださいね！
チームUnagiは今年優勝できるといいですね！

7/21 01:00〜 ICFPC2018
https://twitter.com/ICFPContest2018
https://icfpcontest2018.github.io
0567仕様書無しさん
垢版 |
2018/07/21(土) 00:33:07.70
いくつかの日本企業がチーム作って参加してたりする印象＞ICFPContest
0569仕様書無しさん
垢版 |
2018/07/21(土) 01:28:51.65
grundy数とNimについて調べてるが意味わかんねえ
Nimがxorで判定できる理由がさっぱりわからねえ
Nimに帰着とかいう言い回しがさっぱりわからねえ、grundy数のままで考えたほうがいいんじゃないか
そしてgrundy数もxorで判定できるってのが意味わかんねえ、意味理解せず使うだけなら割といけそうだがそのうち死にそう
0570仕様書無しさん
垢版 |
2018/07/21(土) 03:11:37.88
>>567
企業vs企業が実現できるプログラミングコンテストは少ないからね
0571仕様書無しさん
垢版 |
2018/07/21(土) 03:48:12.05
「nim site:codeforces.com」でググるとたくさん記事出てくるね、英語で読めないけど
0572仕様書無しさん
垢版 |
2018/07/21(土) 03:50:31.94
「nim site:hatenablog.jp」でも記事がチラホラあるね。プログラミング言語のNimのほうの記事もあるけど。
0573仕様書無しさん
垢版 |
2018/07/21(土) 03:54:09.12
普通に「nim grundy」でググっても出てくるんだね
蟻本にも書いてあるそうで
0575仕様書無しさん
垢版 |
2018/07/21(土) 04:07:34.35
分かりやすい解説記事があまりないってことは
分かりやすい解説記事を最初に書いた人が勝つ
0577仕様書無しさん
垢版 |
2018/07/21(土) 13:42:21.01
うーんまだモヤモヤする
Nimの必勝法は英字wikipedia が自分的には一番わかりやすかった
grundy数の使い方はテキトーな日本語blog で割とわかった...はず
grundy数がN の状態からは定義から0...N-1 に遷移できると考えりゃまあたしかにNimっぽく考えられるのかもしれん
Nimと考えりゃgrundy数のxorも自然かもしれん...
なんか理解しきったとは言い難いが
0579仕様書無しさん
垢版 |
2018/07/21(土) 22:52:11.54
ABCオワタ
Cはモノグラフ(整数)にすげえ似た問題があった気がする
0580仕様書無しさん
垢版 |
2018/07/21(土) 22:57:01.05
ABC過去問同様Bまでしか解けなくてわろた
やっぱ向いてないかもしれん
Cは数学的説明付けなくても、単に数列の法則性見抜けば簡単だったのを他の人の提出で知った
Dは察し
0581仕様書無しさん
垢版 |
2018/07/21(土) 22:59:59.40
最大化問題にありがちな典型テクとして自明な上限を考えてそれに一致することを祈るというのがあり
0582仕様書無しさん
垢版 |
2018/07/21(土) 23:12:10.97
なんでみんなこんなの軽々解けるんだ
0584仕様書無しさん
垢版 |
2018/07/22(日) 00:46:20.93
一杯解けなくて悔しい思いを重ねてきたからだよ
0587仕様書無しさん
垢版 |
2018/07/22(日) 06:44:49.86
>>585
それでいいよ。N個バケツ用意してaiの位置にbiを突っ込めばO(N)になる
0588仕様書無しさん
垢版 |
2018/07/22(日) 09:03:14.98
ＡＢＣあったの忘れてた！
0590仕様書無しさん
垢版 |
2018/07/22(日) 18:02:25.01
D問題の復習してたんだけど
C++ってvector<pair<int, int>>でpairのsecondでソートするのって
boostでbindするっていうクソめんどい方法しかないの？

この問題の場合は、aiをsecondにbiをfirstに標準入力から受け取っておけば普通にソートでいいのは分かるんだけど
なんとなく気持ち悪くて

あるいはC++で多次元配列使うなみたいなのもググると出てくるし
vector<pair<int, int>>自体を使わないほうがいいのかな
0591仕様書無しさん
垢版 |
2018/07/22(日) 18:26:49.94
3つ以上の組を扱う場合はstruct作ってそのなかに比較関数を書いてる
記述量は少ないだろうしpairの比較が嫌な場合でもそうすればいいと思う
0592仕様書無しさん
垢版 |
2018/07/23(月) 01:53:27.28
遅延評価セグ木とかいうのどこが遅延評価してるんだ
対応するノードに情報もたせてるだけとちゃうんか
0594仕様書無しさん
垢版 |
2018/07/23(月) 02:25:14.86
std::sortにラムダ式渡す手もある
sort(begin(v), end(v), [](pair<int,int> a, pair<int,int> b){return a.second < b.second;});
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況