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

[0001 仕様書無しさん 2019/05/12(日) 06:12:46.93]

プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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/


※前スレ
競技プログラミングにハマるプログラマのスレ 18
https://medaka.5ch.net/test/read.cgi/prog/1548601907/

[0952 仕様書無しさん 2019/07/21(日) 09:07:48.88]

DPに強くなりたいです。何をすればいいでしょうか

基本的なDPは使えます（部分和問題、コイン両替問題、区間DPなど）
しかし、昨日のABC134のF問題のようなDPは解けません
こういった少し特殊なDPが解けるようになりたいです
どこかにこういった問題が集まっていたりしないでしょうか？

[0953 仕様書無しさん 2019/07/21(日) 10:08:27.09]

typical dp contest という典型DPの問題セットが AtCoder にあります。
典型と銘打っているけど、中級者にも勉強になるかと。

[0954 仕様書無しさん 2019/07/21(日) 11:17:16.19]

EDPCの後ろの方やDEGwerさんpdfもいいですよ

[0955 仕様書無しさん 2019/07/21(日) 13:34:47.46]

次スレ

競技プログラミングにハマるプログラマのスレ 20
https://medaka.5ch.net/test/read.cgi/prog/1563667469/

[0956 仕様書無しさん 2019/07/21(日) 13:51:22.40]

ABCに参加しているトップコーダー（オレンジ）のソースを写経する為読んでいるけど。
写経する前に理解するのが大変。
理詰めすぎるプログラムって読むのつかれる。
しかもCが2分とかで解かれているし、頭の中どうなってんだ。

[0957 仕様書無しさん 2019/07/21(日) 13:53:13.90]

>>955
スレ立て乙

[0958 仕様書無しさん 2019/07/21(日) 13:58:18.67]

>>956
ライブラリ化されてる関係のないメソッドが多かったりして読みずらいよな

[0959 仕様書無しさん 2019/07/21(日) 14:33:21.45]

昨日のE1000人通してるけど証明普通に難しくないか？

[0960 仕様書無しさん 2019/07/21(日) 14:52:06.92]

LDS自信持ってかけた人はすごいと思うわ
俺は自信なかったのでセグ木で貪欲に構築していった
C++ならmultisetで同行できたとかなんとか

[0961 仕様書無しさん 2019/07/21(日) 17:30:11.15]

実験して確認する程度で証明までするのは強い人だけだろう

[0962 仕様書無しさん 2019/07/22(月) 00:34:33.33]

Aしか解けなかったわ

[0963 仕様書無しさん 2019/07/22(月) 18:58:18.27]

昨日のbの解説で出てきたダブリングって何？

[0964 仕様書無しさん 2019/07/22(月) 20:14:27.82]

解説の
>> そこでダブリングをします。
からの続きの文章にやることが書いてある
ダブリングの例としては二分累乗なんかもそう

[0965 仕様書無しさん 2019/07/24(水) 23:20:54.43]

夜更かしできる人はCodeforces に出よう

[0966 仕様書無しさん 2019/07/27(土) 12:44:21.45]

8/23のコンテストの会社どんなところか求人見てみたんだけど
・Asprova の100万行以上のC++プログラムを、1〜2カ月で理解できる能力が必要です
これって可能なの？

[0967 仕様書無しさん 2019/07/27(土) 12:49:29.69]

>>966
競技プログラミングしかやってないやつは企業もいらないだろ

[0968 仕様書無しさん 2019/07/27(土) 14:14:51.02]

>>966
ただのブラックでワロタ

[0969 仕様書無しさん 2019/07/27(土) 17:57:41.03]

>>966
1〜2カ月って長いな
これだけでばブラックとは言えない

[0970 仕様書無しさん 2019/07/27(土) 18:49:24.41]

1日2万行以上か
無理だな

[0971 仕様書無しさん 2019/07/27(土) 19:56:04.54]

22日*８時間*2ヶ月が352時間だから１時間で2840行かあ

[0972 仕様書無しさん 2019/07/27(土) 20:11:49.31]

○ワンゴみたいに、リファクタリング認められずに環境故にコード量膨れ上がってるだけかもしれん
今は改善したかもしれんけど

[0973 仕様書無しさん 2019/07/27(土) 20:27:29.85]

この会社やばいから来ないほうがいいっていう採用担当からのメッセージだぞ
厳しい労働環境のバイトがバイトテロおこすみたいなもん

[0974 仕様書無しさん 2019/07/27(土) 20:29:23.44]

リファクタリングされてない100万行のコードとか地獄じゃん…

[0975 仕様書無しさん 2019/07/27(土) 22:43:07.20]

