競技プログラミングにハマるプログラマのスレ 17
■ このスレッドは過去ログ倉庫に格納されています
仕様書無しさん2018/05/14(月) 06:43:50.62>>384
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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あたりにテンプレ続く
※前スレ
競技プログラミングにハマるプログラマのスレ 16
http://medaka.5ch.net/test/read.cgi/prog/1534548265/ https://twitter.com/chokudai/status/1059066553881190400
今日は強行開催なので鯖が半分だったり色々怪しいんでごめんなさい＞＜ 先日から発信し続けてた通り、AtCoder社員全員不在でサポートはほぼ出来ないのでご了承ください！
（勝手にUnrated判断しても責任は取れません！ごめんなさい！）
https://twitter.com/5chan_nel (5ch newer account) 人がいなくて対応できないときこそ余裕を持たせたジャッジ鯖数にしようよ・・・
https://twitter.com/chokudai/status/1059058886152355841
ギリギリ耐えると思ったけど重いっぽい。ごめんなさーい＞＜
https://twitter.com/5chan_nel (5ch newer account) https://twitter.com/chokudai/status/1057525294423252994
【速報】
・日曜日にABCが出来たらいいなって感じで準備してます
・りんごすぬけちょくだいの３人が東京にいないので、解説放送はできません
・多分事故対応も遅いです。ごめんね＞＜
・有志が勝手に解説放送してくれればちょくだい垢でRTするのでリプライください
https://twitter.com/5chan_nel (5ch newer account) 重過ぎてTwitterのトレンド入りをするという不名誉な事態に 副社長のけんしょーさんでは対応できないってことなのかな くだらないバグでかなり手間取ってしまったので個人的にはunratedになってほしい どいういう事？？？
社長含めてAtCoder社員全員不在でもコンテスト開催できる？
外部からサーバーを遠隔操作して開催か？ 重かったせいで一分後にACしたんだが
こんなんunratedだよなあ C問題atcoderらしくないな
paiza臭がすごい 5分くらい提出結果わからない
問題文読めない
提出するが連続で押されていた判定になって多重にペナルティくらう
ひどい betaじゃない方使ってたんで、いつも通りのコンテストだった。 コンテスト前にVisual Studio のアップデートを実行してしまい
コンテスト中ずっと使えず今もまだインストール中・・・
PaizaIO使って全完できたのでよかったけど・・ 次から重かったらbetaじゃないほうを試してみるか >>55
それゆえ解ける人が爆発的に増えてジャッジ鯖が爆発
ある意味で簡単問題でratingを稼げない仕組みだな 解説もまだ見れないのか
こんな無理矢理開催する必要あったか コピペしたときに
int main(){
cout<<ans<<endl;
}
が
int main(){
cout<<ans<<en;
}
になってCEしたんだけど、おれのミスなのかな
手元でサンプル試してctrl+Aでコピーしたから間だけ削れるってことないと思うんだけど
よくわからん 長く競技プログラミングやってる人はこういう事態にうろたえたりはしないんだろうけど新規さんたちは戸惑うばかりだろうね >>44-47
重要なアナウンスを社長垢のみでやるのいい下限にしろ AtCoderはABCだしこんなもんでええやろって感じが出すぎ ABCは競技プログラミングではなくプログラミングコンテストだから
競技プログラミングというのはオンサイトやTシャツを狙えるDiv1からの世界
そう思っている僕は 野良コン is 何
virtual contest ? 野良コンはunratedコンテストのうち
日本人が賞品や表彰の対象ではない海外の企業コンテストや学生主催コンテストのことだと思っていたけど
正確な定義を教えてベテラン競プロer！ https://yukicoder.me/wiki/online_judge
> インドの大学によるコンテスト(いわゆる"野良コン")も多く開催される。 正確な定義なんてないけど >>77 の認識で大体合ってると思う
hackerrank, hackerearth, codechef とかのコンテスト一覧漁ると出てくる
(全部じゃないけど) ひどい問題があったりして参加者の寛容さが試される 新参ですが、トップコーダーっていつからコンテストの頻度減ったの？
昔は月3回とかやってたんですよね？ 何をすればいいかって？
自分自身の人生なんだからやりたいこと好きなことすればいいんだよ AtCoder Scoresってサイトで自分の成長に繋がる点数帯の問題で特訓するのがいいらしいです
https://beta.atcoder.jp/posts/261 Cで初めて挑戦したがソートとか作らないといけなくて面倒なのな
cpp学び直して出直すわ 貪欲法と全探索の違いがわからない
全探索 全部検索する
貪欲法 値を保持して比較して探索する
こういう認識なんだけど C言語/C++のqsortとJavaのArrays.sortは競プロでは要注意
https://yukicoder.me/wiki/trap 全探索は
全通りの組み合わせ(または全通りの順序)
これの全てについて計算して答えが合うかを調べる(探索する)こと
貪欲法は
全探索はせず
解として良さそうな組み合わせ(または順序)を推定（予想?)してそれを答えをすること
という認識です僕は 言葉にこだわるな
動的計画法と分割統治法を分けてる時点でナンセンスなんだから >>97
そのyukicoderのページにりんくされてるkinabaさんの記事を読みました？ >>99性格にはkinabaさんの記事にリンクされているqnighyさんの記事 >>101
全く関係なかったですね
すみませんでした 貪欲法はその時点でさいつよな選択肢を選んでくだけだろ
全探索の対極じゃねーか 貪欲法は貪欲感あるからセーフ
動的計画法をなんとかしたほうがいい 舌切り雀を思い出し大きいつづらを選ぶ貪欲ババア法とでも覚えておけばOK よくわからんから例題を挙げて貪欲法と動的計画法での解法を述べてくれぇ [PDF] ナップザック問題に対する動的計画法と貪欲法の比較 An Comparative ...
www.salesio-sp.ac.jp/papers/sotsuken/2012/pdf/documents/cs/5407.pdf ナップサック問題(重さの総和が一定以内で価値の総和を最大化)で言うと
貪欲: まだ積んでない荷物の中で 価値/重さ が最大の物(コスパが良いやつ)を優先して選ぶ (最適とは限らない)
動的計画法: DP[i][W] := i番目までの荷物の中から重さの総和がW(以下)になるように積んだときの最大の価値
全探索: 積むか積まないか2^N通り全部試して重さ制約を満たす中で一番いいやつ
それぞれ O(NlogN), O(NW), O(2^N) 動的計画法を前処理的に使って貪欲法を最適にするとかいう技もあるからな
AOJ の「DPL_1_I: Knapsack Problem with Limitations II」参照 >>113
このPDF書いた人、競プロ経験無さそう ナップザックでのDPは枝刈りとメモ化を施した全探索のことなのだ >>117
× ナップザックでのDPは枝刈りとメモ化を施 した全探索のことなのだ
○ ナップザックでのDPは全探索に枝刈りとメモ化を施 した探索なのだ 競技プログラミング入門にやさしいサイト教えてくれ
パイザのCランク問題は解けるくらいのレベルなのだが コドフォの便利な有志サービスが紹介されてる
Codeforces Data Scraping Websites
https://codeforces.com/blog/entry/63040 >>119
競技プログラミング入門って日本語だと何があるんだろうね
布教のために僕も知りたいところ
paizaスレとかだとAOJのコースをおすすめしてる人がいたけど C解けるなら入門は終わってるよ
次はAOJ以外にatcoderの200,300点問題という手もあり AOJの最初の入門編ITP1の前半がDで後半がCくらいじゃないかな
その次のアルゴリズムALDSはpaizaのC解けていても難しいBとか問題によってはAくらい
自力で他人のカンニング無しで解けるのは少ししかない
入門ならAOJで十分解説あるものも多いが解説無いのは自力で調べる練習にもなる カンニングや解説を参照するには競プロやらなくちゃ。 螺旋本読みながらAOJのコースを埋めていくのがいいかな 不参加…カンニング…コピペ… 様々な不正行為 成長によかろうハズもない。
しかし、だからとて解けるまで独りで永遠に考える。これも健全とは言い難い。
毒も喰らう 栄養も喰らう。しばらく独りで考えてダメなら、カンニングしたコードを換骨奪胎し血肉に変える分析こそが競プロには肝要だ。 螺旋本は詳しいのは前半だけで、
解説してるのもソース問題の一部だけ。
全問に解説をつけるべき。 不正行為とは違うだろ。
コンテスト中にＡＣコードをうｐするような事件があるわけじゃなし。 400点問題は20分くらい考えて分かんなかったら解説見ちゃう Topcoderで言うと、わざわざ蟻本見なきゃ解けないような問題ってdiv1 med 以上なんだよな
でも黄色下位までの順位はほぼdiv1 easy 以下の問題の早解きで決まる
勉強なんかしてる暇あったらコンテストに参加しろってのはどこまでも正しいね 競プロをやってると、解けない問題に遭遇しても蟻本を見るってことは無くなるはず。
過去に自分が解いた問題のコードや、ネット上の情報を探すことになるはず。 蟻本要らん子にｗ
中級問題を充実させたatcoder対応版欲しいね。 yukicoderのスコア問題でシンプルで初級的な最適化問題増えたりしないのかな
https://ja.wikipedia.org/wiki/NP困難
巡回セールスマン問題
ナップサック問題
最小頂点被覆問題
最大独立集合問題
最大クリーク問題
分数和計画問題
最小シュタイナー問題
こういうのの教科書にも載ってそうな複雑な設定のないシンプルな問題あったら勉強になりそう? 今夜はyukicoderのコンテスト
明日の昼からAtCoderで企業コンのHTTF
11/10(土) 14:00 HACK TO THE FUTURE 2019予選
11/23(金) 21:00 DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選
11/24(土) 20:00 第5回 ドワンゴからの挑戦状 予選
12/2(日) 21:00 AtCoder Grand Contest 029
12/15(土) 21:00 AtCoder Grand Contest 030 >>135
個人的に欲しいわぁ
AOJにはあるのかな 色々サービスあるんだねー
AtCoder関連サービス Advent Calendar
https://adventar.org/calendars/2932 5ch.netではなく2ch scのほうに書き込んでる奴いるのな
13スレと14スレでID:でページ内検索したら出てきた >>139
ID:o0ILzjH5Fという奴がむなしいことをやっていて草
》╋|||《数学オリンピック 28》|||╋《
http://ai.2ch\.sc/test/read.cgi/math/1423833544 明日の昼ごろからギフト券が当たるプログラミング・コンテストがあるよ！
HACK TO THE FUTURE 2019予選2018/11/10 14:00:00〜2018/11/10 22:00:00
https://future-contest-2019-qual.contest.atcoder.jp/
予選抽選プレゼント
本選進出者（辞退者含む）を除き、有効な回答を提出された方の中から、抽選で30名に3,000円分のギフトカードをプレゼントいたします。 新卒だったら本選参加資格あったのだが残念
unratedだから抽選権を得たら即撤退で ■ このスレッドは過去ログ倉庫に格納されています
