競技プログラミングにハマるプログラマのスレ 13

**仕様書無しさん** · 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にテンプレ続く

**仕様書無しさん** · 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にテンプレ続く

**仕様書無しさん** · 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にテンプレ続く

**仕様書無しさん** · 2017/11/29(水) 17:19:30.65

**仕様書無しさん** · 2017/11/29(水) 17:21:57.52

テンプレはTopCoder部のカレンダーが古かったので変えたのとTwitterのリストを追加しました

**仕様書無しさん** · 2017/11/29(水) 17:31:41.58

乙

**仕様書無しさん** · 2017/11/29(水) 18:03:32.44

TopcoderMMの上位外国人の一部はCOPILOTだからAtCoderには参戦していない？

**仕様書無しさん** · 2017/11/29(水) 18:18:10.56

>>1おつ

**仕様書無しさん** · 2017/11/29(水) 18:24:31.13

https://twitter.com/chokudai/status/935698499542269952

なんちゅう強引な

**仕様書無しさん** · 2017/11/29(水) 18:27:39.82

https://twitter.com/chokudai/status/935707784330350592
AtCoderとツイートしてchokudai釣ろうぜ

**仕様書無しさん** · 2017/11/29(水) 19:09:36.88

>>1-5
乙

**仕様書無しさん** · 2017/11/29(水) 19:26:12.97

chokudai先生はこのスレ見てた気がするけど…

**仕様書無しさん** · 2017/11/29(水) 20:04:35.39

最近のAtCoderは忙しそうだからchokudaiさんスレ見てなさそう

**仕様書無しさん** · 2017/11/29(水) 21:04:09.30

https://twitter.com/kenkoooo/status/935818208430366720

AtCoder Problemsが新しくなるらしい

**仕様書無しさん** · 2017/11/30(木) 20:05:24.77

北大×日立のコンテストの2ncは参加者が少ないからが50位以内の記念品圏内狙いやすそう

**仕様書無しさん** · 2017/11/30(木) 20:12:38.94

ウェザーニューズのコンテストと被ってるけど大丈夫なんだろうかアットコーダー

**仕様書無しさん** · 2017/11/30(木) 20:13:28.48

>>16 勘違いしてた被ってなかった、スマソ

**仕様書無しさん** · 2017/11/30(木) 22:44:41.42

マラソンだけじゃなく競プロも頑張りましょう！

12/1の0時ちょうどからyukicoder Advent Calendar Contest(24日間)が始まります
https://yukicoder.me/contests/182

12/1の18時半からCodeChef December Challenge 2017(10日間)が始まります
https://www.codechef.com/DEC17

**仕様書無しさん** · 2017/11/30(木) 22:54:16.65

完全に忘れてた。
出なくちゃ。

**仕様書無しさん** · 2017/11/30(木) 23:01:51.72

マラソンマッチ上位者らの話を読んでこれが上位のテクなんじゃないかと思うところ

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

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

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

[4] 焼きなまし法はループ回数が多いほど良いらしいのでひたすら高速化

**仕様書無しさん** · 2017/11/30(木) 23:07:28.19

[2]-[3]を繰り返し繰り返しすることでよりよい解にたどり着けるのではなかろうか

**仕様書無しさん** · 2017/11/30(木) 23:23:21.84

chokudaiさんはアルゴリズマーだから
競プロで使うアルゴリズムもマラソンマッチで使うアルゴリズムも機械学習で使うアルゴリズムもAIで使うアルゴリズムも
ありとあらゆるアルゴリズムに強そう

**仕様書無しさん** · 2017/11/30(木) 23:37:58.22

×強そう
○強い

**仕様書無しさん** · 2017/11/30(木) 23:41:31.06

ゆきこだのアドベコン
１問目のFAを狙いに行く

**仕様書無しさん** · 2017/11/30(木) 23:57:45.57

https://shindanmaker.com/539444
yukicoderのおみくじ

**仕様書無しさん** · 2017/11/30(木) 23:58:30.20

よしこーなー

