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

■ このスレッドは過去ログ倉庫に格納されています
1仕様書無しさん
垢版 |
2019/01/28(月) 00:11:47.31
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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あたりにテンプレ続く
※前スレ
競技プログラミングにハマるプログラマのスレ 17
https://medaka.5ch.net/test/read.cgi/prog/1540997394/
2019/03/16(土) 18:28:42.01
AGC
順番が３１，３２に直ったね
2019/03/16(土) 22:21:17.47
ＴＬＥかぁ
2019/03/16(土) 23:43:44.03
A,Bは典型
2019/03/16(土) 23:45:57.59
Cはグレイコードではなかった
2019/03/17(日) 00:24:57.33
C解きたかった...
2019/03/17(日) 16:54:55.01
8時間マラソンした後1時間休んで1時間50分AGCとか頭もレートも溶ける
2019/03/17(日) 18:00:28.89
30位まで賞品あるとは太っ腹だな
マラソン形式なら俺でもワンチャン
2019/03/17(日) 18:40:06.38
マラソンはレートつかないからやる気でねー
2019/03/17(日) 20:25:34.20
来週はマラソン、AGC、ABCと連続するね
461仕様書無しさん
垢版 |
2019/03/17(日) 20:53:01.62
今日の21:20からyukicoderでコンテストらしい
全問数え上げ超典型らしい
462仕様書無しさん
垢版 |
2019/03/18(月) 16:21:48.74
http://tco19.topcoder.com/regional-events/tco19-regional-event-japan

SRMに参加する日本人多くてびっくり
2019/03/20(水) 01:41:47.07
div3やdiv2onlyにも強者らが参加して解法ツイートしてくれるから自分的には結構助かっている。ありがとう。
464仕様書無しさん
垢版 |
2019/03/20(水) 05:59:39.09
何でおまえらそんなに賢いの
2019/03/20(水) 09:38:06.78
>>464
さっさとアカウントを作って参加すればいい
2019/03/21(木) 11:38:12.70
twitterなんてすぐ流れるから解説記事が欲しいぞ
2019/03/21(木) 12:31:38.18
kmjpは神
未だに丁寧にdiv2 easy・ mediumも解いてる神
2019/03/21(木) 12:52:26.27
kmjpってどんな人なんだろうな
人生の大半の時間を競プロに費やしてるんじゃないか
2019/03/21(木) 13:00:04.78
それなら競プロの神ですね
2019/03/21(木) 14:50:12.46
https://atcoder-scores.herokuapp.com/?user=kmjp
好感持てるよね 👀
Rock54: Caution(BBR-MD5:b95868ef2c0ed5e765a4d10ada4cf289)
2019/03/22(金) 19:33:12.88
本日yukicoderあります
472仕様書無しさん
垢版 |
2019/03/22(金) 21:11:26.23
ゆきこ出ます
2019/03/22(金) 23:50:08.73
CADDiの８時間マラソン明日
出る人たち頑張ってね
2019/03/22(金) 23:53:04.90
現役プログラマーのオッサンパワーのすごさを若者学生たちに見せ付けてあげて
2019/03/23(土) 07:55:30.04
CADDiコンおいしそう
・海外勢がいない
・マラソン系を避ける人が多い
・土曜日に丸々８時間暇してる人間は少ない
・unratedを避ける人が多い
・アルゴ勢でマラソン強い人は一部だけ
・マラソン勢はTopcoderのMM中でこっちには来ない
・３０位まで賞金

これは勝つる
2019/03/23(土) 08:41:50.45
今日のAGCも難しそう
22時からなので注意

