- 1 名前：仕様書無しさん [2018/10/31(水) 23:49:54.41 .net]
- 仕様書無しさん2018/05/14(月) 06:43:50.62>>384
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)やCTFなどを楽しんでる競技プログラマ(競プロer)の雑談スレ
競プロイベントや競プロ問題や有名競プロerや競プロでよく使うアルゴリズム等について語りあったり、競プロ関連の質問相談なんでもおｋ
競プロ初心者でググっても解説読んでも分からないことがあったらスレの競プロの先輩方に訊いてみるのも手だよ(分かりやすい解説サイトとか書籍とか教えてくれるかもしれないよ)
次スレは>>950
# オンラインジャッジ・コンテストサイト
## 日本語
yukicoder https://yukicoder.me/
AtCoder https://atcoder.jp/
AIZU ONLINE JUDGE (AOJ) judge.u-aizu.ac.jp/onlinejudge/
## 英語
TopCoder
Single Round Match (SRM) 関係リンク集 codeforces.com/blog/entry/21879
Marathon Match (MM) https://community.topcoder.com/longcontest/?module=ViewPractice
※TopCoderは初参加までの手順が煩雑です。まずはググってみて、それでも分からなかったらスレで聞こう！
Codeforces codeforces.com/
CS Academy https://csacademy.com/
Project Euler https://projecteuler.net/ 和訳 odz.sakura\.ne.jp/projecteuler/
>>2-10あたりにテンプレ続く
※前スレ
競技プログラミングにハマるプログラマのスレ 16
medaka.5ch.net/test/read.cgi/prog/1534548265/
- 34 名前：仕様書無しさん [2018/11/04(日) 20:23:41.55 .net]
- ライター誰なの？
- 35 名前：仕様書無しさん mailto:sage [2018/11/04(日) 20:46:39.40 .net]
- 匿名希望さんからの出題です
- 36 名前：仕様書無しさん mailto:sage [2018/11/04(日) 20:53:57.21 .net]
- お腹いたい
- 37 名前：仕様書無しさん mailto:sage [2018/11/04(日) 21:50:00.75 .net]
- 鯖重いんだが
- 38 名前：仕様書無しさん mailto:sage [2018/11/04(日) 21:51:55.58 .net]
- 重すぎる
ギリギリ狙うんじゃなくて余裕を持ってくれ
- 39 名前：仕様書無しさん mailto:sage [2018/11/04(日) 21:58:31.37 .net]
- betaが遅いらしい
- 40 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:09:33.04 .net]
- 人数の増加に耐えれないんじゃこどふぉを笑えないなあ
- 41 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:17:47.84 .net]
- 今日社長だけらしいヤバみ
- 42 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:19:22.15 .net]
- 強行開催があだになったなあ
- 43 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:21:58.63 .net]
- 手順書整えてくり
- 44 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:25:45.65 .net]
- 全完まにあった。
- 45 名前：仕様書無しさん [2018/11/04(日) 22:26:25.20 .net]
- https://twitter.com/chokudai/status/1059066553881190400
今日は強行開催なので鯖が半分だったり色々怪しいんでごめんなさい＞＜ 先日から発信し続けてた通り、AtCoder社員全員不在でサポートはほぼ出来ないのでご了承ください！
（勝手にUnrated判断しても責任は取れません！ごめんなさい！）
(deleted an unsolicited ad)
- 46 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:28:38.03 .net]
- そんな無理してコンテスト開かなくても…
- 47 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:31:26.98 .net]
- 人がいなくて対応できないときこそ余裕を持たせたジャッジ鯖数にしようよ・・・
https://twitter.com/chokudai/status/1059058886152355841
ギリギリ耐えると思ったけど重いっぽい。ごめんなさーい＞＜
(deleted an unsolicited ad)
- 48 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:34:16.74 .net]
- https://twitter.com/chokudai/status/1057525294423252994
【速報】
・日曜日にABCが出来たらいいなって感じで準備してます
・りんごすぬけちょくだいの３人が東京にいないので、解説放送はできません
・多分事故対応も遅いです。ごめんね＞＜
・有志が勝手に解説放送してくれればちょくだい垢でRTするのでリプライください
(deleted an unsolicited ad)
- 49 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:36:29.21 .net]
- 重過ぎてTwitterのトレンド入りをするという不名誉な事態に
- 50 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:37:00.62 .net]
- 副社長のけんしょーさんでは対応できないってことなのかな
- 51 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:38:30.89 .net]
- くだらないバグでかなり手間取ってしまったので個人的にはunratedになってほしい
- 52 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:39:25.67 .net]
- ここはsemi-ratedで
- 53 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:39:57.78 .net]
- どいういう事？？？
社長含めてAtCoder社員全員不在でもコンテスト開催できる？
外部からサーバーを遠隔操作して開催か？
- 54 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:40:40.88 .net]
- 残り1分でなんとか全完できた
- 55 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:42:10.88 .net]
- 重かったせいで一分後にACしたんだが
こんなんunratedだよなあ
- 56 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:42:31.08 .net]
- C問題atcoderらしくないな
paiza臭がすごい
- 57 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:44:31.44 .net]
- 5分くらい提出結果わからない
問題文読めない
提出するが連続で押されていた判定になって多重にペナルティくらう
ひどい
- 58 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:45:01.78 .net]
- ABC Onlyだし実装重視でもええんでない
- 59 名前：仕様書無しさん [2018/11/04(日) 22:45:27.44 .net]
- betaだけが重かったらしいね
- 60 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:47:46.67 .net]
- betaじゃない方使ってたんで、いつも通りのコンテストだった。
- 61 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:52:06.69 .net]
- コンテスト前にVisual Studio のアップデートを実行してしまい
コンテスト中ずっと使えず今もまだインストール中・・・
PaizaIO使って全完できたのでよかったけど・・
- 62 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:52:40.30 .net]
- 次から重かったらbetaじゃないほうを試してみるか
- 63 名前：仕様書無しさん mailto:sage [2018/11/04(日) 22:55:16.52 .net]
- >>55
それゆえ解ける人が爆発的に増えてジャッジ鯖が爆発
ある意味で簡単問題でratingを稼げない仕組みだな
- 64 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:09:29.97 .net]
- ジャッジは普通に処理できてた気がするけども
- 65 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:12:15.64 .net]
- https://twitter.com/skyaozora/status/1059078509375549440
skyさんのスクリーンキャプチャ
(deleted an unsolicited ad)
- 66 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:15:23.06 .net]
- 解説もまだ見れないのか
こんな無理矢理開催する必要あったか
- 67 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:17:39.84 .net]
- コピペしたときに
int main(){
cout<<ans<<endl;
}
が
int main(){
cout<<ans<<en;
}
になってCEしたんだけど、おれのミスなのかな
手元でサンプル試してctrl+Aでコピーしたから間だけ削れるってことないと思うんだけど
よくわからん
- 68 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:17:41.22 .net]
- ratedでいいだろ早くしろよ
- 69 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:18:51.67 .net]
- https://img.atcoder.jp/abc113/editorial.pdf
きてるぞ
- 70 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:19:59.77 .net]
- Dが難しいかった
- 71 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:22:38.30 .net]
- 長く競技プログラミングやってる人はこういう事態にうろたえたりはしないんだろうけど新規さんたちは戸惑うばかりだろうね
- 72 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:28:57.81 .net]
- >>44-47
重要なアナウンスを社長垢のみでやるのいい下限にしろ
- 73 名前：仕様書無しさん [2018/11/04(日) 23:42:05.65 .net]
- https://twitter.com/chokudai/status/1059092978659016706
状況確認できてないですが、エラーログ見た限り基本的にはRatedです。接続厳しかったのは申し訳ないです＞＜
強行開催時はもうちょい障害率が高いことを発信した方がいいかな……。
https://twitter.com/chokudai/status/1059093069604089856
レート更新は社員が誰もいないのでしばらくないです。
(deleted an unsolicited ad)
- 74 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:45:15.34 .net]
- AtCoderはABCだしこんなもんでええやろって感じが出すぎ
- 75 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:47:53.57 .net]
- ABCは競技プログラミングではなくプログラミングコンテストだから
競技プログラミングというのはオンサイトやTシャツを狙えるDiv1からの世界
そう思っている僕は
- 76 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:48:41.24 .net]
- 野良コンに積極的に参加して運営のハードル下げよう
- 77 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:50:05.74 .net]
- 野良コン is 何
virtual contest ?
- 78 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:53:41.93 .net]
- 野良コンはunratedコンテストのうち
日本人が賞品や表彰の対象ではない海外の企業コンテストや学生主催コンテストのことだと思っていたけど
正確な定義を教えてベテラン競プロer！
- 79 名前：仕様書無しさん mailto:sage [2018/11/04(日) 23:59:48.82 .net]
- https://yukicoder.me/wiki/online_judge
> インドの大学によるコンテスト(いわゆる"野良コン")も多く開催される。
- 80 名前：仕様書無しさん mailto:sage [2018/11/05(月) 00:42:09.97 .net]
- 正確な定義なんてないけど >>77 の認識で大体合ってると思う
hackerrank, hackerearth, codechef とかのコンテスト一覧漁ると出てくる
(全部じゃないけど) ひどい問題があったりして参加者の寛容さが試される
- 81 名前：仕様書無しさん mailto:sage [2018/11/05(月) 01:11:32.70 .net]
- https://twitter.com/chokudai/status/964534596485316608?s=09
ABC限定だとちょっと決まってないですけど、出来るだけ何かしらのRatedコンテストを週１で、ってルールはあります！
(deleted an unsolicited ad)
- 82 名前：仕様書無しさん [2018/11/05(月) 02:56:59.80 .net]
- レート更新されたね
- 83 名前：仕様書無しさん mailto:sage [2018/11/05(月) 09:36:53.01 .net]
- 暫くアルゴリズムの勉強してようっと
- 84 名前：仕様書無しさん mailto:sage [2018/11/05(月) 09:48:14.60 .net]
- 新参ですが、トップコーダーっていつからコンテストの頻度減ったの？
昔は月3回とかやってたんですよね？
- 85 名前：仕様書無しさん [2018/11/05(月) 10:44:56.40 .net]
- 緑になったけど次何すればいい？
- 86 名前：仕様書無しさん mailto:sage [2018/11/05(月) 11:29:02.01 .net]
- >>18
りんごさん2位おめでとうございます
- 87 名前：仕様書無しさん mailto:sage [2018/11/05(月) 12:59:51.04 .net]
- レート５６なんだけど何すればいい
- 88 名前：仕様書無しさん mailto:sage [2018/11/05(月) 15:35:16.49 .net]
- 何をすればいいかって？
自分自身の人生なんだからやりたいこと好きなことすればいいんだよ
- 89 名前：仕様書無しさん mailto:sage [2018/11/05(月) 17:38:25.77 .net]
- いきなりスケールのでかい話になったな
- 90 名前：仕様書無しさん [2018/11/05(月) 18:06:17.77 .net]
- ABCを全部埋めて青色になろう
- 91 名前：仕様書無しさん mailto:sage [2018/11/05(月) 18:46:28.83 .net]
- AtCoder Scoresってサイトで自分の成長に繋がる点数帯の問題で特訓するのがいいらしいです
https://beta.atcoder.jp/posts/261
- 92 名前：仕様書無しさん mailto:sage [2018/11/05(月) 18:47:03.40 .net]
- Cで初めて挑戦したがソートとか作らないといけなくて面倒なのな
cpp学び直して出直すわ
- 93 名前：仕様書無しさん mailto:sage [2018/11/05(月) 18:48:47.81 .net]
- >>83
過去のSRMの開催記録はこちらで確認できるみたいです
https://competitiveprogramming.info/topcoder/srm
- 94 名前：仕様書無しさん mailto:sage [2018/11/05(月) 19:10:45.99 .net]
- 貪欲法と全探索の違いがわからない
全探索 全部検索する
貪欲法 値を保持して比較して探索する
こういう認識なんだけど
- 95 名前：仕様書無しさん mailto:sage [2018/11/05(月) 19:11:06.15 .net]
- >>91
cならqsortってのがあったはず
- 96 名前：仕様書無しさん mailto:sage [2018/11/05(月) 19:24:41.66 .net]
- C言語/C++のqsortとJavaのArrays.sortは競プロでは要注意
https://yukicoder.me/wiki/trap
- 97 名前：仕様書無しさん mailto:sage [2018/11/05(月) 19:34:09.30 .net]
- 全探索は
全通りの組み合わせ(または全通りの順序)
これの全てについて計算して答えが合うかを調べる(探索する)こと
貪欲法は
全探索はせず
解として良さそうな組み合わせ(または順序)を推定（予想?)してそれを答えをすること
という認識です僕は
- 98 名前：仕様書無しさん mailto:sage [2018/11/05(月) 19:48:32.98 .net]
- >>95
それJavaね
- 99 名前：仕様書無しさん mailto:sage [2018/11/05(月) 19:50:47.45 .net]
- 言葉にこだわるな
動的計画法と分割統治法を分けてる時点でナンセンスなんだから
- 100 名前：仕様書無しさん mailto:sage [2018/11/05(月) 19:51:51.62 .net]
- >>97
そのyukicoderのページにりんくされてるkinabaさんの記事を読みました？
- 101 名前：仕様書無しさん mailto:sage [2018/11/05(月) 19:54:30.57 .net]
- >>99性格にはkinabaさんの記事にリンクされているqnighyさんの記事
- 102 名前：仕様書無しさん mailto:sage [2018/11/05(月) 20:04:55.51 .net]
- >>100
全く関係ないと思うけど
- 103 名前：仕様書無しさん mailto:sage [2018/11/05(月) 20:08:23.75 .net]
- >>101
全く関係なかったですね
すみませんでした
- 104 名前：仕様書無しさん mailto:sage [2018/11/05(月) 20:10:43.59 .net]
- Ｃ＋＋ならＳＴＬでソートでしょ
- 105 名前：仕様書無しさん mailto:sage [2018/11/05(月) 20:11:04.70 .net]
- 貪欲法はその時点でさいつよな選択肢を選んでくだけだろ
全探索の対極じゃねーか
- 106 名前：仕様書無しさん mailto:sage [2018/11/05(月) 20:23:13.40 .net]
- 貪欲法は自己中法と改名すべき
- 107 名前：仕様書無しさん mailto:sage [2018/11/05(月) 20:36:57.22 .net]
- >>94
あったのか、ただの勉強不足だった
- 108 名前：仕様書無しさん mailto:sage [2018/11/05(月) 22:35:20.52 .net]
- 貪欲法は貪欲感あるからセーフ
動的計画法をなんとかしたほうがいい
- 109 名前：仕様書無しさん mailto:sage [2018/11/05(月) 22:47:20.49 .net]
- 舌切り雀を思い出し大きいつづらを選ぶ貪欲ババア法とでも覚えておけばOK
- 110 名前：仕様書無しさん mailto:sage [2018/11/05(月) 22:53:26.62 .net]
- 競プロのアドベントカレンダーというのがあるらしい
https://twitter.com/-/status/1059424794892890113
- 111 名前：仕様書無しさん mailto:sage [2018/11/06(火) 00:26:52.68 .net]
- よくわからんから例題を挙げて貪欲法と動的計画法での解法を述べてくれぇ
- 112 名前：仕様書無しさん mailto:sage [2018/11/06(火) 00:33:11.19 .net]
- ナップザック問題？
- 113 名前：仕様書無しさん mailto:sage [2018/11/06(火) 00:56:43.21 .net]
- ん？
全探索と貪欲法の違いの話じゃなかったのか？
- 114 名前：仕様書無しさん mailto:sage [2018/11/06(火) 01:31:07.17 .net]
- [PDF] ナップザック問題に対する動的計画法と貪欲法の比較 An Comparative ...
www.salesio-sp.ac.jp/papers/sotsuken/2012/pdf/documents/cs/5407.pdf
- 115 名前：仕様書無しさん mailto:sage [2018/11/06(火) 03:14:55.15 .net]
- ナップサック問題(重さの総和が一定以内で価値の総和を最大化)で言うと
貪欲: まだ積んでない荷物の中で 価値/重さ が最大の物(コスパが良いやつ)を優先して選ぶ (最適とは限らない)
動的計画法: DP[i][W] := i番目までの荷物の中から重さの総和がW(以下)になるように積んだときの最大の価値
全探索: 積むか積まないか2^N通り全部試して重さ制約を満たす中で一番いいやつ
それぞれ O(NlogN), O(NW), O(2^N)
- 116 名前：仕様書無しさん mailto:sage [2018/11/06(火) 03:58:52.42 .net]
- 動的計画法を前処理的に使って貪欲法を最適にするとかいう技もあるからな
AOJ の「DPL_1_I: Knapsack Problem with Limitations II」参照
- 117 名前：仕様書無しさん mailto:sage [2018/11/06(火) 15:17:04.57 .net]
- >>113
このPDF書いた人、競プロ経験無さそう
- 118 名前：仕様書無しさん mailto:sage [2018/11/06(火) 15:28:11.26 .net]
- ナップザックでのDPは枝刈りとメモ化を施した全探索のことなのだ
- 119 名前：仕様書無しさん mailto:sage [2018/11/06(火) 15:31:15.99 .net]
- >>117
× ナップザックでのDPは枝刈りとメモ化を施 した全探索のことなのだ
○ ナップザックでのDPは全探索に枝刈りとメモ化を施 した探索なのだ
- 120 名前：仕様書無しさん mailto:sage [2018/11/08(木) 02:13:53.23 .net]
- 競技プログラミング入門にやさしいサイト教えてくれ
パイザのCランク問題は解けるくらいのレベルなのだが
- 121 名前：仕様書無しさん mailto:sage [2018/11/08(木) 04:10:27.77 .net]
- コドフォの便利な有志サービスが紹介されてる
Codeforces Data Scraping Websites
https://codeforces.com/blog/entry/63040
- 122 名前：仕様書無しさん mailto:sage [2018/11/08(木) 04:12:10.24 .net]
- >>119
競技プログラミング入門って日本語だと何があるんだろうね
布教のために僕も知りたいところ
paizaスレとかだとAOJのコースをおすすめしてる人がいたけど
- 123 名前：仕様書無しさん mailto:sage [2018/11/08(木) 04:37:27.94 .net]
- C解けるなら入門は終わってるよ
次はAOJ以外にatcoderの200
- 124 名前：,300点問題という手もあり []
- [ここ壊れてます]
- 125 名前：仕様書無しさん mailto:sage [2018/11/08(木) 09:28:27.78 .net]
- AOJの最初の入門編ITP1の前半がDで後半がCくらいじゃないかな
その次のアルゴリズムALDSはpaizaのC解けていても難しいBとか問題によってはAくらい
自力で他人のカンニング無しで解けるのは少ししかない
入門ならAOJで十分解説あるものも多いが解説無いのは自力で調べる練習にもなる
- 126 名前：仕様書無しさん mailto:sage [2018/11/08(木) 12:44:51.36 .net]
- カンニングや解説を参照するには競プロやらなくちゃ。
- 127 名前：仕様書無しさん mailto:sage [2018/11/08(木) 12:50:14.61 .net]
- 螺旋本読みながらAOJのコースを埋めていくのがいいかな
- 128 名前：仕様書無しさん mailto:sage [2018/11/08(木) 13:03:14.63 .net]
- 不参加…カンニング…コピペ… 様々な不正行為 成長によかろうハズもない。
しかし、だからとて解けるまで独りで永遠に考える。これも健全とは言い難い。
毒も喰らう 栄養も喰らう。しばらく独りで考えてダメなら、カンニングしたコードを換骨奪胎し血肉に変える分析こそが競プロには肝要だ。
- 129 名前：仕様書無しさん mailto:sage [2018/11/08(木) 13:03:19.20 .net]
- 螺旋本は詳しいのは前半だけで、
解説してるのもソース問題の一部だけ。
全問に解説をつけるべき。
- 130 名前：仕様書無しさん mailto:sage [2018/11/08(木) 13:05:48.87 .net]
- 不正行為とは違うだろ。
コンテスト中にＡＣコードをうｐするような事件があるわけじゃなし。
- 131 名前：仕様書無しさん mailto:sage [2018/11/08(木) 13:07:26.69 .net]
- 400点問題は20分くらい考えて分かんなかったら解説見ちゃう
- 132 名前：仕様書無しさん mailto:sage [2018/11/08(木) 15:38:26.20 .net]
- Topcoderで言うと、わざわざ蟻本見なきゃ解けないような問題ってdiv1 med 以上なんだよな
でも黄色下位までの順位はほぼdiv1 easy 以下の問題の早解きで決まる
勉強なんかしてる暇あったらコンテストに参加しろってのはどこまでも正しいね
- 133 名前：仕様書無しさん mailto:sage [2018/11/08(木) 20:17:56.97 .net]
- 競プロをやってると、解けない問題に遭遇しても蟻本を見るってことは無くなるはず。
過去に自分が解いた問題のコードや、ネット上の情報を探すことになるはず。
- 134 名前：仕様書無しさん mailto:sage [2018/11/09(金) 00:03:34.93 .net]
- 流量制約付きフロー使いたいときは蟻本見ちゃうな
|
 |
