X



競技プログラミングにハマるプログラマのスレ 11 [無断転載禁止]©2ch.net
レス数が1000を超えています。これ以上書き込みはできません。
0001仕様書無しさん2017/06/22(木) 22:18:06.15
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)やCTFなどを楽しんでる競技プログラマ(競プロer)の雑談スレ
競プロイベントや競プロ問題や有名競プロerや競プロでよく使うアルゴリズム等について語りあったり、競プロ関連の質問相談なんでもおk
競プロ初心者でググっても解説読んでも分からないことがあったらスレの競プロの先輩方に訊いてみるのも手だよ(分かりやすい解説サイトとか書籍とか教えてくれるかもしれないよ)
次スレは>>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にテンプレ続く
0952仕様書無しさん2017/09/09(土) 23:39:12.35
解説聞いてもよくわかんないな。(´・ω・`)
0953仕様書無しさん2017/09/09(土) 23:39:15.84
dは典型だと思ったけれど、意外と苦労した人いたのね
0954仕様書無しさん2017/09/09(土) 23:45:46.87
>949
DはbitDPつかって
O(N^3 + R^2*2^R)
で解いたわ。
でも、R<=8だと、R!=40320だから、R^2*2^R=16384とあまりかわらないね。N^3の方が大きいし。
階乗で解くほうが実装も楽そうだし、提出時間も考えたら階乗が正解なのかも。
0955仕様書無しさん2017/09/09(土) 23:47:56.65
WFは200^3が100万を超えてるけどアリだったのか。
0956仕様書無しさん2017/09/09(土) 23:50:12.91
C,Dの差が100かあ
0958仕様書無しさん2017/09/10(日) 05:39:01.00
D問題は
ワーシャルフロイドはまだ勉強してないので
ワーシャルフロイドだと気づいた時点で詰んだ
0959仕様書無しさん2017/09/10(日) 10:25:22.77
>958
WFの存在を知っているなら、理屈はともかく実装はすごく簡単だし、競技中に学んでしまえばよかったのでは。
0960仕様書無しさん2017/09/10(日) 10:33:58.22
競技中に知らないアルゴリズム勉強して理解して即初実践とかエリートかよぉ
0961仕様書無しさん2017/09/10(日) 10:55:28.46
>>960
単なる三重ループなのにそうやって否定から入るからABCすら全完できないのでは
0962仕様書無しさん2017/09/10(日) 11:27:55.24
>>960
理屈まで学ぼうとすると確かに面倒だが、実装だけまずしておいて理屈は後から勉強すればいい
まずはACが正義
0963仕様書無しさん2017/09/10(日) 16:30:06.79
>>962
理屈がわかんないと実装できないような(´・ω・`)
ムズカシイね・・・
ループが3重になると思考停止しちゃうよ・・・
0964仕様書無しさん2017/09/10(日) 16:43:55.89
ワーシャルフロイドの実装例見た?
つべこべ言ってやらない典型
0965仕様書無しさん2017/09/10(日) 16:59:32.19
>>963
俺だって Ford Fulkerson とか理屈は分かってないけどライブラリとしては持ってるぞ
0966仕様書無しさん2017/09/10(日) 17:29:45.46
改行入れたけど、一行でも実装できるよ。
for (int k=0; k!=n;++k)
for (int i=0; i!=n; ++i)
for (int j=0; j!=n; ++j)
dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j])
0967仕様書無しさん2017/09/10(日) 17:38:28.69
まあ適切に初期化する必要があるけど
0968仕様書無しさん2017/09/10(日) 18:52:53.72
その k != n って動くんだろうけどわざとやってるの?
0969仕様書無しさん2017/09/10(日) 19:17:37.31
おそらく正当性や計算量解析まで理解してフロー、最小全域木、Union Findなどを使ってる人数は1割もいない
実装は簡単だけど
0970仕様書無しさん2017/09/10(日) 21:29:31.47
ワーシャルフロイドで距離を調べた後に
Rの全組み合わせを更に調べないといけないのか。(´・ω・`)
0971仕様書無しさん2017/09/10(日) 21:41:55.44
Binary Indexed Tree なんかも理屈はちょっと理解するのは難しいよな
俺は Segment Tree の空間計算量が少ない版としか理解してない
0972仕様書無しさん2017/09/10(日) 21:44:27.76
>>966
はぇ〜、(二つのノード間の経路の移動は、途中色んなノードを経由するのに、余計なこと考えずにあらゆる三ノードの関係だけを総当たりさえすれば許されるのか)すっごい

二点間を指定しただけで、具体的にどのように辿るか指定していない、抽象的な距離、
対するは経由点を一つ挿んだ二つの経路の距離の和。これもまた抽象的なまま扱う。
抽象には抽象をぶつける
同じ次元で闘わせれば具体的なことを考えずとも解決してしまう
これなかなか、(心情的な割り切りが)&#160;難しいねんな
0973仕様書無しさん2017/09/10(日) 21:47:04.20
次スレ
ttp://medaka.2ch.net/test/read.cgi/prog/1505047495/
0974仕様書無しさん2017/09/10(日) 22:24:47.99
>968
c++を学んだ時に使った何かの本かwebサイトで、forループの終了判定は、i < n でなく、i != n を使うのを推奨していて、それに従っている。
勉強に使った資料を辿ると、
C++ Primer か、
おハゲ様のThe C++ Programming Language か、
Effective C++か、
CppCoreGuidelinesか、
なんだけど、
どこに書いてあるか特定出来なかった。
自分の勘違いかもしれない。
0975仕様書無しさん2017/09/10(日) 22:59:58.87
・不一致の判定
・大小の判定
アセンブリ言語の命令的にはどっちが速いの?
0976仕様書無しさん2017/09/10(日) 23:42:40.36
>>975
一緒やで
結局は引き算して0かどうかで判断するから
0978仕様書無しさん2017/09/11(月) 00:45:56.21
パフォーマンスが同じならヒューマンリーダブルな方を持ちたいねんな
0980仕様書無しさん2017/09/11(月) 01:51:16.00
BITはSegTreeに比べて空間計算量が1/2倍になるのに加え、メモリアクセスが少なくなるから時間計算量も定数倍改善する
その代わり演算が結合的で可換でないと使えない
0981仕様書無しさん2017/09/11(月) 18:33:11.30
>>974
なんで推奨されてるのか謎だけど、typo増えそうでやだなー
0982仕様書無しさん2017/09/11(月) 21:42:56.71
operetor<が無い可能性もあるテンプレート型のイテレータとかなら分かるが
intは初耳
0988仕様書無しさん2017/09/12(火) 21:52:12.91
AtCoderの400から600くらいのレベルの問題を解きたいのですが
AtCoderと似た傾向の問題がある所ないですか?
TopCoderのDiv1は250は直近のはだいたい解いてしまいました
0989仕様書無しさん2017/09/12(火) 22:19:43.39
yukicoder の星3か星4くらいがAtCoderの400から600くらいに該当すると思う。
0990仕様書無しさん2017/09/13(水) 03:26:56.39
そんなに解いたのならTC MedやAC 1000前後の問題に手を出していいんじゃないのか?
0991仕様書無しさん2017/09/13(水) 12:44:13.06
俺もそれぐらいバンバン解けるようになりてーわ
0992仕様書無しさん2017/09/13(水) 14:44:50.81
  バン   AC
バン (∩`・ω・) バン AC
  / ミつ / ̄ ̄ ̄/
  ̄ ̄\/___/
0994仕様書無しさん2017/09/13(水) 17:18:37.18
  バン WA WA
バン (#`・ω・) バン WA
  / ミつ / ̄ ̄ ̄/ WA
  ̄ ̄\/___/ WA
  WA  WA
1000仕様書無しさん2017/09/13(水) 18:24:27.46
973 名前:仕様書無しさん[sage] 投稿日:2017/09/10(日) 21:47:04.20
次スレ
ttp://medaka.2ch.net/test/read.cgi/prog/1505047495/
10011001Over 1000Thread
このスレッドは1000を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。
life time: 82日 20時間 6分 21秒
10021002Over 1000Thread
2ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。


───────────────────
《プレミアム会員の主な特典》
★ 2ちゃんねる専用ブラウザからの広告除去
★ 2ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────

会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。

▼ プレミアム会員登録はこちら ▼
https://premium.2ch.net/

▼ 浪人ログインはこちら ▼
https://login.2ch.net/login.php
レス数が1000を超えています。これ以上書き込みはできません。

ニューススポーツなんでも実況