Task Score
A 400
B 700
C 800
D 1000
E 1200
F 1800
2019/03/23(土) 10:19:56.38
Aが400って正気かよ…
2019/03/23(土) 11:41:38.36
優しい400がでると考えましょう
2019/03/23(土) 20:33:18.04
前みたいに700簡単なんだろ
二完余裕だな
2019/03/23(土) 20:45:49.65
３桁スコアは全部取る
2019/03/23(土) 20:59:36.12
今回橙の人がwriterに入ってるけどAGCって橙でも作問できるの？ABCだけじゃなかったっけ？
2019/03/23(土) 21:09:47.05
そんな決まり聞いたことないや
483仕様書無しさん
垢版 |
2019/03/23(土) 21:17:19.89
>>481
作問はAtCoderのレートだけで判断されない
AtCoderあまりやらない人でCodeforcesやTopcoderでレッドコーダー経験者だっている
2019/03/24(日) 00:01:33.98
上位の人たちの各問題を解くのにかかった時間が速過ぎてヤバイな
レッドコーダーまさに化け物って感じだな
2019/03/24(日) 00:16:15.28
私がAGCで3完できるのはいつの日やら
2019/03/24(日) 22:34:29.96
ぎりぎり全完
まにあった
2019/03/24(日) 22:44:22.92
すごいな
Dはさっぱりだ
2019/03/25(月) 01:23:02.98
最近AtCoderでプログラミングの勉強を始めて今回初参戦だったんだけど二問目と三問目が
例題はパスするんだけど提出すると不正解になるテストコードがあって駄目だった
問題部分を特定したいからテストコード見たいんだけどなんでコンテストが終わった後に
公開してくれないんだろう
2019/03/25(月) 02:06:18.86
テストデータを見ずにデバッグ出来る能力を求められているからね…
コンテスト中はテストデータを見ずにACに辿り着く必要があるからその練習だと思えば…

上位のレートの高い人のACしてるコードを読んで自分のコードと比較するなり
もしくは入力データをランダムとかで自分でいくつも作って上位のレートの高い人のACしてるコードの実行結果と比較するなり
2019/03/25(月) 02:24:22.05
ありがとう
ちょっとまだコンテストに参加するには早そうだからしばらくはそういう感じで一問一問
じっくり考えて勉強してく事にする
2019/03/25(月) 09:01:46.17
>>488
テストケースは公開されてるよ
アドレスはスレなりgoogleなりで検索して
2019/03/25(月) 09:02:02.19
>>488
コーナーケースとか境界値で検索
2019/03/25(月) 09:12:42.76
今回のBめちゃ難しい方だからおちんこじゃだめよ
A解けたならちゃんと勉強できてると思うし
後、レートはとにかく参加しないと上がらない
(実力が伸びない的な意味じゃなくてレートの仕様的に)から
まだ早いとか言わずにどんどん参加した方がいいと思う
2019/03/25(月) 09:47:41.90
おちんこじゃだめだよね
2019/03/25(月) 11:37:37.71
まだ早いなんて言って参加しないの典型的無能ムーブだから考え直したほうがいい
2019/03/25(月) 12:17:37.18
無理して出続けてもなとは思うけどな
下がるレートは一番のモチベ下げ要因だし
2019/03/25(月) 12:23:19.37
確かにコンテスト出ても解けないんじゃあ面白くないわな
2019/03/25(月) 13:14:58.13
Ａ問題、Ｂ問題なんて標準入出力と
プログラミング入門レベルの知識でＯＫ

サッと解けるようにならなくちゃダメダメ
2019/03/25(月) 15:00:26.22
488だけど色々レスありがとう
とりあえずBは凡ミスに気づけて後からの提出でAC出来てよかった
Cはテストケースの4以降がTLEって出るからもっと効率のいいソースを
書けってだけでソース的には問題ないっぽい
とりあえずこれから解説動画でC問題の解説見てくる
2019/03/26(火) 19:27:50.79
誰でも頭が良くなる、プログラムが書けるようになる方法が発見される 10547
https://you-can-program.hatenablog.jp
2019/03/26(火) 19:44:27.80
ARCとか何年ぶりだ
2019/03/27(水) 00:03:21.58
診断人さん意外にお若い方だったんですねえ
2019/03/28(木) 04:50:30.66
アルゴリズム説明してるサイトを見つけた(競プロで使える？)


