X
競技プログラミングにハマるプログラマのスレ 13
■ このスレッドは過去ログ倉庫に格納されています
0001仕様書無しさん
垢版 |
2017/11/29(水) 17:17:11.56
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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にテンプレ続く
0002仕様書無しさん
垢版 |
2017/11/29(水) 17:17:50.05
# 高校生・大学生対象コンテスト
情報オリンピック https://www.ioi-jp.org/
ACM-ICPC http://icpc.iisf.or.jp/

# その他便利なサイト
コンテスト・カレンダー
https://competitiveprogramming.info/calendar
http://clist.by/
AtCoder Problems http://kenkoooo.com/atcoder/
オンライン整数列大辞典 https://oeis.org/?language=japanese
WolframAlpha https://www.wolframalpha.com/
Spaghetti Source
旧: http://www.prefield.com/algorithm/
新: https://github.com/spaghetti-source/algorithm
競技プログラミングwiki http://wikiwiki.jp/kyopro/
AOJ-ICPC http://aoj-icpc.ichyo.jp/
competitiveprogramming.info https://competitiveprogramming.info/
競プロSlack https://competitiveprogramming.info/slack
OnlineJudgeHelper (オンラインジャッジ補助スクリプト) https://github.com/nodchip/OnlineJudgeHelper
Google翻訳 https://translate.google.co.jp/

>>3にテンプレ続く
0003仕様書無しさん
垢版 |
2017/11/29(水) 17:18:51.89
# 書籍
プログラミングコンテストチャレンジブック (蟻本)
https://www.amazon.co.jp/dp/4839941068/
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (AOJ本, TLE本, 渦巻本)
https://www.amazon.co.jp/dp/4839952957/
最強最速アルゴリズマー養成講座 (チーター本)
https://www.amazon.co.jp/dp/4797367172/

# 日本人競技プログラマ
Twitter 競技プログラマリスト
https://twitter.com/kinaba/lists/topcoder-jp
https://twitter.com/kobae964/lists/atcoder
TopCoder Single Round Match (SRM) のランキング
https://community.topcoder.com/tc?cc=392&;sc=&sd=&cc=392&module=AlgoRank&nr=200&sr=
TopCoder Marathon Match (MM) ランキング
https://community.topcoder.com/longcontest/stats/?module=CoderRank&;cc=392
Codeforces ランキング
http://codeforces.com/ratings/country/Japan

>>4にテンプレ続く
0004仕様書無しさん
垢版 |
2017/11/29(水) 17:19:30.65
# 過去スレ
1: http://tamae.2ch.net/test/read.cgi/prog/1443271207/
2: http://tamae.2ch.net/test/read.cgi/prog/1461096973/
3: http://tamae.2ch.net/test/read.cgi/prog/1468710465/
4: http://tamae.2ch.net/test/read.cgi/prog/1470294745/
5: http://tamae.2ch.net/test/read.cgi/prog/1472132297/
6: http://tamae.2ch.net/test/read.cgi/prog/1479623072/
7: http://tamae.2ch.net/test/read.cgi/prog/1482151701/
8: http://tamae.2ch.net/test/read.cgi/prog/1483782812/
9: http://tamae.2ch.net/test/read.cgi/prog/1487426332/
10: http://medaka.2ch.net/test/read.cgi/prog/1493085730/
11: http://medaka.2ch.net/test/read.cgi/prog/1498137486/
12: https://medaka.5ch.net/test/read.cgi/prog/1505047495/
# 関連スレ
【したらば】プロコン・競プロ・ハッカソン・CTFなどについて語り合う掲示板
http://jbbs.shitaraba.net/internet/13109/
TopCoder
http://mevius.2ch.net/test/read.cgi/tech/1333159918/l50
プログラミングのお題スレ Part9 [無断転載禁止]c2ch.net
http://mevius.2ch.net/test/read.cgi/tech/1480579110/
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3c2ch.net
http://mevius.2ch.net/test/read.cgi/tech/1466315249/l50
【会津】パソコン甲子園2004【若松】
http://mevius.2ch.net/test/read.cgi/tech/1094308951/l50
CTFについて語るスレ [無断転載禁止]c2ch.net
http://medaka.2ch.net/test/read.cgi/sec/1476430177/l50

