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

**仕様書無しさん** · 2018/08/18(土) 08:24:25.58

仕様書無しさん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あたりにテンプレ続く
※前スレ
競技プログラミングにハマるプログラマのスレ 15
http://medaka.5ch.net/test/read.cgi/prog/1526247830

**仕様書無しさん** · 2018/08/18(土) 15:09:28.54

おつおつ

**仕様書無しさん** · 2018/08/18(土) 16:13:07.12

>>1
乙！

**仕様書無しさん** · 2018/08/18(土) 19:25:00.18

１乙

**仕様書無しさん** · 2018/08/18(土) 20:06:57.03

今夜ＡＢＣだな！

**仕様書無しさん** · 2018/08/18(土) 20:17:33.91

マジかw風呂入らな

**仕様書無しさん** · 2018/08/18(土) 21:00:44.50

問題草生える

**仕様書無しさん** · 2018/08/18(土) 22:02:44.33

草が生えている

**仕様書無しさん** · 2018/08/18(土) 22:42:46.72

いつもどおりのＡ問題に絵がついた

**仕様書無しさん** · 2018/08/18(土) 22:43:09.49

ダメでした

**仕様書無しさん** · 2018/08/18(土) 22:44:19.25

むずすぎ

**仕様書無しさん** · 2018/08/18(土) 22:44:44.60

今回もD解けなかった
無念

**仕様書無しさん** · 2018/08/18(土) 22:46:17.41

B解けね
例題は解けたのに

**仕様書無しさん** · 2018/08/18(土) 22:47:11.31

セグメントツリーを使う問題だ！と勘違いして
ググりはじめて時間切れ

**仕様書無しさん** · 2018/08/18(土) 22:48:40.56

いつまでたってもDが解けるようにならないなあ

**仕様書無しさん** · 2018/08/18(土) 22:49:49.19

セグメントツリーだりーと思ったけどやらなくて通って草
ABCのみでもそれでいいのか

**仕様書無しさん** · 2018/08/18(土) 22:50:09.45

ABCでセグ木使わないといけない問題は出ないね

**仕様書無しさん** · 2018/08/18(土) 22:52:12.97

えっ！そうなの？？？

**仕様書無しさん** · 2018/08/18(土) 22:54:35.35

Dは二次元配列使って解いたけどもセグ木で解く場合は何の情報持たせるんだ?

**仕様書無しさん** · 2018/08/18(土) 22:54:45.22

いや、ググりながら400点に要求するテクにしては難し過ぎると思ったんだけども。
逆にこれセグ木で解こうとしたら解けるんです？

**仕様書無しさん** · 2018/08/18(土) 22:55:55.75

ABC106解説放送
https://youtu.be/OdJH-io-sVw

**仕様書無しさん** · 2018/08/18(土) 23:10:41.43

ソートして始点だけどN小さいから2次元の方が早い

**仕様書無しさん** · 2018/08/19(日) 01:40:28.68

Codeforces に出ると毎回すげえ汚いコードが生産される

**仕様書無しさん** · 2018/08/19(日) 21:16:58.46

きれいなコードだと、ミスがばれちゃう？？？

**仕様書無しさん** · 2018/08/19(日) 22:45:23.44

意図的な難読化はこどふぉでは禁止されている

**仕様書無しさん** · 2018/08/20(月) 01:18:15.59

うるせえ難読化のつもりはなくても簡潔な実装をする実力がないためにクソコードが生産されるんじゃい
そして今日もクソコードを生産した、TLEでハゲた
精進が足りん

**仕様書無しさん** · 2018/08/20(月) 02:31:32.47

atcoderで解説してる「りんご」さんの本名教えて

**仕様書無しさん** · 2018/08/20(月) 04:48:43.66

りんごさんコドフォとかのプロフィールに普通に本名書いてるよね

https://codeforces.com/profile/rng_58

**仕様書無しさん** · 2018/08/20(月) 19:23:25.16