**仕様書無しさん** · 2017/11/30(木) 23:59:50.52

へべれけに酔っ払っているけどyukicoderいくよ！

【ぴょん吉】 · 2017/12/01(金) 00:32:16.83

アドベントカレンダー

「競プロ!!」競技プログラミング Advent Calendar 2017 - Adventar
https://adventar.org/calendars/2221

Competitive Programming Advent Calendar 2017 - Adventar
https://adventar.org/calendars/2437

解説 Advent Calendar 2017 - Adventar
https://adventar.org/calendars/2398

Advent Calendar Contest Advent Calendar 2017 - Adventar
https://adventar.org/calendars/2214

**仕様書無しさん** · 2017/12/01(金) 00:36:49.60

>>28
診断人さんのカレンダー空きが多いね

**仕様書無しさん** · 2017/12/01(金) 00:38:52.09

マラソンマッチと競プロの両方で使えるテクニックとか誰か記事書いてほしいね

**仕様書無しさん** · 2017/12/01(金) 20:26:57.80

Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017 - Togetter
https://togetter.com/li/1176965

**仕様書無しさん** · 2017/12/01(金) 22:57:15.56

こどふぉは明日か…

**仕様書無しさん** · 2017/12/02(土) 01:43:07.32

ゆきこだアドベコン中は毎日だよ

**仕様書無しさん** · 2017/12/02(土) 01:44:21.52

ところで
いろはちゃん深夜にツイートとは何事ですか
https://twitter.com/codera_iroha/status/936626300722208768

**仕様書無しさん** · 2017/12/02(土) 18:08:34.59

強いマラソンerが漏れなく並べられてる公開twitterリストは無さそう

**仕様書無しさん** · 2017/12/02(土) 18:24:17.47

ずっと避けてきたけど初コドフォやろうかな

**仕様書無しさん** · 2017/12/02(土) 18:52:10.94

避ける必要なんてないぞ
突っ込め

**仕様書無しさん** · 2017/12/02(土) 22:33:28.41

>>35
今回のマラソンで全員AtCoder勢になったということでKさんがリストに追加してくれるはず…!!

**仕様書無しさん** · 2017/12/02(土) 22:58:14.46

Is it rated?

**仕様書無しさん** · 2017/12/02(土) 23:00:15.38

こどふぉることもunratedになることも無いことを祈るばかり

**仕様書無しさん** · 2017/12/02(土) 23:03:58.26

よしこーなー

**仕様書無しさん** · 2017/12/02(土) 23:08:26.76

海外の競プロer、日本アニメオタク率高い

**仕様書無しさん** · 2017/12/03(日) 00:57:04.18

地獄のコドフォ

**仕様書無しさん** · 2017/12/03(日) 01:21:28.17

デビューには最悪の回だったね

**仕様書無しさん** · 2017/12/03(日) 01:23:51.96

こどふぉが糞回だとそれにでてくるアニメのキャラの印象が最悪になる現象

**仕様書無しさん** · 2017/12/03(日) 01:26:54.01

初参加でコドフォよくわからないけど糞問だったの？（一完）
BはOEIS使ったけどバグって通らなかった

**仕様書無しさん** · 2017/12/03(日) 01:40:08.12

semi-ratedという新概念が誕生した

**仕様書無しさん** · 2017/12/03(日) 01:50:10.23

ゴミ問題にゴミシステムがあわさったゴミラウンド

**仕様書無しさん** · 2017/12/03(日) 02:00:42.43

キャラクター付きの回は地雷率高い気がする

**仕様書無しさん** · 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と競合？

**仕様書無しさん** · 2017/12/03(日) 03:10:29.76

これ普通のratedだと単純にいまの倍変動してたって認識でいいんだろうか

**仕様書無しさん** · 2017/12/03(日) 16:47:13.72

Codeforcesは夜中だから出ていないけど出なくてよかったと思うことのほうが多い

**仕様書無しさん** · 2017/12/03(日) 18:04:50.87

贅沢言ってるとatcoder以外にでるとこなくなっちゃうからなあ