ここまでテンプレ
0005仕様書無しさん
垢版 |
2017/11/29(水) 17:21:57.52
テンプレはTopCoder部のカレンダーが古かったので変えたのとTwitterのリストを追加しました
0007仕様書無しさん
垢版 |
2017/11/29(水) 18:03:32.44
TopcoderMMの上位外国人の一部はCOPILOTだからAtCoderには参戦していない？
0013仕様書無しさん
垢版 |
2017/11/29(水) 20:04:35.39
最近のAtCoderは忙しそうだからchokudaiさんスレ見てなさそう
0015仕様書無しさん
垢版 |
2017/11/30(木) 20:05:24.77
北大×日立のコンテストの2ncは参加者が少ないからが50位以内の記念品圏内狙いやすそう
0016仕様書無しさん
垢版 |
2017/11/30(木) 20:12:38.94
ウェザーニューズのコンテストと被ってるけど大丈夫なんだろうかアットコーダー
0019仕様書無しさん
垢版 |
2017/11/30(木) 22:54:16.65
完全に忘れてた。
出なくちゃ。
0020仕様書無しさん
垢版 |
2017/11/30(木) 23:01:51.72
マラソンマッチ上位者らの話を読んでこれが上位のテクなんじゃないかと思うところ

[1] (自分にとって状態やスコアなどが)ビジュアライザを作る （GUIツールくらいちょちょいで作れるくらいのスキルを身に付ける）

[2] 順番に並べるなど適当に並べただけの状態の解に焼きなまし法を長時間(コンテストの実行時間を大きく超えて)使ってより最適解に近い状態の解をビジュアライザ等の解析ツールで分析する
　　（近傍は解の２つの要素交換とか１つ隣に移動させるとかハミング距離(?)の近い距離で移動で遷移させる）

[3] 分析した最適解により近い形を貪欲法やビームサーチなどで作りあげ初期値としてから焼きなまし法する

[4] 焼きなまし法はループ回数が多いほど良いらしいのでひたすら高速化
0021仕様書無しさん
垢版 |
2017/11/30(木) 23:07:28.19
[2]-[3]を繰り返し繰り返しすることでよりよい解にたどり着けるのではなかろうか
0022仕様書無しさん
垢版 |
2017/11/30(木) 23:23:21.84
chokudaiさんはアルゴリズマーだから
競プロで使うアルゴリズムもマラソンマッチで使うアルゴリズムも機械学習で使うアルゴリズムもAIで使うアルゴリズムも
ありとあらゆるアルゴリズムに強そう
0030仕様書無しさん
垢版 |
2017/12/01(金) 00:38:52.09
マラソンマッチと競プロの両方で使えるテクニックとか誰か記事書いてほしいね
0035仕様書無しさん
垢版 |
2017/12/02(土) 18:08:34.59
強いマラソンerが漏れなく並べられてる公開twitterリストは無さそう
0038仕様書無しさん
垢版 |
2017/12/02(土) 22:33:28.41
>>35
今回のマラソンで全員AtCoder勢になったということでKさんがリストに追加してくれるはず…!!
0040仕様書無しさん
垢版 |
2017/12/02(土) 23:00:15.38
こどふぉることもunratedになることも無いことを祈るばかり
0045仕様書無しさん
垢版 |
2017/12/03(日) 01:23:51.96
こどふぉが糞回だとそれにでてくるアニメのキャラの印象が最悪になる現象
0046仕様書無しさん
垢版 |
2017/12/03(日) 01:26:54.01
初参加でコドフォよくわからないけど糞問だったの？（一完）
BはOEIS使ったけどバグって通らなかった
0048仕様書無しさん
垢版 |
2017/12/03(日) 01:50:10.23
ゴミ問題にゴミシステムがあわさったゴミラウンド
0050仕様書無しさん
垢版 |
2017/12/03(日) 02:47:20.70
北大×日立マラソンに夢中ですっかり忘れてたがSamurAIcoding

