競技プログラミングにハマるプログラマのスレ 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/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
過去問埋めではなくコンテストに出たい？
2019/04/04(木) 23:51:03.76
今ICPC WFやってるのね
東大すごいじゃん
553仕様書無しさん
垢版 |
2019/04/05(金) 05:32:51.09
東大3位おめでとう！

上位のCFレートやばいな
https://codeforces.com/blog/entry/66365?#comment-503857
2019/04/05(金) 09:56:10.86
>>551
そうですね。
そのくらいのレベルの問題を解きたいというのと全完したいというのがあります
555仕様書無しさん
垢版 |
2019/04/05(金) 16:37:17.27
水色や青色のレベルのコーダーが全完可能な問題セットになることのあるコンテストでABC以外か
2019/04/05(金) 17:21:22.57
codeforces div3 かSRM div2
2019/04/06(土) 00:24:43.58
>>542
年齢制限はオンサイト参加資格の話で、オンラインのラウンドは多分年齢制限ない
つまりごく一部の人を除いて関係ない
2019/04/06(土) 00:29:21.96
じゃあ息子と娘も参加させるわ
2019/04/06(土) 15:13:14.68
qual通過
2019/04/06(土) 18:25:46.30
Tシャツ欲しかったなあ…
2019/04/06(土) 19:07:01.99
今日はAtCoder水色以上の競プロerは20時半からのCodeforcesのratedコンテスト
AtCoder緑色以下の競プロerは21時からのAtCoderのABC
2019/04/06(土) 19:10:30.94
CodeForcesやTopCoderSRMのコンテストは事前登録が必要だから気をつけて
2019/04/06(土) 23:06:54.95
こどふぉは5分前着席とは知らなんだ
2019/04/06(土) 23:10:01.84
こどふぉは間に合うようにスタンバイすれば5分前着席になるから
2019/04/06(土) 23:38:57.55
C++ 入門書のおすすめっていまはどれがいいですか？
C++11とか14とかよくわからんです、
C++のバージョンアップで使える書式がふえたってことでしょうか？
2019/04/06(土) 23:39:54.71
GCJは今からでも参加登録間に合うよ
今回のqualは通貨しやすい
2019/04/06(土) 23:41:08.92
C++本の入門用なら10年ぐらい前の本でも大丈夫でしょうか？
2019/04/07(日) 00:02:45.98
一つも自分で調べてないヴァカにつけるレスなし
2019/04/07(日) 00:30:42.35
>>565
ハゲの本でいい
2019/04/07(日) 00:31:17.12
atcoderしかやらないならatcoderのc++のバージョンに合わせたらいいんじゃね
2019/04/07(日) 05:58:06.02
昨夜のABCのB問題難しすぎわろた…
まだ茶色にもなってないんだけど、他の人のコード見てもわからんわこんなんｗｗｗ
2019/04/07(日) 08:40:43.37
>>571
解説ＰＤＦは分かる？

注文の順番による時間の違いは、最後の料理を何にするかだけって事で
2019/04/07(日) 11:00:42.15
予選終了
2019/04/07(日) 11:19:28.52
interactiveな問題は相手が対話を終了している場合に入力を待ち続けるとTLEになるんだな
当たり前なことに気づかなかった
2019/04/07(日) 12:17:44.74
天下のgoogle様なのにUIがひでえ
2019/04/07(日) 18:30:22.62
qual通過したけど、Round1のA, B, Cはどれかに出ればいいの？それとも全部に出て順番に勝ち上がっていく感じ？
2019/04/07(日) 18:45:43.19
各sub-roundで上位1500人がRound2に進出できて、一度通過したらその後のsub-roundは参加できない。
感覚だけど1A,1Bの通過難易度は同じくらいで1Cはやや緩い
2019/04/07(日) 21:23:30.02
なるほど、ありがとう
2019/04/07(日) 22:31:24.25
>>556
codeforces div3ってeducationalより簡単なのか
今度解いてみよ
2019/04/07(日) 22:56:05.97
SRM div2 hardをコンスタントに解けたら普通に黄色相当だよ

コドフォはいろいろと細かいから分からん
2019/04/08(月) 04:47:17.40
二部探索とか三部探索ってさ、探索領域の左端と右端のどっちを返すべきかたまに分からなくなるんだよな
だからおおよその領域を探索アルゴリズムで決めてからその周辺を総当たりしてる
こんなバカ他にいますか？
2019/04/08(月) 05:18:56.00
たまにやるけど
2019/04/08(月) 11:35:24.24
>>581
整数ならめぐるちゃん式でなんとかならん？
https://twitter.com/meguru_comp/status/697008509376835584
https://twitter.com/5chan_nel (5ch newer account)
2019/04/08(月) 12:06:29.78
>>583
半開区間で持つようにはしてるけど

たとえば
[left, right)
で持つようにしてたら最後に返すべきなのは必ず left だ、ってこと？
2019/04/08(月) 12:28:50.24
>>584
結論としてはそう
このコードの関数solve()は満たすべき条件を表しているので、
solve()がtrueになるときに代入される変数を返せばいいと思えばわかりやすいかな
2019/04/08(月) 18:06:12.85
そうじゃないだろ
めぐる式の利点はleftとかrightで持つんじゃなくてok, ngで持つようにして返す値は最小値最大値に限らずokを返せばいいっていうところだって
2019/04/08(月) 18:12:26.67
あと実数の三分探索は十分な回数のループ回してたらどっち返してもいい、誤差の範囲に収まるから
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況