- 1 名前:仕様書無しさん [2018/10/31(水) 23:49:54.41 .net]
- 仕様書無しさん2018/05/14(月) 06:43:50.62>>384
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)やCTFなどを楽しんでる競技プログラマ(競プロer)の雑談スレ 競プロイベントや競プロ問題や有名競プロerや競プロでよく使うアルゴリズム等について語りあったり、競プロ関連の質問相談なんでもおk 競プロ初心者でググっても解説読んでも分からないことがあったらスレの競プロの先輩方に訊いてみるのも手だよ(分かりやすい解説サイトとか書籍とか教えてくれるかもしれないよ) 次スレは>>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/
- 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コンテストを週1で、ってルールはあります! (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]
- レート56なんだけど何すればいい
- 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]
- C++ならSTLでソートでしょ
- 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]
- 不正行為とは違うだろ。
コンテスト中にACコードをうpするような事件があるわけじゃなし。
- 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]
- 流量制約付きフロー使いたいときは蟻本見ちゃうな
- 135 名前:仕様書無しさん mailto:sage [2018/11/09(金) 00:13:09.47 .net]
- yukicoderのアドベントカレンダーコンテストの
https://adventar.org/calendars/3329
- 136 名前:仕様書無しさん mailto:sage [2018/11/09(金) 00:20:46.94 .net]
- 蟻本要らん子にw
中級問題を充実させたatcoder対応版欲しいね。
- 137 名前:仕様書無しさん mailto:sage [2018/11/09(金) 00:27:36.07 .net]
- yukicoderのスコア問題でシンプルで初級的な最適化問題増えたりしないのかな
https://ja.wikipedia.org/wiki/NP困難 巡回セールスマン問題 ナップサック問題 最小頂点被覆問題 最大独立集合問題 最大クリーク問題 分数和計画問題 最小シュタイナー問題 こういうのの教科書にも載ってそうな複雑な設定のないシンプルな問題あったら勉強になりそう?
- 138 名前:仕様書無しさん mailto:sage [2018/11/09(金) 00:31:55.91 .net]
- 今夜は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
- 139 名前:仕様書無しさん mailto:sage [2018/11/09(金) 00:47:50.42 .net]
- >>135
個人的に欲しいわぁ AOJにはあるのかな
- 140 名前:仕様書無しさん mailto:sage [2018/11/09(金) 01:38:26.58 .net]
- 色々サービスあるんだねー
AtCoder関連サービス Advent Calendar https://adventar.org/calendars/2932
- 141 名前:仕様書無しさん mailto:sage [2018/11/09(金) 18:19:49.48 .net]
- 5ch.netではなく2ch scのほうに書き込んでる奴いるのな
13スレと14スレでID:でページ内検索したら出てきた
- 142 名前:仕様書無しさん mailto:sage [2018/11/09(金) 18:26:30.16 .net]
- >>139
ID:o0ILzjH5Fという奴がむなしいことをやっていて草 》╋|||《数学オリンピック 28》|||╋《 ai.2ch\.sc/test/read.cgi/math/1423833544
- 143 名前:仕様書無しさん [2018/11/09(金) 18:30:54.07 .net]
- 明日の昼ごろ
- 144 名前:ゥらギフト券が当たるプログラミング・コンテストがあるよ!
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円分のギフトカードをプレゼントいたします。 [] - [ここ壊れてます]
- 145 名前:仕様書無しさん mailto:sage [2018/11/09(金) 18:36:55.61 .net]
- 新卒だったら本選参加資格あったのだが残念
unratedだから抽選権を得たら即撤退で
- 146 名前:仕様書無しさん mailto:sage [2018/11/09(金) 18:38:39.77 .net]
- 明日に備えて焼きなましを勉強しよう
- 147 名前:仕様書無しさん mailto:sage [2018/11/09(金) 19:20:13.54 .net]
- マラソン系の記事だとこれかな?
マラソンマッチの資料集 threeprogramming.lolipop.jp/blog/?p=1164 ↓適当にピックアップ 焼きなまし法のコツ Ver. 1.2 shindannin.hatenadiary.com/entry/20121224/1356364040 chokudaiサーチのメモ fmhr.hatenablog.jp/entry/2016/05/08/071710 chokudaiサーチ(ビームサーチ亜種)の利点の話 chokudai.hatenablog.com/entry/2017/04/12/055515 Chokudai search https://www.slideshare.net/chokudai/chokudai-search-23234124 競プロ解法紹介〜レベル別マラソンの戦い方〜 https://qiita.com/tsukammo/items/7041a00e429f9f5ac4ae 競プロ解法紹介〜大局観で高得点を取る!〜 https://qiita.com/tsukammo/items/85ffbe907e89b051d715
- 148 名前:仕様書無しさん mailto:sage [2018/11/09(金) 19:23:30.27 .net]
- 短時間マラソンなら貪欲法で十分な希ガス
- 149 名前:仕様書無しさん mailto:sage [2018/11/09(金) 19:32:45.27 .net]
- 過去のRCOハーフマラソン・HTTFやchokudaiコンテスト1,2,3で特訓
AtCoderのコンテスト検索機能にマラソン問題だけ表示するオプションが欲しいね
- 150 名前:仕様書無しさん [2018/11/09(金) 19:35:35.37 .net]
- 今夜はyukicoderもあるよ!最高★3.5だから全完しような!
yukicoder contest 203 2018-11-09 21:20:00〜2018-11-09 23:20:00 (2h) https://yukicoder.me/contests/210
- 151 名前:仕様書無しさん mailto:sage [2018/11/09(金) 20:29:57.59 .net]
- セキュリティの都合で、個人情報を要求してくるコンテストには参加できない
- 152 名前:仕様書無しさん mailto:sage [2018/11/09(金) 21:38:55.49 .net]
- マイホームセキュリティの人か
- 153 名前:仕様書無しさん mailto:sage [2018/11/09(金) 22:16:22.91 .net]
- マラソンだけでARCなしか
企業コンに邪魔されてAGCまでコンテストなさそうなの嫌だなあ
- 154 名前:仕様書無しさん mailto:sage [2018/11/09(金) 22:46:21.59 .net]
- 企業コンもratedにしてくれればいいのに
- 155 名前:仕様書無しさん mailto:sage [2018/11/09(金) 23:25:32.94 .net]
- yukicoderの★3は難しいな
- 156 名前:仕様書無しさん mailto:sage [2018/11/09(金) 23:48:45.64 .net]
- ★を200倍するとAtCoderの配点になるイメージ
- 157 名前:仕様書無しさん mailto:sage [2018/11/10(土) 01:27:53.16 .net]
- レートなしやめちくりー
- 158 名前:仕様書無しさん mailto:sage [2018/11/10(土) 02:05:12.32 .net]
- 普通のarcはえなさすぎ
- 159 名前:仕様書無しさん mailto:sage [2018/11/10(土) 02:22:34.66 .net]
- 社長増長してきたか。うふふ
- 160 名前:仕様書無しさん mailto:sage [2018/11/10(土) 15:12:59.65 .net]
- 昨日のyukicoder知らずに寝ちゃった・・・
- 161 名前:仕様書無しさん [2018/11/10(土) 15:30:40.47 .net]
- >>141
やっぞ 正の得点で抽選権ゲットすっぞ 新卒どもは本選目指して粘れっ
- 162 名前:仕様書無しさん mailto:sage [2018/11/10(土) 15:32:42.48 .net]
- >有効な回答を提出された方の中から、抽選で30名に
成績によらず抽選で貰える すごい!
- 163 名前:仕様書無しさん mailto:sage [2018/11/10(土) 17:08:44.98 .net]
- 今週atcoder無しかよおおおおお
- 164 名前:仕様書無しさん [2018/11/10(土) 17:42:51.17 .net]
- rated欲は海外コンテストで満たすしかないね
明日朝はLeetCodeあります?
- 165 名前:仕様書無しさん mailto:sage [2018/11/10(土) 17:46:11.89 .net]
- 海外コンテストなのはともかくとして、
なぜにLeetCodeなんぞを
- 166 名前:仕様書無しさん mailto:sage [2018/11/10(土) 17:53:16.99 .net]
- 今夜0:30からHackerEarthでNovember Easy' 18 RATED CONTESTだよ
https://www.hackerearth.com/en-us/challenge/competitive/november-easy-18/
- 167 名前:仕様書無しさん mailto:sage [2018/11/10(土) 17:55:43.10 .net]
- >>162
paizaスレの>>1でLeetCodeが紹介されてる
- 168 名前:仕様書無しさん mailto:sage [2018/11/10(土) 18:02:33.41 .net]
- paizaスレのスレ主は、
CodeIQは滅びました と書き続ける変な奴 転職スレなのに海外サイトばかり押しまくりの変な奴
- 169 名前:仕様書無しさん [2018/11/10(土) 18:05:34.24 .net]
- 一般論としてマラソン系問題の要領は問題文にあるスコア計算式と睨めっこすることにあると思う
- 170 名前:仕様書無しさん mailto:sage [2018/11/10(土) 18:23:23.23 .net]
- マラソン系問題むずいねぇ
- 171 名前:仕様書無しさん mailto:sage [2018/11/10(土) 19:29:42.24 .net]
- 5時間考えて最初の自明提出からスコア上がらない
つらい
- 172 名前:仕様書無しさん mailto:sage [2018/11/10(土) 19:29:56.19 .net]
- マラソン系の問題ってどれもだいたい問題どおりのシュミレーションするコードを書かないといけないのが実装量多くてしんどい
でも書かないとスコア計算できないしタフガイ向けコンテスト
- 173 名前:仕様書無しさん mailto:sage [2018/11/10(土) 19:36:17.59 .net]
- なるほど理解した
マラソンは向いてない
- 174 名前:仕様書無しさん [2018/11/10(土) 22:14:35.75 .net]
- 8時間一瞬で溶けた……用意してた夕食今から食べないと
|
![](http://yomi.mobi/qr.gif)
|