X
競技プログラミングにハマるプログラマのスレ 16
■ このスレッドは過去ログ倉庫に格納されています
0001仕様書無しさん垢版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
0002仕様書無しさん垢版2018/08/18(土) 08:26:32.61
テンプレ続き

# 高校生・大学生対象コンテスト
情報オリンピック 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-10あたりにテンプレ続く
0003仕様書無しさん垢版2018/08/18(土) 08:27:43.46
テンプレ続き

# 書籍
プログラミングコンテストチャレンジブック (蟻本)
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-10あたりにテンプレ続く
https://twitter.com/5chan_nel (5ch newer account)
0004仕様書無しさん垢版2018/08/18(土) 08:37:31.64
テンプレ続き (2ch.netから5ch.netに、httpはhttpsにしました)

# 過去スレ
1: https://tamae.5ch.net/test/read.cgi/prog/1443271207/
2: https://tamae.5ch.net/test/read.cgi/prog/1461096973/
3: https://tamae.5ch.net/test/read.cgi/prog/1468710465/
4: https://tamae.5ch.net/test/read.cgi/prog/1470294745/
5: https://tamae.5ch.net/test/read.cgi/prog/1472132297/
6: https://tamae.5ch.net/test/read.cgi/prog/1479623072/
7: https://tamae.5ch.net/test/read.cgi/prog/1482151701/
8: https://tamae.5ch.net/test/read.cgi/prog/1483782812/
9: https://tamae.5ch.net/test/read.cgi/prog/1487426332/
10: https://medaka.5ch.net/test/read.cgi/prog/1493085730/
11: https://medaka.5ch.net/test/read.cgi/prog/1498137486/
12: https://medaka.5ch.net/test/read.cgi/prog/1505047495/
13: https://medaka.5ch.net/test/read.cgi/prog/1511943431/
14: https://medaka.5ch.net/test/read.cgi/prog/1517756393/
15: https://medaka.5ch.net/test/read.cgi/prog/1526247830/

>>5-10あたりにテンプレ続く
0005仕様書無しさん垢版2018/08/18(土) 08:38:47.78
テンプレ続き

# 関連スレ
【したらば】プロコン・競プロ・ハッカソン・CTFなどについて語り合う掲示板
https://jbbs.shitaraba.net/internet/13109/
TopCoder
https://mevius.5ch.net/test/read.cgi/tech/1333159918/l50
プログラミングのお題スレ Part9 [無断転載禁止]c2ch.net
https://mevius.5ch.net/test/read.cgi/tech/1480579110/
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3c2ch.net
https://mevius.5ch.net/test/read.cgi/tech/1466315249/l50
【会津】パソコン甲子園2004【若松】
https://mevius.5ch.net/test/read.cgi/tech/1094308951/l50
CTFについて語るスレ [無断転載禁止]c2ch.net
https://medaka.5ch.net/test/read.cgi/sec/1476430177/l50

>>1からここまでテンプレ
0009仕様書無しさん垢版2018/08/18(土) 14:15:42.73
１乙！１乙！１乙！１乙！１乙！１乙！１乙！１乙！１乙！１乙！１乙！１乙！１乙！
0010仕様書無しさん垢版2018/08/18(土) 14:42:01.45
書き込みが少ないと落ちるか？？？
0012仕様書無しさん垢版2018/08/18(土) 16:13:07.12
>>1
乙！
0020仕様書無しさん垢版2018/08/18(土) 22:44:19.25
むずすぎ
0023仕様書無しさん垢版2018/08/18(土) 22:47:11.31
セグメントツリーを使う問題だ！と勘違いして
ググりはじめて時間切れ
0025仕様書無しさん垢版2018/08/18(土) 22:49:49.19
セグメントツリーだりーと思ったけどやらなくて通って草
ABCのみでもそれでいいのか
0028仕様書無しさん垢版2018/08/18(土) 22:54:35.35
Dは二次元配列使って解いたけどもセグ木で解く場合は何の情報持たせるんだ?
0029仕様書無しさん垢版2018/08/18(土) 22:54:45.22
いや、ググりながら400点に要求するテクにしては難し過ぎると思ったんだけども。
逆にこれセグ木で解こうとしたら解けるんです？
0035仕様書無しさん垢版2018/08/20(月) 01:18:15.59
うるせえ難読化のつもりはなくても簡潔な実装をする実力がないためにクソコードが生産されるんじゃい
そして今日もクソコードを生産した、TLEでハゲた
精進が足りん
0036仕様書無しさん垢版2018/08/20(月) 02:31:32.47
atcoderで解説してる「りんご」さんの本名教えて
0038仕様書無しさん垢版2018/08/20(月) 19:23:25.16
D問題一向に解けない初学者だが、テンプレの書籍が何かの役に立つだろうか
0039仕様書無しさん垢版2018/08/20(月) 19:34:17.44
教科書で基本を学ばず
いきなり問題集や試験問題を解けるだろうか

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