D問題一向に解けない初学者だが、テンプレの書籍が何かの役に立つだろうか

**仕様書無しさん** · 2018/08/20(月) 19:34:17.44

教科書で基本を学ばず
いきなり問題集や試験問題を解けるだろうか

じゃあ教科書で基本を学べば試験問題を解くことも可能かもしれないが
問題集でしっかりと演習を積んだほうが試験問題をより確実に解けることだろう

さて、競プロ本と呼ばれる
蟻本、チーター本、螺旋本、これらは教科書なのか問題集なのか

**仕様書無しさん** · 2018/08/20(月) 20:22:36.60

そういった本まだ持ってないんだけど前提知識はどこまで求められてるのだろ

**仕様書無しさん** · 2018/08/20(月) 20:50:07.04

どれも自分で解くことは想定してないから教科書かな
問題集の役割は過去問が担っている

**仕様書無しさん** · 2018/08/20(月) 20:51:56.79

ひょっとしてABC全完目指すくらいまでは過去問やりこみが一番なんだろうか？

**仕様書無しさん** · 2018/08/20(月) 21:02:00.72

蟻本の前半くらいは読んどいたほうがいいと思う

**仕様書無しさん** · 2018/08/20(月) 22:05:27.26

第1回 Asprovaプログラミングコンテスト
https://www.asprova.com/jp/procon/procon1.php#nav

このコンテストやっとMM常連の人が登場してきたね

**仕様書無しさん** · 2018/08/20(月) 22:42:16.57

うーん買ってみるか

**仕様書無しさん** · 2018/08/20(月) 23:26:49.75

https://twitter.com/tanakh/status/1031543670674092033

tanakhさんのRustの競プロ用マクロ
これinteractive問題や入力データ数が入力含まれてない問題には対応していなさそうだけどとても便利そう

Rustで競技プログラミングスターターキット
https://qiita.com/hatoo@github/items/fa14ad36a1b568d14f3e
Rustで競プロに使えそうな入力取得用マクロ
https://qiita.com/gyu-don/items/73ed75d83a40d5d2785f
競プロRustスニペット集
https://github.com/hamadu/competitive-rust-snippets

Rustの日本語本が出たことだし
Rustで競プロもっと流行れ！
https://twitter.com/5chan_nel (5ch newer account)

**仕様書無しさん** · 2018/08/21(火) 00:09:25.78

D言語は競プロに向いてる言語だから普及させたいけど
C++/Rustと違って競プロ以外で実際に開発等に使用される話題では弱すぎるため普及力が弱い

D言語で競技プログラミング
http://yosupo.hatenablog.com/entry/2018/02/20/015531
D言語の競技プログラミング用ライブラリを作ってみた
http://yosupo.hatenablog.com/entry/2018/05/29/021518
競技プログラミングのためのD言語 (1/2)https://topcoder.g.hatena.ne.jp/cafelier/20120416/1334600551
競技プログラミングのためのD言語 (2/2)
https://topcoder.g.hatena.ne.jp/cafelier/20120416/1334600552

**仕様書無しさん** · 2018/08/21(火) 00:20:02.32

競プロはC++

**仕様書無しさん** · 2018/08/21(火) 00:22:15.06

蟻本の前半は基本的なテクニックが網羅的に書かれてるから
一度読んでおくと良いと思う
（基本的とは言ってもきちんと使いこなせれば青～黄色レベルにはなる）

**仕様書無しさん** · 2018/08/21(火) 07:14:02.41

過去問やれよ‥

**仕様書無しさん** · 2018/08/21(火) 13:20:29.42

両方やるに決まってるだろ

**仕様書無しさん** · 2018/08/21(火) 13:23:21.12

過去問だけやって実力つくほどのセンスないわ

**仕様書無しさん** · 2018/08/21(火) 14:08:54.92

蟻本無くてもABCのCまでなら行けるけどね

**仕様書無しさん** · 2018/08/21(火) 14:33:03.84

