- 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/
- 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]
- 流量制約付きフロー使いたいときは蟻本見ちゃうな
- 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]
- 蟻本要らん子にｗ
中級問題を充実させた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時間一瞬で溶けた……用意してた夕食今から食べないと
- 175 名前：仕様書無しさん mailto:sage [2018/11/10(土) 22:44:09.60 .net]
- 8時間も一つの問題に対して費やせないわ、みんなよくやるなぁ
- 176 名前：仕様書無しさん mailto:sage [2018/11/10(土) 23:08:06.69 .net]
- 俺なんか Topcoder SRM Div2 Med の問題に 12 時間使ったことあるよ
- 177 名前：仕様書無しさん mailto:sage [2018/11/10(土) 23:10:58.94 .net]
- 正の得点したので抽選の対象になれたのでよかった
- 178 名前：仕様書無しさん [2018/11/10(土) 23:15:02.89 .net]
- 20分後からのコドフォはdiv1div2の混合ratedコンテストだったのだな
https://codeforces.com/contests/1055
- 179 名前：仕様書無しさん mailto:sage [2018/11/10(土) 23:18:01.17 .net]
- >>175
Round2ってなっているからRound1通過者だけかと思ってたけど
Round1,2,3それぞれ独立してたのな
https://codeforces.com/blog/entry/62355
- 180 名前：仕様書無しさん mailto:sage [2018/11/10(土) 23:34:28.55 .net]
- 11/16にtomerunさんがtopcoderのマラソンマッチを解説するようです
https://twitter.com/Topcoder/status/1061082537269829632
(deleted an unsolicited ad)
- 181 名前：仕様書無しさん mailto:sage [2018/11/10(土) 23:50:36.07 .net]
- >>172
ゲームでハイスコア伸ばすために8時間ずっとプレイし続ける感覚でやってる
- 182 名前：仕様書無しさん mailto:sage [2018/11/11(日) 12:19:03.25 .net]
- 競プロはマイクラ
- 183 名前：仕様書無しさん [2018/11/11(日) 15:17:00.79 .net]
- HTTF解説放送あったようだ
https:/twitter.com/atcoder/status/1061243834028371968
(deleted an unsolicited ad)
- 184 名前：仕様書無しさん [2018/11/11(日) 22:41:46.51 .net]
- >>136
金曜土曜と予選が続くのか
- 185 名前：仕様書無しさん mailto:sage [2018/11/11(日) 22:58:25.81 .net]
- 人が1日に必要とする栄養の摂取量を確実に摂るために
料理の栄養の量でDPで1日3食分の最高のメニューを見つけ出せれば競プロが役に立つと
- 186 名前：仕様書無しさん [2018/11/11(日) 23:05:49.31 .net]
- CODE FESTIVAL 2018にAI ChallengeというゲームAIコンテストが併設開催されてる
2048っていうゲームを対戦ゲームにしたものらしい
コードの提出期限は11/16だそうで
https://www.recruit-jinji.jp/recruitment/code_fes/
https://www.exkazuu.net/AIChallenge2018AtCodeFestival/
- 187 名前：仕様書無しさん [2018/11/11(日) 23:07:08.15 .net]
- >>183の現在のランキング
https://aichallenge.exkazuu.net/contests/1
- 188 名前：仕様書無しさん [2018/11/11(日) 23:22:44.89 .net]
- >>183-184
これをダウンロードしてローカルで試すらしい
https://github.com/exKAZUu/AIChallenge2018AtCodeFestival/releases
https://github.com/exKAZUu/AIChallenge2018AtCodeFestival/blob/master/Battle2048/README.md
- 189 名前：仕様書無しさん mailto:sage [2018/11/12(月) 00:05:16.58 .net]
- atcoderのレート上げたいのでratedコンテストが欲しい
- 190 名前：仕様書無しさん mailto:sage [2018/11/13(火) 02:03:44.09 .net]
- chokudaiさん
レートと能力の話やめてほしいな
あげようと頑張ってる最中に評価されたくない
- 191 名前：仕様書無しさん mailto:sage [2018/11/13(火) 02:38:15.13 .net]
- 「役に立たない」スレから流れてきた粘着かよ
- 192 名前：仕様書無しさん mailto:sage [2018/11/13(火) 07:14:15.54 .net]
- chokudaiネットストーカーは
書いてることが分からん。
- 193 名前：仕様書無しさん mailto:sage [2018/11/13(火) 09:36:40.86 .net]
- 競プロって詰将棋みたいなもんだから社長の言うこと気にするな
- 194 名前：仕様書無しさん mailto:sage [2018/11/13(火) 09:41:07.12 .net]
- リセマラ封じって好評なのかな？
- 195 名前：仕様書無しさん mailto:sage [2018/11/13(火) 09:46:46.80 .net]
- 企業向けの話よねえ。atcoderの保身の為じゃないかな
- 196 名前：仕様書無しさん mailto:sage [2018/11/13(火) 09:58:02.20 .net]
- 夏頃のABCで、中国系の名前で数字連番が20個くらい出てたの見たことある。意味分からん
- 197 名前：仕様書無しさん mailto:sage [2018/11/13(火) 10:25:34.42 .net]
- chokudaiネットストーカーは、専用スレでも立ててそっちに逝け
- 198 名前：仕様書無しさん mailto:sage [2018/11/13(火) 10:32:07.68 .net]
- 競プロで一番得してるのは起業した社長だよな。
他は養分
- 199 名前：仕様書無しさん mailto:sage [2018/11/13(火) 11:19:23.40 .net]
- 競プロ業界で金儲けとか無理でしょ
そりゃ社長とその愉快な仲間たち数人が飯食える程度にはなんとかなるだろうけど
大化けして億り人量産のウハウハですわーにはならんでしょ
一般人からしたら超キモヲタ人種だし
- 200 名前：仕様書無しさん mailto:sage [2018/11/13(火) 11:53:53.38 .net]
- 入社したあと自社に貢献できるかも微妙かもね。
同期と横一線じゃろ
|
 |