C問題の解答intでおさまらないことがあるのか…
1時間ぐらいそれで悩んでたわ
まだ解けたからいいけど萎える

[0976 仕様書無しさん 2019/07/27(土) 22:47:07.44]

Dは典型DPか

[0977 仕様書無しさん 2019/07/27(土) 22:49:49.32]

DからEFの難易度の差がやべえ

[0978 仕様書無しさん 2019/07/27(土) 22:49:55.73]

文字列アルゴリズムっぽいの出るたびにローリングハッシュでごまかしてるけどいい加減KMPとか理解せんとあかんなこれ

[0979 仕様書無しさん 2019/07/27(土) 22:50:32.34]

D解けなかったー

[0980 仕様書無しさん 2019/07/27(土) 23:15:56.53]

Eなんて絶対解けないと思って見てなかったけど意外と簡単じゃない？
すぐに１次元に帰結できるし

[0981 仕様書無しさん 2019/07/27(土) 23:26:30.55]

E問題、最短経路に関する発想がどうして思いつくのか理解不能

[0982 仕様書無しさん 2019/07/27(土) 23:35:16.10]

>>981
たとえば入力例 3だったらまずはY軸を合わせるために(0,0),(0,4),(0,8),(3,9)にする
そうするとあと残りの距離は9-3で6だから距離4でどうやって行けるか考えればいい
こんな感じに１次元上に落し込めばそんなに難しくないと思う

[0983 仕様書無しさん 2019/07/27(土) 23:44:55.03]

あれEって40人も解けてないのか
もしかして>>982の考え方間違ってる？

[0984 仕様書無しさん 2019/07/28(日) 00:26:49.54]

まともE解いてないけどないけど >>982 みたいな遷移で(5,9) はどうやって構築するん

[0985 仕様書無しさん 2019/07/28(日) 00:50:58.36]

>>984
すまん(3,9)から右に3左に1進めばいいと思ってたんだけど
マンハッタン距離だからダメなんだな
左に１進むのを最初にやって(-1,3)から始まるようにすれば行けるかも…？

[0986 仕様書無しさん 2019/07/28(日) 01:06:38.35]

chokudaiが解くのに1時間半かかってる
Beginner Contestとは一体

[0987 仕様書無しさん 2019/07/28(日) 01:35:13.19]

発想はまだしもこれ時間内に詰め切るのはきついな

[0988 仕様書無しさん 2019/07/28(日) 01:52:29.92]

AGC7位のchokudaiが1時間半てもうレベル設定間違ってるのでは

でもDまでの解説は普段より分かりやすかった
いつもこの人がやって欲しい

[0989 仕様書無しさん 2019/07/28(日) 09:57:33.77]

一方F問題は解説だけで理解できるな(解けなかったけど)

周期性のある列に対しては有向グラフ等でループ構造を作ってあげれば1周期のみで全体を表現できるってことを覚えておこう

あとKMP法は知らなかったのでこれも覚えておこう

[0990 仕様書無しさん 2019/07/28(日) 19:53:47.28]

研究室奥の問題集全然解けなかった…

[0991 仕様書無しさん 2019/07/28(日) 20:54:48.15]

Day2はハードモードだししゃーない

[0992 仕様書無しさん 2019/07/28(日) 21:39:56.57]

この先頑張っても中高生にすら勝てる気がしないな
俺は一体…

[0993 仕様書無しさん 2019/07/28(日) 23:08:37.18]

数学力を磨かんと話にならん

[0994 仕様書無しさん 2019/07/29(月) 02:23:20.23]

FHC 2019 Finalists
https://codeforces.com/blog/entry/68738

日本から2人

[0995 仕様書無しさん 2019/07/29(月) 18:54:20.55]

【乞食速報】ヤマト運輸がプログラミングコンテストを開催【賞金総額95万】 [418042375]
https://leia.5ch.net/test/read.cgi/poverty/1564388438/

[0996 仕様書無しさん 2019/07/29(月) 19:13:50.70]

これとは別でガバガバ二段階認証の件で叩かれててもう色々あかんでしょ

[0997 仕様書無しさん 2019/07/30(火) 06:04:35.16]

乞食速報って板の住人が賞金取れるんかいな？？？

[0998 仕様書無しさん 2019/07/30(火) 17:17:47.23]

ヤマトコン、問題が公開されて業プロとは別物ってことが分かっても「現実問題はこんなに単純じゃない！システム舐めんな！」みたいな怒り方する人出てきそうだなあと嫌儲見て思った

[0999 仕様書無しさん 2019/07/30(火) 17:29:14.77]

ume

[1000 仕様書無しさん 2019/07/30(火) 17:29:34.75]

ume