https://inzkyk.github.io/algorithms
このページは Jeff Erickson 著 Algorithms の翻訳です。英語版は CC BY 4.0 です。 © Jeff Erickson 2018
2019/03/30(土) 12:53:59.62
topcoderのマラソンマッチって、クソ面白いのに参加者少ないのは、入れ込んじゃって時間使い過ぎるのが怖いから？
2019/03/30(土) 14:44:21.57
マラソンって何で入門すればいいのかわからないです。教えてください
競プロは蟻本とかあるじゃないですか
2019/03/30(土) 16:46:28.19
>>505
空手で黄色なれるよ
2019/03/30(土) 16:46:43.36
蟻本ないからこれを参考にしてマラソンマッチ始めた
http://threeprogramming.lolipop.jp/blog/?p=1164
508仕様書無しさん
垢版 |
2019/03/30(土) 16:56:35.47
amazonで『最適化』で検索して出てくる本じゃダメなの？
教えてマラソンer!!
2019/03/30(土) 18:30:01.51
>>508
それが必要になるのは一位を取り合ってる人たちだけだよ
2019/03/30(土) 20:02:53.69
逆に言えば１位を取りたいなら読めってことだな
2019/03/30(土) 21:54:27.55
>>510
言い方を変えると、同じ解法でできるだけ順位上げたいなら要る
2019/03/30(土) 22:31:58.36
貪欲と山登りと焼きなましでどうにかなるよ
2019/03/30(土) 22:57:59.32
>>512
嘘つくな
生半可な覚悟だと近傍が上手くとれなくて上位半分にも入れない
2019/03/30(土) 23:04:16.89
雑魚なので無限に椅子を温めた
今月椅子を温めただけだった
2019/03/30(土) 23:07:32.74
AB早解きで青パフォウマウマだな
2019/03/30(土) 23:31:32.80
699位までのAB２日が青パフォか
AB提出まで3分
タイピングマスターか
2019/03/30(土) 23:58:54.05
CDEのどれか解ければ胸張って青パフォと言えるぞ
2019/03/30(土) 23:59:15.42
ルールがよく分からないんだけど提出する予定のコードをテストするのってアリなのかな？
2019/03/31(日) 00:01:32.92
ありだよ
2019/03/31(日) 00:14:58.61
ありがとう
俺はまだ一分一秒でも早く提出したいって感じでもないからチェックしよっと
2019/03/31(日) 00:44:36.69
今日から始めた初心者は二完が2500人も並んだ順位表を見て何を思うのだろうな
2019/03/31(日) 01:01:07.79
普通のARC開いて欲しい
2019/03/31(日) 01:01:17.10
もともとやってた人なら人増えたなって思うけど、初めてならほーんって感じなのでは
2019/03/31(日) 01:21:32.17
レートは一応上がったけどつまらなかった
今回クソゲーだろ
2019/03/31(日) 04:45:18.04
500を解けるようになればクソゲーではなくなる
2019/03/31(日) 06:49:33.92
Ｃ問題、Ｄ問題もそれほど困難ではないでしょ
2019/03/31(日) 07:39:18.79
迷路の解き方の数をスタックを使った深さ優先探索で数えたいとする

このとき、スタックに頂点だけじゃなくて現在に至るまでに辿った道順も積む方法しか思いつかないんだが、頂点だけ積むようなやり方はありますか？
2019/03/31(日) 09:19:16.10
よく分からんがそもそも迷路って解が一意じゃないとダメなのでは
2019/03/31(日) 11:21:37.42
閉路があったら爆発しそう
2019/03/31(日) 11:22:27.88
迷路を解くって最短経路？オイラー路？
2019/03/31(日) 11:24:36.52
s/オイラー/ハミルトン
532527
垢版 |
2019/03/31(日) 14:02:08.24
普通にスタートとゴールがあるグラフで、スタートからゴールに至る道のりを列挙する状況を想定してます