**仕様書無しさん** · 2017/12/03(日) 18:08:38.18

贅沢言っても出れるatcoderってすげえ

**仕様書無しさん** · 2017/12/03(日) 18:28:55.97

21時からABC Onlyです
https://beta.atcoder.jp/contests/abc080
100 - 200 - 300 - 400

**仕様書無しさん** · 2017/12/03(日) 21:34:13.10

ABC全完できた

**仕様書無しさん** · 2017/12/03(日) 21:58:48.11

おめでとん

**仕様書無しさん** · 2017/12/03(日) 22:02:49.53

Cの文章わかりにくい

**仕様書無しさん** · 2017/12/03(日) 22:12:04.80

readforces

**仕様書無しさん** · 2017/12/03(日) 22:31:01.09

C問題意味わかんねー(´・ω・｀)

**仕様書無しさん** · 2017/12/03(日) 22:43:28.86

問題の文章が分かりにくくても上位の人たちの解答速度すごい

**仕様書無しさん** · 2017/12/03(日) 22:53:07.59

C問題の意味がわかったら
残り時間１０分だった・・・

**仕様書無しさん** · 2017/12/03(日) 22:56:56.80

CとDの問題文が分かりづらくて時間かかってしまった
全探索と典型だから問題文さえ分かりやすければもっと早くに提出できた
（問題文が分かりやすければ他の人も提出早くなるので順位は変わらんかもしれん）

**仕様書無しさん** · 2017/12/03(日) 22:57:53.21

CもDもひどい問題文だ。

問題文はあきらめて
入出力例から予想して解くことになるな。

**仕様書無しさん** · 2017/12/03(日) 22:59:12.29

競プロコンテストではなく読解力コンテスト

**仕様書無しさん** · 2017/12/03(日) 22:59:32.03

質問タブに助けられた

**仕様書無しさん** · 2017/12/03(日) 23:00:18.57

上位の人たちは、入出力例からすぐに問題が分かるんだろう

**仕様書無しさん** · 2017/12/03(日) 23:01:08.72

>>61
強い人たちマジ化物

**仕様書無しさん** · 2017/12/03(日) 23:02:00.67

読解力はどうすれば鍛えられるの？

**仕様書無しさん** · 2017/12/03(日) 23:02:52.42

こりゃ読解力ではＡＣできない。

問題文は、回答者を混乱させるだけ

**仕様書無しさん** · 2017/12/03(日) 23:05:20.64

Dは典型だから入力から予想できそうではあるけど

**仕様書無しさん** · 2017/12/03(日) 23:06:05.43

確かにちょっと分かりにくかったが言うほど酷くはないでしょ

**仕様書無しさん** · 2017/12/03(日) 23:07:03.11

これはsemi-ratedが必用ですな

**仕様書無しさん** · 2017/12/03(日) 23:08:53.69

解説放送はなしか

**仕様書無しさん** · 2017/12/03(日) 23:08:59.27

問題文が普通だったら、簡単な問題ばかり

**仕様書無しさん** · 2017/12/03(日) 23:13:37.17

ABCなら水色以上なら全完当然の易しい問題ばかりなのは普通

**仕様書無しさん** · 2017/12/03(日) 23:14:27.12

ABC(only回)なら水色以上なら全完当然の易しい問題ばかりなのは普通

**仕様書無しさん** · 2017/12/03(日) 23:18:53.25

ハラスメントを観測しました

**仕様書無しさん** · 2017/12/03(日) 23:20:55.16

最近のABC/ARCのCとDは1年前の頃より難易度が下がってきているように感じるのは俺のレベルが上がったからだろうか

**仕様書無しさん** · 2017/12/03(日) 23:22:06.33

レベルが上がってすばらしいね

**仕様書無しさん** · 2017/12/03(日) 23:25:30.52

動画の準備に手間取っていたのかな？

**仕様書無しさん** · 2017/12/03(日) 23:25:57.55

俺のレベルは下がる一方でショボンとするw