さて、競プロ本と呼ばれる
蟻本、チーター本、螺旋本、これらは教科書なのか問題集なのか
0040仕様書無しさん垢版2018/08/20(月) 20:22:36.60
そういった本まだ持ってないんだけど前提知識はどこまで求められてるのだろ
0041仕様書無しさん垢版2018/08/20(月) 20:50:07.04
どれも自分で解くことは想定してないから教科書かな
問題集の役割は過去問が担っている
0042仕様書無しさん垢版2018/08/20(月) 20:51:56.79
ひょっとしてABC全完目指すくらいまでは過去問やりこみが一番なんだろうか？
0046仕様書無しさん垢版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)
0047仕様書無しさん垢版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
0049仕様書無しさん垢版2018/08/21(火) 00:22:15.06
蟻本の前半は基本的なテクニックが網羅的に書かれてるから
一度読んでおくと良いと思う
（基本的とは言ってもきちんと使いこなせれば青〜黄色レベルにはなる）
0055仕様書無しさん垢版2018/08/21(火) 17:31:49.49
プログラミング未経験からならCまで
経験者ならDまで
これだろ
0059仕様書無しさん垢版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)
0060仕様書無しさん垢版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
0062仕様書無しさん垢版2018/08/21(火) 22:46:19.73
>>60
> chokudai氏は「むしろ競技プログラミング自体が、人生のさまざまな局面で役に立つ」という。

ホンマか？
0066仕様書無しさん垢版2018/08/21(火) 23:26:09.76
どうなんだろう
こどふぉで一回嘘が想定解だったときは素直に謝罪しつつ誰か正当な解法考えてくれ〜みたいな感じになってその後どうなったか知らない
0067仕様書無しさん垢版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
0070仕様書無しさん垢版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)
0072仕様書無しさん垢版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)
0074仕様書無しさん垢版2018/08/22(水) 06:18:49.91
日本人にも参加しやすい時間帯のコンテストサイトになるか？
0075仕様書無しさん垢版2018/08/22(水) 07:17:50.71
ARC070 のD問題のテストケースって弱い?
AC解答の実行時間でソートすると
8 100
1 1 8 8 8 25 26 50
で落ちそうなのがちらほら見えるのですけども
0076仕様書無しさん垢版2018/08/22(水) 09:06:52.23
【料金泥棒】奪っても捕まらない業界【知財泥棒】

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

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

お前らの金やプログラムを泥棒しても捕まらないからな
0077仕様書無しさん垢版2018/08/22(水) 11:33:44.04
>>75
そのテストケースで落ちそうだってなんでわかるの？
いくつか遅い方のコードでコードテストしても通ったけど。
0078仕様書無しさん垢版2018/08/22(水) 17:45:39.59
ARC070のD
https://beta.atcoder.jp/contests/arc070/tasks/arc070_b

ARC070のDを実行時間でソート
https://beta.atcoder.jp/contests/arc070/submissions?f.Language=&;f.Status=AC&f.Task=arc070_b&f.User=&orderBy=time_consumption

>>75のケースで
答えが 2 になるものと 5 になるものがある(どっちが正しいかは知らん)
2 https://beta.atcoder.jp/contests/arc070/submissions/1169545
5 https://beta.atcoder.jp/contests/arc070/submissions/1170044
5 https://beta.atcoder.jp/contests/arc070/submissions/1170371
5 https://beta.atcoder.jp/contests/arc070/submissions/1170505
5 https://beta.atcoder.jp/contests/arc070/submissions/1174578
2 https://beta.atcoder.jp/contests/arc070/submissions/1258378
2 https://beta.atcoder.jp/contests/arc070/submissions/1441772

https://wandbox.org/permlink/aJJyOZg6M3Qgqcf5
0079仕様書無しさん垢版2018/08/22(水) 17:52:14.55
コードは読んでないけど嘘貪欲が通った感じなのかな？
0080仕様書無しさん垢版2018/08/22(水) 17:56:14.90
落ちるってTLEじゃなくてWAであったか。

じゃあ>>75と同様のケースがテストケースに必要だな。
0081仕様書無しさん垢版2018/08/22(水) 18:07:27.30
自分がＡＣしたコードでは、>>75で２だけど、

２なのか５なのか正解が気になる・・・・
0083仕様書無しさん垢版2018/08/22(水) 18:12:29.41
カードiを含む和がK以上になる部分集合のうち
カードiを取り除くと和がK未満になる部分集合が存在するならカードiは必要
そうでないならカードiは不要
という問題かな？問題文分かりにくいな
0084仕様書無しさん垢版2018/08/22(水) 18:14:49.07
解説ＰＤＦでもＤ問題の冒頭で間違ってるし、
ミスありまくりの問題だったのね。
0088仕様書無しさん垢版2018/08/22(水) 18:53:25.30
ARC070のD
問題点が明らかになっても、AtCoder は修正なしなのか？？？
0091仕様書無しさん垢版2018/08/22(水) 19:23:23.36
トヨタも虜にする｢天才が憧れる天才｣AI企業、PFNゴールデンチームの全貌
https://www.businessinsider.jp/post-173455


強い競プロerがたくさんいる企業だったっけか
0095仕様書無しさん垢版2018/08/22(水) 20:03:16.85
後からやる人用にテスト増やせばいいのに
やらなら除外した方がいいな
0096仕様書無しさん垢版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 を外せるからか？？？
0098仕様書無しさん垢版2018/08/22(水) 21:14:06.01
テストケースをＤＬして見てみると
不必要な数が０であるか全部不要だというテストケースが大半だな。
0099仕様書無しさん垢版2018/08/22(水) 21:24:50.11
全５１個のテストケース中で、
正解の不要数が０と全部のいずれでもないのは１２個だけ。
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況