いやDまではいけるだろ

**仕様書無しさん** · 2018/08/21(火) 17:31:49.49

プログラミング未経験からならCまで
経験者ならDまで
これだろ

**仕様書無しさん** · 2018/08/21(火) 17:50:39.18

そもそも過去問といてる過程で経験者になるだろ

**仕様書無しさん** · 2018/08/21(火) 17:52:28.97

プログラミング経験の有無関係あるか？

**仕様書無しさん** · 2018/08/21(火) 18:47:38.79

無いな
むしろ数学的な知識と英語の知識が重要

**仕様書無しさん** · 2018/08/21(火) 19:50:15.38

ツイッターを「プログラミングコンテスト」で検索すると世の中色々なコンテストがあるんだなと実感する
https://twitter.com/search?f=tweets&;q=プログラミングコンテスト&src=typd

その中でとても怪しそうなコンテストがあった
怪しい

https://twitter.com/FPT_Japan/status/1031732651848228864
> FPTジャパンは、国籍・性別・年齢にとらわれないプログラマー同士の交流の場を創り出すことを目的とし、「第1回プログラミングコンテスト（ピカロンウォー）」を開催します。
> ■ 賞金総額：17,000 US$

> コンテストはオンライン部門とオフライン部門の2部構成で開催され、1チーム3人によるチーム制での参加となります。1位から3位までの受賞チームに対しては、豪華な賞が与えられます。

> オンラインの部☆
> ☆コンテストの内容：2種類あります☆
> AI部門
> コーディング部門
https://twitter.com/5chan_nel (5ch newer account)

**仕様書無しさん** · 2018/08/21(火) 22:40:57.29

強い人たちってこういう記事で顔や本名を公開されちゃうのな

CODE VSが示すプログラマに必要な戦略と問題解決能力
https://next.rikunabi.com/tech/docs/ct_s03600.jsp?p=002393
学生プログラマ日本一は誰？「CODE VS」決勝戦に潜入
https://next.rikunabi.com/tech/docs/ct_s03600.jsp?p=002311
CODE VS、Tech-Tokyo─決勝を制した学生ギークは誰？
https://next.rikunabi.com/tech/docs/ct_s03600.jsp?p=002037

**仕様書無しさん** · 2018/08/21(火) 22:43:04.46

流石に許可取ってんだろ

**仕様書無しさん** · 2018/08/21(火) 22:46:19.73

>>60
> chokudai氏は「むしろ競技プログラミング自体が、人生のさまざまな局面で役に立つ」という。

ホンマか？

**仕様書無しさん** · 2018/08/21(火) 22:55:04.75

>>60
1つ目の記事、めっちゃ競プロを褒めちぎっている…

**仕様書無しさん** · 2018/08/21(火) 23:00:57.80

絶賛している割にはCODE VSは開催予定無いようだけど

**仕様書無しさん** · 2018/08/21(火) 23:10:23.97

https://twitter.com/n_vip/status/1031902471688343554

このツイート見て思ったけど
各競プロサイトのコンテストで問題や想定解に間違いがあってトラブルったときの問題って過去問の公開では修正されているのだろうか
https://twitter.com/5chan_nel (5ch newer account)

**仕様書無しさん** · 2018/08/21(火) 23:26:09.76

どうなんだろう
こどふぉで一回嘘が想定解だったときは素直に謝罪しつつ誰か正当な解法考えてくれ～みたいな感じになってその後どうなったか知らない

**仕様書無しさん** · 2018/08/22(水) 00:13:21.65

明日CSAあるね
Round #86 (Div. 2 only)
https://csacademy.com/contest/round-86/

土曜にARC101/ABC107があるね
久々のARCでrating変動の緊張を再び味わえるね！やったね！
ARC https://beta.atcoder.jp/contests/arc101