**仕様書無しさん** · 2017/12/03(日) 23:29:44.96

>>72
これが競プロ脳か
数多くの競プロ問題に触れる熟練者はそれこぞ数多くの悪問に出会い慣れて感覚がマヒしている状態
(冗談です)

**仕様書無しさん** · 2017/12/03(日) 23:32:14.97

英語苦手だからどんな悪文だろうと日本語で提供されてるだけで感謝してる
けど今回は読めなかったなぁ

**仕様書無しさん** · 2017/12/03(日) 23:33:07.36

やはりこの難易度のセットだとパフォーマンスあまり出なくてレーティングあんま上がらんどふぉ

**仕様書無しさん** · 2017/12/03(日) 23:35:23.26

そろそろコンテストサイトを擬人化する人々が現れてもいいころでは

**仕様書無しさん** · 2017/12/03(日) 23:45:36.77

りんごさんの解説聞いてもC問題意味わからんw

**仕様書無しさん** · 2017/12/03(日) 23:56:22.05

C問題は
商店街に何とか姉ちゃんの店と店１～店Nの店が存在していて
店１～店Ｎの営業してる曜日と時間帯が与えられて
何とか姉ちゃんの店が店ｉと営業曜日と時間帯がカブった回数に応じて何とか姉ちゃんの店の利益が決まるというデータが与えられて
何とか姉ちゃんの店が一番儲かる何とか姉ちゃんの店の営業する曜日と時間帯の組み合わせを探してその利益を答えろって問題

組み合わせ全通り探索
月曜の午前・月曜の午後・火曜の午前・・・土曜の午後の１０の日にちそれぞれに営業するかしないか決める探索
組み合わせ１つごとに店１～店Ｎとの各営業日時競合回数調べて利益計算

**仕様書無しさん** · 2017/12/03(日) 23:59:44.01

競プロerには文章力がない

**仕様書無しさん** · 2017/12/04(月) 00:06:08.39

D問題の-0.5の制限が録画が同じチャンネルだと影響受けないって部分が分かりにくかった

**仕様書無しさん** · 2017/12/04(月) 00:09:34.32

入力情報(NとかAとかがかかれてるやつ)を見ながら問題読むと理解しやすい気がする

**仕様書無しさん** · 2017/12/04(月) 00:13:38.48

AGC以外のARC/ABCの問題は審査甘めで採用されるらしいから多少アな問題も出ることもある

**仕様書無しさん** · 2017/12/04(月) 00:14:53.61

>>88
入力例1はなんで利益8になるのかわからんのだが？

**仕様書無しさん** · 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

**仕様書無しさん** · 2017/12/04(月) 00:46:50.21

私の競プロの楽しみ方

解けるべき問題をリアルタイムでコンテスト時間内に解けるかどうかを楽しんでいる

**仕様書無しさん** · 2017/12/04(月) 00:49:05.09

>>94
サンクス。全く問題からは読み取れんな。どうしたら解けるようになるんだろ。

**仕様書無しさん** · 2017/12/04(月) 00:55:10.94

コンテストで高ぶった気持ちを落ち着けて
冷静になって問題文を読む、読み直す
読み取れた情報を紙に箇条書きでもいいのでメモして情報を整理することもよい
メモした情報と問題文に齟齬が無いか確認するのもよい

情報を読み取る力は訓練で身につけられる
(競プロに限らず情報を読み取る力は大事)

**仕様書無しさん** · 2017/12/04(月) 00:55:56.96

入力サンプルの説明や質問タブの確認も怠ることなく

**仕様書無しさん** · 2017/12/04(月) 01:16:50.77

何とか姉ちゃんで思ったけど、競プロの問題文に出す人物の名前、太郎とか次郎とか分かりやすい名前にして全部統一してほしい

**仕様書無しさん** · 2017/12/04(月) 01:19:56.68

uwiさんのよしこーなー何と思ったらHackerRankか

**仕様書無しさん** · 2017/12/04(月) 01:20:57.10

一時期高橋くんだけだったから華があるとは思う