競技プログラミングにハマるプログラマのスレ 11 [無断転載禁止]©2ch.net
レス数が1000を超えています。これ以上書き込みはできません。
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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にテンプレ続く dは典型だと思ったけれど、意外と苦労した人いたのね >949
DはbitDPつかって
O(N^3 + R^2*2^R)
で解いたわ。
でも、R<=8だと、R!=40320だから、R^2*2^R=16384とあまりかわらないね。N^3の方が大きいし。
階乗で解くほうが実装も楽そうだし、提出時間も考えたら階乗が正解なのかも。 WFは200^3が100万を超えてるけどアリだったのか。 >>954
next_permutation で十分だよね D問題は
ワーシャルフロイドはまだ勉強してないので
ワーシャルフロイドだと気づいた時点で詰んだ >958
WFの存在を知っているなら、理屈はともかく実装はすごく簡単だし、競技中に学んでしまえばよかったのでは。 競技中に知らないアルゴリズム勉強して理解して即初実践とかエリートかよぉ >>960
単なる三重ループなのにそうやって否定から入るからABCすら全完できないのでは >>960
理屈まで学ぼうとすると確かに面倒だが、実装だけまずしておいて理屈は後から勉強すればいい
まずはACが正義 >>962
理屈がわかんないと実装できないような(´・ω・`)
ムズカシイね・・・
ループが3重になると思考停止しちゃうよ・・・ ワーシャルフロイドの実装例見た?
つべこべ言ってやらない典型 >>963
俺だって Ford Fulkerson とか理屈は分かってないけどライブラリとしては持ってるぞ 改行入れたけど、一行でも実装できるよ。
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]) その k != n って動くんだろうけどわざとやってるの? おそらく正当性や計算量解析まで理解してフロー、最小全域木、Union Findなどを使ってる人数は1割もいない
実装は簡単だけど ワーシャルフロイドで距離を調べた後に
Rの全組み合わせを更に調べないといけないのか。(´・ω・`) Binary Indexed Tree なんかも理屈はちょっと理解するのは難しいよな
俺は Segment Tree の空間計算量が少ない版としか理解してない >>966
はぇ〜、(二つのノード間の経路の移動は、途中色んなノードを経由するのに、余計なこと考えずにあらゆる三ノードの関係だけを総当たりさえすれば許されるのか)すっごい
二点間を指定しただけで、具体的にどのように辿るか指定していない、抽象的な距離、
対するは経由点を一つ挿んだ二つの経路の距離の和。これもまた抽象的なまま扱う。
抽象には抽象をぶつける
同じ次元で闘わせれば具体的なことを考えずとも解決してしまう
これなかなか、(心情的な割り切りが) 難しいねんな 次スレ
ttp://medaka.2ch.net/test/read.cgi/prog/1505047495/ >968
c++を学んだ時に使った何かの本かwebサイトで、forループの終了判定は、i < n でなく、i != n を使うのを推奨していて、それに従っている。
勉強に使った資料を辿ると、
C++ Primer か、
おハゲ様のThe C++ Programming Language か、
Effective C++か、
CppCoreGuidelinesか、
なんだけど、
どこに書いてあるか特定出来なかった。
自分の勘違いかもしれない。 ・不一致の判定
・大小の判定
アセンブリ言語の命令的にはどっちが速いの? >>975
一緒やで
結局は引き算して0かどうかで判断するから パフォーマンスが同じならヒューマンリーダブルな方を持ちたいねんな BITはSegTreeに比べて空間計算量が1/2倍になるのに加え、メモリアクセスが少なくなるから時間計算量も定数倍改善する
その代わり演算が結合的で可換でないと使えない >>974
なんで推奨されてるのか謎だけど、typo増えそうでやだなー operetor<が無い可能性もあるテンプレート型のイテレータとかなら分かるが
intは初耳 AtCoderの400から600くらいのレベルの問題を解きたいのですが
AtCoderと似た傾向の問題がある所ないですか?
TopCoderのDiv1は250は直近のはだいたい解いてしまいました yukicoder の星3か星4くらいがAtCoderの400から600くらいに該当すると思う。 そんなに解いたのならTC MedやAC 1000前後の問題に手を出していいんじゃないのか? バン AC
バン (∩`・ω・) バン AC
/ ミつ / ̄ ̄ ̄/
 ̄ ̄\/___/ バン WA WA
バン (#`・ω・) バン WA
/ ミつ / ̄ ̄ ̄/ WA
 ̄ ̄\/___/ WA
WA WA 973 名前:仕様書無しさん[sage] 投稿日:2017/09/10(日) 21:47:04.20
次スレ
ttp://medaka.2ch.net/test/read.cgi/prog/1505047495/ このスレッドは1000を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。
life time: 82日 20時間 6分 21秒 2ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。
───────────────────
《プレミアム会員の主な特典》
★ 2ちゃんねる専用ブラウザからの広告除去
★ 2ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────
会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。
▼ プレミアム会員登録はこちら ▼
https://premium.2ch.net/
▼ 浪人ログインはこちら ▼
https://login.2ch.net/login.php レス数が1000を超えています。これ以上書き込みはできません。