( ABC https://beta.atcoder.jp/contests/abc107 )

https://clist.by より

ところでTOKIコンテスト、AtCoderのせいで時間被りしてるが大丈夫だろうか
TOKI Regular Open Contest #2
https://tlx.toki.id/contests/troc-2

**仕様書無しさん** · 2018/08/22(水) 00:23:21.70

>>67
インドネシアの人がTOKIを取るかAtCoderを取るかの問題だから
インドネシアの人はTOKIを選ぶだろうから大丈夫と予想しておく

前回そんなに反響なさそう

TOKI Regular Open Contest #1
https://codeforces.com/blog/entry/60812

**仕様書無しさん** · 2018/08/22(水) 00:25:35.40

ほぼインドネシア人のコンテストだね

https://tlx.toki.id/ranking

**仕様書無しさん** · 2018/08/22(水) 00:32:15.99

インドネシアのトップのレッドコーダーのjonathanirvingsさんGoogle務めなのかな？すごい
(インドネシアの人たちAtCoderで誕生年登録している人多いけど若い人多くてオッサンいなさそう)

https://beta.atcoder.jp/ranking?f.Country=ID
https://codeforces.com/ratings/country/Indonesia

https://beta.atcoder.jp/users/jonathanirvings
https://codeforces.com/profile/jonathanirvings
https://twitter.com/jonathanirvings
https://twitter.com/5chan_nel (5ch newer account)

**仕様書無しさん** · 2018/08/22(水) 00:40:15.47

このスレは今日からインドネシアになりました

**仕様書無しさん** · 2018/08/22(水) 01:00:36.32

>>59
このコンテスト主催のFPTジャパンについて軽く調べてみたけど
ベトナムにFPTグループって企業があってそこの子会社のFPTソフトウェアの日本法人がFPTジャパン
FPTグループは大学も運営していてコドフォにもその学生がたくさんいる

FPT University
https://codeforces.com/ratings/organization/89

https://en.wikipedia.org/wiki/FPT_University
https://en.wikipedia.org/wiki/FPT_Group
https://en.wikipedia.org/wiki/FPT_Software
https://www.fpt-software.jp/company-information/company-fact-sheet/
https://www.fpt-software.jp/company-information/fpt-japan/

怪しい企業じゃなくてよかったね！(ツイッターだけ見ると怪しい https://twitter.com/FPT_Japan )
https://twitter.com/5chan_nel (5ch newer account)

**仕様書無しさん** · 2018/08/22(水) 04:52:52.47

TOKI-OJは何故そこにコンテスト予定を立ててしまったのか…

https://medaka.5ch.net/test/read.cgi/prog/1526247830/757n

**仕様書無しさん** · 2018/08/22(水) 06:18:49.91

日本人にも参加しやすい時間帯のコンテストサイトになるか？

**仕様書無しさん** · 2018/08/22(水) 07:17:50.71

ARC070 のD問題のテストケースって弱い?
AC解答の実行時間でソートすると
8 100
1 1 8 8 8 25 26 50
で落ちそうなのがちらほら見えるのですけども

**仕様書無しさん** · 2018/08/22(水) 09:06:52.23

【料金泥棒】奪っても捕まらない業界【知財泥棒】

俺がSE辞めて人売りやる理由

・偽装請負多重派遣のSEに制裁を与えられる
・結婚相手を苦しめるSEに制裁を与えられる
・人売りは低額でできるから俺でもできる
・人売りは大儲けだから家族に奉仕できる
・SEは結婚障害者だから家族に迷惑かかる
・SEの多数は高額料金を提供してくれる
・SEの多数は知的財産を譲渡してくれる
・SEの多数は料金以上に開発してくれる
・SEの多数は搾取損害を訴えないでくれる
・SEを多重派遣したら責任問題を揉み消せる
・SEに不法行為しても機密誓約で揉み消せる
・SEを人身売買しても民事不介入の警察に捕まらない
・SEに料金以上の作業強要しても開発判断不能な警察や裁判官を騙せる
・SEに分量以上の作業強要しても開発判断不能な警察や裁判官を騙せる
・SEに契約以外の作業強要しても開発判断不能な警察や裁判官を騙せる
・SEを過労死や鬱病にしても開発判断不能な警察や裁判官を騙せる
・SEの報酬が不払いでも未完成と偽って開発判断不能な警察や裁判官を騙せる

お前らの金やプログラムを泥棒しても捕まらないからな

**仕様書無しさん** · 2018/08/22(水) 11:33:44.04

>>75
そのテストケースで落ちそうだってなんでわかるの？
いくつか遅い方のコードでコードテストしても通ったけど。

**仕様書無しさん** · 2018/08/22(水) 17:45:39.59

**仕様書無しさん** · 2018/08/22(水) 17:52:14.55

コードは読んでないけど嘘貪欲が通った感じなのかな？

**仕様書無しさん** · 2018/08/22(水) 17:56:14.90

落ちるってTLEじゃなくてWAであったか。

じゃあ>>75と同様のケースがテストケースに必要だな。

**仕様書無しさん** · 2018/08/22(水) 18:07:27.30

自分がＡＣしたコードでは、>>75で２だけど、

２なのか５なのか正解が気になる・・・・

**仕様書無しさん** · 2018/08/22(水) 18:08:04.05

コンテスト当時も嘘が通ってることに気づいてる人がチラホラ
(Codeforcesと違ってAtCoderはコンテスト当時の情報を掘り出すの厳しすぎる)

https://twitter.com/search?f=tweets&;q=D%20%20list%3Akobae964%2Fatcoder%20until%3A2017-03-20&src=typd
https://twitter.com/5chan_nel (5ch newer account)

**仕様書無しさん** · 2018/08/22(水) 18:12:29.41

カードiを含む和がK以上になる部分集合のうち
カードiを取り除くと和がK未満になる部分集合が存在するならカードiは必要
そうでないならカードiは不要
という問題かな？問題文分かりにくいな

**仕様書無しさん** · 2018/08/22(水) 18:14:49.07

解説ＰＤＦでもＤ問題の冒頭で間違ってるし、
ミスありまくりの問題だったのね。

**仕様書無しさん** · 2018/08/22(水) 18:30:26.11

>>82
agwさんのtogetterでは古いのはARC076/ABC065、AGC017までしかないのか…

https://togetter.com/id/masashinakata

**仕様書無しさん** · 2018/08/22(水) 18:33:50.65

Dのテストケースの弱さはコドフォのコメントでも指摘されてるね

AtCoder Regular Contest 070 and interactive problems - Codeforces
http://codeforces.com/blog/entry/50991

**仕様書無しさん** · 2018/08/22(水) 18:36:52.02

コドフォで怪しいレート分布の図を作った人がいるらしい

Rating Distribution
http://codeforces.com/blog/entry/61362

**仕様書無しさん** · 2018/08/22(水) 18:53:25.30

ARC070のD
問題点が明らかになっても、AtCoder は修正なしなのか？？？

**仕様書無しさん** · 2018/08/22(水) 19:08:37.09

修正はしなさそうだよ

https://twitter.com/chokudai/status/956736474476498944
https://twitter.com/5chan_nel (5ch newer account)

**仕様書無しさん** · 2018/08/22(水) 19:11:54.00

これも参考までに

https://twitter.com/chokudai/status/924289754631254020
https://twitter.com/chokudai/status/986840907872784385
https://twitter.com/5chan_nel (5ch newer account)

**仕様書無しさん** · 2018/08/22(水) 19:23:23.36

トヨタも虜にする｢天才が憧れる天才｣AI企業、PFNゴールデンチームの全貌
https://www.businessinsider.jp/post-173455

強い競プロerがたくさんいる企業だったっけか

**仕様書無しさん** · 2018/08/22(水) 19:26:54.04

>>81
1+8+8+8+25+50=100
25+26+50=100
なんで想定解答は0だと思われる

**仕様書無しさん** · 2018/08/22(水) 19:47:13.55

>>83
たぶん違うと思う

**仕様書無しさん** · 2018/08/22(水) 19:57:20.94

>>92
順位表の上位数名のコードだと答えが 0 になるね

https://beta.atcoder.jp/contests/arc070/standings

つまり 2 も 5 も別々の嘘解法かｗ

**仕様書無しさん** · 2018/08/22(水) 20:03:16.85

後からやる人用にテスト増やせばいいのに
やらなら除外した方がいいな

**仕様書無しさん** · 2018/08/22(水) 20:36:47.07

ARC070のD
>>75 の
8 100
1 1 8 8 8 25 26 50

だと見るからに、不必要な数は無しで０のはず。

２は、
1 1 8 8 8 25 50
=101
の時に１が１つ不要になるので
これを２回数えたか？？？

５は、
1 1 8 8 8 25 26 50
全ての集合の時に
５つ 1 1 8 8 8 を外せるからか？？？

**仕様書無しさん** · 2018/08/22(水) 21:00:08.94

>>83の解釈であってるでしょ

**仕様書無しさん** · 2018/08/22(水) 21:14:06.01

テストケースをＤＬして見てみると
不必要な数が０であるか全部不要だというテストケースが大半だな。

**仕様書無しさん** · 2018/08/22(水) 21:24:50.11

全５１個のテストケース中で、
正解の不要数が０と全部のいずれでもないのは１２個だけ。

**仕様書無しさん** · 2018/08/22(水) 23:01:31.56

CSAまであと1時間！

https://csacademy.com/contest/round-86/

Round #86 (Div. 2)
https://codeforces.com/blog/entry/61367

**仕様書無しさん** · 2018/08/22(水) 23:19:50.74

海外のコンテストは深夜すぎるな。

**仕様書無しさん** · 2018/08/22(水) 23:59:44.51

時差的にしゃーない

**仕様書無しさん** · 2018/08/23(木) 08:15:06.15

国内コンテストはありがたい

**仕様書無しさん** · 2018/08/23(木) 08:20:30.98

atcoderが小中学生狙うならもっと早く夕方にでもしなきゃだな。

**仕様書無しさん** · 2018/08/23(木) 09:45:10.56

小中学生狙うなら休日の昼間だな

**仕様書無しさん** · 2018/08/23(木) 10:41:47.28

yukicoderが匿名ログイン廃止！！！

お知らせ：8/23の夜　現状の匿名ログインは廃止されます。
今後はパスワードが必要になります。
したがって現状の匿名アカウントにはログインできなくなります。
今後ともSNSログインが推奨です

**仕様書無しさん** · 2018/08/23(木) 10:44:28.36

yukicoder contest 198
2018-08-24 21:20:20〜
2018-08-24 23:20:20

20秒ってとこが間違いだな。

**仕様書無しさん** · 2018/08/23(木) 14:29:46.07

変な競プロマンガがあるらしい。

競技プログラマー情(ジョー): 第一話：Hello World (同人誌)

https://www.amazon.co.jp/%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%83%BC%E6%83%85-%E3%82%B8%E3%83%A7%E3%83%BC-%E7%AC%AC%E4%B8%80%E8%A9%B1%EF%BC%9AHello-World-%E5%90%8C%E4%BA%BA%E8%AA%8C-ebook/dp/B01MS53YUZ

http://satelliteyezu.hatenablog.com/entry/2016/12/19/162610

**仕様書無しさん** · 2018/08/23(木) 17:22:39.94

相変わらず、ABCのC問題が安定して解けず
D問題はほぼまるで解けないんだけど
これやっぱり解放暗記的に数こなすしか無いの？
蟻本ってのはたぶんもっと難しいレベルだよね？

**仕様書無しさん** · 2018/08/23(木) 17:37:03.75

Ｃ問題のＣ＋＋でのＡＣコードを見て何やってる分かるぐらいなら
難しいってことは無いばず。

他の競プロ本も同じ。