ルールとかビジュアライザとか？
https://github.com/SamurAI-Coding/Software2017-18
https://github.com/SamurAI-Coding/Software2017-18/blob/master/documents/rule-jp.pdf

数日前からサイトが落ちてるらしい
http://samuraicoding.info/index-jp.html

https://twitter.com/IpsjSamurAI/status/920366979898269696
日立がゴールドスポンサーとのことだからAtCoderと競合？
0051仕様書無しさん
垢版 |
2017/12/03(日) 03:10:29.76
これ普通のratedだと単純にいまの倍変動してたって認識でいいんだろうか
0052仕様書無しさん
垢版 |
2017/12/03(日) 16:47:13.72
Codeforcesは夜中だから出ていないけど出なくてよかったと思うことのほうが多い
0053仕様書無しさん
垢版 |
2017/12/03(日) 18:04:50.87
贅沢言ってるとatcoder以外にでるとこなくなっちゃうからなあ
0054仕様書無しさん
垢版 |
2017/12/03(日) 18:08:38.18
贅沢言っても出れるatcoderってすげえ
0061仕様書無しさん
垢版 |
2017/12/03(日) 22:43:28.86
問題の文章が分かりにくくても上位の人たちの解答速度すごい
0062仕様書無しさん
垢版 |
2017/12/03(日) 22:53:07.59
C問題の意味がわかったら
残り時間１０分だった・・・
0063仕様書無しさん
垢版 |
2017/12/03(日) 22:56:56.80
CとDの問題文が分かりづらくて時間かかってしまった
全探索と典型だから問題文さえ分かりやすければもっと早くに提出できた
（問題文が分かりやすければ他の人も提出早くなるので順位は変わらんかもしれん）
0064仕様書無しさん
垢版 |
2017/12/03(日) 22:57:53.21
CもDもひどい問題文だ。

問題文はあきらめて
入出力例から予想して解くことになるな。
0067仕様書無しさん
垢版 |
2017/12/03(日) 23:00:18.57
上位の人たちは、入出力例からすぐに問題が分かるんだろう
0070仕様書無しさん
垢版 |
2017/12/03(日) 23:02:52.42
こりゃ読解力ではＡＣできない。

問題文は、回答者を混乱させるだけ
0071仕様書無しさん
垢版 |
2017/12/03(日) 23:05:20.64
Dは典型だから入力から予想できそうではあるけど
0072仕様書無しさん
垢版 |
2017/12/03(日) 23:06:05.43
確かにちょっと分かりにくかったが言うほど酷くはないでしょ
0075仕様書無しさん
垢版 |
2017/12/03(日) 23:08:59.27
問題文が普通だったら、簡単な問題ばかり
0076仕様書無しさん
垢版 |
2017/12/03(日) 23:13:37.17
ABCなら水色以上なら全完当然の易しい問題ばかりなのは普通
0077仕様書無しさん
垢版 |
2017/12/03(日) 23:14:27.12
ABC(only回)なら水色以上なら全完当然の易しい問題ばかりなのは普通
0079仕様書無しさん
垢版 |
2017/12/03(日) 23:20:55.16
最近のABC/ARCのCとDは1年前の頃より難易度が下がってきているように感じるのは俺のレベルが上がったからだろうか
0080仕様書無しさん
垢版 |
2017/12/03(日) 23:22:06.33
レベルが上がってすばらしいね
0083仕様書無しさん
垢版 |
2017/12/03(日) 23:29:44.96
>>72
これが競プロ脳か
数多くの競プロ問題に触れる熟練者はそれこぞ数多くの悪問に出会い慣れて感覚がマヒしている状態
(冗談です)
0084仕様書無しさん
垢版 |
2017/12/03(日) 23:32:14.97
英語苦手だからどんな悪文だろうと日本語で提供されてるだけで感謝してる
けど今回は読めなかったなぁ
0085仕様書無しさん
垢版 |
2017/12/03(日) 23:33:07.36
やはりこの難易度のセットだとパフォーマンスあまり出なくてレーティングあんま上がらんどふぉ
0086仕様書無しさん
垢版 |
2017/12/03(日) 23:35:23.26
そろそろコンテストサイトを擬人化する人々が現れてもいいころでは
0088仕様書無しさん
垢版 |
2017/12/03(日) 23:56:22.05
C問題は
商店街に何とか姉ちゃんの店と店１〜店Nの店が存在していて
店１〜店Ｎの営業してる曜日と時間帯が与えられて
何とか姉ちゃんの店が店ｉと営業曜日と時間帯がカブった回数に応じて何とか姉ちゃんの店の利益が決まるというデータが与えられて
何とか姉ちゃんの店が一番儲かる何とか姉ちゃんの店の営業する曜日と時間帯の組み合わせを探してその利益を答えろって問題