しかし、この反応を見ると、その目的で深さ優先探索を使うのは一般的じゃないようですね
2019/03/31(日) 15:07:31.12
各頂点を訪れたかどうかをbool変数に持っておけばいいんじゃないの？
2019/03/31(日) 15:58:37.32
重みなしグラフの最短距離のパスの数え上げならABC021C　正直者の高橋くん
に解説あるよ
最短路のDAGを幅優先探索とかで作ってから動的計画法で数え上げ（またはメモ化再帰）

同じ頂点を通らないパス（遠回りしてもいい）の数え上げ（数え上げおねえさん問題）は
Knuth大先生の simpath アルゴリズムとういのがあるらしい（自分では理解できてないです）
2019/04/01(月) 01:13:03.47
初めてコンテストに参加したけどAB解いただけなのにいきなり茶色になってワロタ
ABCのCですら解けるか怪しいのに怖いわ
2019/04/01(月) 14:18:40.21
今回のC問題は水色上位以上レベルあるしまあ
2019/04/01(月) 18:44:08.94
水色上位どころか青中位はあるよ
2019/04/01(月) 19:49:59.87
ARCの二問目は基本的に青レベル
水色レベルが出るのはABC-Dだけ
2019/04/01(月) 19:58:43.71
そんなことないけど…
2019/04/01(月) 20:43:48.45
AB超早解きで青パフォなんだから
今回のCは青中堅だな
2019/04/01(月) 21:02:02.47
んなこと言ったらtopcoder SRM div1 easy は5割ほどしか通せてないからね？(笑)
542仕様書無しさん
垢版 |
2019/04/03(水) 20:59:01.04
Google Code Jam の Qualification Round 2019 があるよ

4月6日の午前8時から提出期限が27時間
決められた点数分を稼げば次のラウンドへ進めるよ

AtCoderのABCのCやDをたまに解けるくらいの実力なら記念参加するのもありだよ

年齢制限は18歳以上
Tシャツを狙いに行くならAtCoderの青色以上の実力は最低限いるかもね
これの次のラウンドからはよくある競プロのコンテスト形式で2時間半で開催時間に人権がないけれども

https://codingcompetitions.withgoogle.com/codejam/schedule
2019/04/03(水) 21:10:42.72
>>542
マラソン系じゃないんでしょ？
2019/04/03(水) 23:42:40.40
過去問を見ればわかるけど競プロ問題だよ
出力フォーマットがやや特殊なだけで
入力もAtCoderではあまりないスタイルかもしれない
2019/04/03(水) 23:49:50.64
各問題に入力の小さい部分点(small)があるから
それだけを解ける解法で部分点を確実に取りに行く戦略があったりする
GoogleCodeJamのほかにFacebookHackerCupやCodeChef-LongChallengeなどでも
2019/04/04(木) 19:15:22.43
>>チーター、蟻、螺旋本を買う。
螺旋本と蟻本は買ったんだけど
チーター本って買う必要ある？
2019/04/04(木) 19:18:33.98
例年のQualification Roundの個人的な体感・感想だけど
3〜4問出題されて簡単めが2問、難しめが1〜2問
それぞれテストケースがsmallとlargeの2種類用意されていて
簡単めを2問ともsmallとlargeをACする、もしくは全問のsmallをACする、のいずれかでラウンド通過

ABC/ARCの配点イメージで
簡単めのsmallが300〜400、largeが400〜700
難しめのsmallが400〜600、largeが500〜1000前後

paizaの時間制限がかわいいくらいに思える24時間以上あるから
ABCをコンテスト時間以上かければ自力全完できる緑や茶の人でもワンチャンあるんじゃないの？
2019/04/04(木) 19:21:29.87
螺旋本と蟻本を持っているなら
chokudaiにお布施したいならチーター本買えばいいと思うよ
2019/04/04(木) 19:41:41.78
螺旋本読むよりは蟻本読みながらAOJのコース埋めるのが良いと思うけどね

講義には螺旋本は使えると思う
2019/04/04(木) 22:38:37.48
abcと同じかちょっと難しめくらいのレベルのコンテストってあります？
こどふぉのdiv3とかってこれくらいなんでしょうか
2019/04/04(木) 23:41:10.52
過去問埋めではなくコンテストに出たい？
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。