組み合わせ全通り探索
月曜の午前・月曜の午後・火曜の午前・・・土曜の午後の１０の日にちそれぞれに営業するかしないか決める探索
組み合わせ１つごとに店１〜店Ｎとの各営業日時競合回数調べて利益計算
0090仕様書無しさん
垢版 |
2017/12/04(月) 00:06:08.39
D問題の-0.5の制限が録画が同じチャンネルだと影響受けないって部分が分かりにくかった
0091仕様書無しさん
垢版 |
2017/12/04(月) 00:09:34.32
入力情報(NとかAとかがかかれてるやつ)を見ながら問題読むと理解しやすい気がする
0092仕様書無しさん
垢版 |
2017/12/04(月) 00:13:38.48
AGC以外のARC/ABCの問題は審査甘めで採用されるらしいから多少アな問題も出ることもある
0094仕様書無しさん
垢版 |
2017/12/04(月) 00:36:08.24
入力例１はこれか
1
1 1 0 1 0 0 0 1 0 1　　←　店１が営業してる曜日・時間帯のとこは1、休業は0、店１は営業してるのは５箇所の曜日時間帯だけ
3 4 5 6 7 8 9 -2 -3 4 -2

店１と営業日が1回もカブらない場合は利益3
店１と営業日が1回だけカブる場合は利益4
店１と営業日が2回だけカブる場合は利益5
店１と営業日が3回だけカブる場合は利益6
店１と営業日が4回だけカブる場合は利益7
店１と営業日が5回だけカブる場合は利益8
店１と営業日が6回だけカブる場合は利益9　←店１は５箇所しか営業してないので6回以上カブることはない
店１と営業日が7回だけカブる場合は利益-2
店１と営業日が8回だけカブる場合は利益-3
店１と営業日が9回だけカブる場合は利益4
店１と営業日が10回だけカブる場合は利益-2
0095仕様書無しさん
垢版 |
2017/12/04(月) 00:46:50.21
私の競プロの楽しみ方

解けるべき問題をリアルタイムでコンテスト時間内に解けるかどうかを楽しんでいる
0096仕様書無しさん
垢版 |
2017/12/04(月) 00:49:05.09
>>94
サンクス。全く問題からは読み取れんな。どうしたら解けるようになるんだろ。
0097仕様書無しさん
垢版 |
2017/12/04(月) 00:55:10.94
コンテストで高ぶった気持ちを落ち着けて
冷静になって問題文を読む、読み直す
読み取れた情報を紙に箇条書きでもいいのでメモして情報を整理することもよい
メモした情報と問題文に齟齬が無いか確認するのもよい

情報を読み取る力は訓練で身につけられる
(競プロに限らず情報を読み取る力は大事)
0098仕様書無しさん
垢版 |
2017/12/04(月) 00:55:56.96
入力サンプルの説明や質問タブの確認も怠ることなく
0099仕様書無しさん
垢版 |
2017/12/04(月) 01:16:50.77
何とか姉ちゃんで思ったけど、競プロの問題文に出す人物の名前、太郎とか次郎とか分かりやすい名前にして全部統一してほしい
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況