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

■ このスレッドは過去ログ倉庫に格納されています
2020/02/08(土) 11:04:05.90
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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/proj
※前スレ
競技プログラミングにハマるプログラマのスレ 22
https://medaka.5ch.net/test/read.cgi/prog/1575287454/
2020/03/21(土) 23:45:32.80
>>796
ありがとう！
2020/03/21(土) 23:49:21.82
A - Range Flip Find Routeって、
bfsやdfsでは解けないんでしょうか
2020/03/22(日) 00:04:16.38
距離0→距離1→とやっていけばできそうだけど
ダイクストラ法(0-1BFS)を使うのと変わらないかも
2020/03/22(日) 00:10:24.16
やっぱAGCはたのしいな
802799
垢版 |
2020/03/22(日) 00:11:12.98
>>800
ありがとう
2020/03/22(日) 00:31:31.69
問題は面白いんだけど勝てねえ
勝てるという意味ではARCやこどふぉの方が楽しい
2020/03/22(日) 09:20:49.60
>>794
そうなんですね…もう少し解説ブログとかを調べて読み込んでみます

>>797
前者でした。木問題に限らず埋めていった方がいいという事ですね、やってみます

どうもありがとうございました
2020/03/22(日) 13:01:57.85
>>792って全方位木DPか木の直径の性質を使う奴かだからちょっと難しい気はする
DFS一発で解けるような問題からやったほうがいいかなあとか思った
2020/03/22(日) 18:41:35.11
>>805
普通に全頂点間の距離を求めるだけでは
2020/03/22(日) 18:45:06.31
>>806
グラフのn=10000でΘ(n^2)は厳しそう
2020/03/22(日) 18:53:57.54
10^4で2乗オーダーこわい
2020/03/22(日) 18:55:08.16
>>807
10^8ならいけると思ったけどよく考えたらlognもつくか
2020/03/22(日) 19:03:11.81
>>809
logどこ
2020/03/22(日) 19:12:05.68
>>810
LCA求めるとこ
2020/03/22(日) 19:33:56.68
どこでlcaつかうねん
2020/03/22(日) 19:34:17.51
やるにしても全頂点からDFS/BFSするだけでしょ
LCAがO(1)という話もあるけど
2020/03/22(日) 19:57:56.84
>>811
LCAで任意の二点間距離がlognで求まる的な？
2020/03/22(日) 20:23:24.69
直径求めたら直径の2点とのどっちからからの距離が任意頂点の高さでしょ
2020/03/22(日) 21:21:08.02
>>814
それ
この問題なら必要なかった
817792
垢版 |
2020/03/22(日) 22:36:05.53
>>805
もし「DFS一発で解けるような問題」ご存じでしたら教えてほしいです
ALDSも一工夫必要な問題が多くて、解説読んでるんですが中々理解が進まないので…
2020/03/22(日) 22:38:08.43
見落としてる例外がどこかわからない
こういうのができないから昔から数学が苦手なんだよなぁ
2020/03/22(日) 22:42:44.39
外部からの攻撃で草
2020/03/22(日) 22:50:12.83
ここの住人の仕業か？
2020/03/22(日) 22:56:33.96
攻撃する利点はなんぞ
2020/03/22(日) 23:05:34.67
愉快犯か？
2020/03/22(日) 23:12:03.84
こういう時に損害賠償って言うんじゃないですかね
2020/03/22(日) 23:18:45.94
攻撃者はレッドコーダーと戦いたいのでは？
2020/03/22(日) 23:34:41.13
ABC生やしてる暇あるんだったらAGC生やせよ！というメッセージということか
2020/03/23(月) 01:21:35.12
>>817
迷路でスタートからゴールまで辿り着けるかどうか判定とかDFSのみだね。
2020/03/23(月) 01:28:06.33
nosub戦略でWA出したんやろ
2020/03/23(月) 02:27:47.33
>>817
ほんとにDFSやるだけのやつ
https://atcoder.jp/contests/atc001/tasks/dfs_a

BFSもあるよ
https://atcoder.jp/contests/abc007/tasks/abc007_3

応用
https://atcoder.jp/contests/arc031/tasks/arc031_2
https://atcoder.jp/contests/abc151/tasks/abc151_d
2020/03/23(月) 04:48:19.74
>>792
DFSだけで解いた
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4285896#1
2020/03/23(月) 07:21:17.38
こういうライブラリ化の仕方初めて見たかも
2020/03/23(月) 08:20:59.41
パソコン甲子園、いつになったら解説を公開するんですかね
AtCoderなんて毎週開催でちゃんと解説公開してるよ?
2020/03/23(月) 08:38:26.04
パソコン甲子園に言えや
ここは5chやぞ
2020/03/23(月) 13:13:13.16
ここでパソコン甲子園の文句言うのは俺は別に構わないと思うけど, 同じこと投稿しすぎで鬱陶しい
2020/03/23(月) 15:38:56.62
https://twitter.com/pc_koshien

パソコン甲子園の公式ツイッターで
ツイートで解説してるやんけ

このツイッターアカウントのプロフィールに連絡先のメールアドレスも記載されてんだから
そこにメールでもしろ
https://twitter.com/5chan_nel (5ch newer account)
2020/03/23(月) 15:50:34.45
>>834
PDF以外の形式は公開とは定義されないんだろう競プロerの中では
社長に良識あると褒められるほどの競プロerともあろう存在がスレで文句撒き散らすからには運営には何度も連絡してて音沙汰がないってことだろう
そういうことだ
2020/03/23(月) 16:11:38.92
https://twitter.com/chokudai/status/1032505124688605185
> 競技プログラミング勢、5chですら良識を持って行動している
https://twitter.com/5chan_nel (5ch newer account)
2020/03/23(月) 17:35:29.63
競プロ界隈で使われてると聞く翻訳サイト
Google翻訳、みらい翻訳、DeepL翻訳

使われて無さそうな翻訳
Bing翻訳、Yandex翻訳、Weblio翻訳、エキサイト翻訳、Papago翻訳、Baidu翻訳
2020/03/23(月) 17:52:07.88
>>829
嘘解法だね
2020/03/23(月) 18:12:29.39
Java読めないけど正しいように見える
2020/03/23(月) 18:18:55.07
この行のところでstartが更新されないパターンあるんじゃない？嘘解法でしょ
if (dist[j] > dist[start]) start = j;
2020/03/23(月) 18:21:56.47
最初の反復でN=1なら更新入らないがこれは自明に正しい
N>1なら絶対更新入る
2回目の反復で更新しない場合はあるがこれはstartが直径になりうる頂点だったときのみで別に正しい
3回目は意味無し

なんか違うか？
2020/03/23(月) 18:26:20.23
>>841
正しかったのか
勘違いして嘘解法って言ってゴメンね
2020/03/23(月) 18:28:59.86
ちゃんと謝ってて偉い
2020/03/23(月) 20:03:25.21
えらい
2020/03/23(月) 21:45:10.39
コンテストありがとう
問題ありがとう
解説ありがとう
支えてくれた皆ありがとう
2020/03/23(月) 21:54:11.81
さよなら
2020/03/23(月) 22:29:21.76
さよなら
2020/03/23(月) 22:32:28.13
オンラインジャッジというコンピュータリソースまで無料で使わせて頂き競技プログラミングの世界には感謝の言葉が尽きません
2020/03/23(月) 22:44:36.69
本当に良識を持って行動してて草
2020/03/23(月) 22:48:28.04
5chて
Twitterのリンク貼ると5chの公式Twitterのリンク挿入されるし
はてなブログなどの一部のサイトのリンク貼ると5chのNG規制で書き込めない＆ブラックリスト扱いでしばらく何も書き込めなくなる

真面目な話しようとすると制限が厳しいし

早く日本勢向けの競プロのSNSやフォーラムなどのコミュニティの場が発足してほしい
2020/03/23(月) 23:07:40.81
https://twitter.com/*/status/989064618084634625
てす
2020/03/24(火) 19:06:31.08
touristも高齢者の仲間入りしたからマラソンマッチに本格参入したのかな

競プロにおいてIOIやICPCが若者だから
2020/03/24(火) 19:45:40.55
touristって最強扱いされて何年目くらいになるの
2020/03/24(火) 20:21:44.06
touristの記事の中で東大の名前がある

https://en.wikipedia.org/wiki/Gennady_Korotkevich
2020/03/25(水) 13:47:48.22
オケ村とかいうの寒すぎる
2020/03/25(水) 14:03:11.25
極々一部の身内でしか使ってない言葉取り上げてどうすんの
2020/03/25(水) 14:10:09.60
オケ村とかいうの村寒すぎる明
2020/03/25(水) 14:30:09.61
極々一部じゃないんだよな
2020/03/25(水) 15:32:09.03
使ってる人数数えてみなよ
2020/03/25(水) 15:53:13.53
内輪ネタが外から見たら寒いのは仕方ない
861仕様書無しさん
垢版 |
2020/03/25(水) 16:05:19.71
Twitterで稚拙な呟きしてる競プロer嫌い
大人ならちゃんとした口調で喋った方が良いよ
特に中高生とかもろに影響受けて、ミーム使うことに陶酔してそうで可哀想
ただでさえ現実との繋がりが強い界隈なんだからSNSの使い方くらいは分別つけた方がいいんじゃないかな
2020/03/25(水) 16:34:36.86
>>861
稚　拙　に　き　あ　ち　ゃ　ん　？　笑
2020/03/25(水) 16:44:14.53
ここでご高説を披露しても実際にミーム使ってる連中の目には留まらないけどな
愚痴ならここですればいいけど、こうすべきってのをここで言っても無駄無駄
2020/03/25(水) 16:44:30.43
稚拙村稚拙明
865仕様書無しさん
垢版 |
2020/03/25(水) 16:48:16.88
確かに稚拙とか可哀想とか一言余計だったな
まず自分を省みるべきだった
上から目線でキツい言い方してごめん
2020/03/25(水) 16:53:09.30
ちゃんと謝ってて偉い
2020/03/25(水) 18:25:23.42
るるるるるる〜
2020/03/25(水) 21:19:35.08
AtCoderオンライン勉強会 第一回 「PASTエントリー取得講座」って何?
どこにも情報がない
2020/03/25(水) 21:52:17.37
>>868
「あーだこーだー」っていう名前の火曜隔週の生放送の前回(第二回)か前々回(初回)に言ってた
2020/03/25(水) 21:59:58.49
メンテが入るってことはいよいよ言語アップデートか
2020/03/26(木) 00:39:48.30
rubyがどうこうってのはもう直ったんか？
2020/03/27(金) 15:38:56.38
？？？「不眠不休の競プロは自粛を」
2020/03/27(金) 17:31:47.98
お前らが単に競プロって言うときどの範囲を言ってる？

GCJ決勝やAGCのような頂上決定戦的なコンテストだけ？
div2やABCを含めたコンテストまで？
コンテスト以外、つまり過去問埋めやバチャまで全部を言う？

お前らが単に競プロerと言うときどの範囲を言ってる？

レッドコーダーのみ？
入賞争いに加われる暖色系まで？
入賞には縁がない下位暖色系まで？
DP問とか触りだす水色や青色まで？
灰色も含めコンテストに参加してる全員？
コンテスト未経験の過去問埋めやバチャしてるだけも含めてる？
2020/03/27(金) 17:33:05.32
>>873
赤や橙の人が競プロについて言及してるときどの範囲を言ってるのかよく分からなくなる
2020/03/27(金) 17:50:49.37
SRMでdiv1難易度のdiv混合戦を頻発させてdiv1を大掃除して欲しいわ
2020/03/27(金) 17:58:51.72
両方一番下
2020/03/27(金) 18:20:34.41
便宜上div2までを競プロ、div2上層を競プロerち呼んでる
心の中ではdiv1以上を競プロ、div1参加資格あるレベルを競プロerと思ってるわ
※divはcodeforces基準
2020/03/27(金) 19:45:54.40
O色未満は競プロerじゃないみたいな思想は過激だし誰も幸せにならないと思うが
こういうこと言い出す奴のせいでコミュニティが息苦しくなると思うんだけど
2020/03/27(金) 19:54:37.10
無駄に文章が長い人や過激な人はスルーしましょう
880仕様書無しさん
垢版 |
2020/03/27(金) 20:01:20.57
コンテストに出てないのは競技者とは言えないのでは？とは思ってしまうなあ
2020/03/27(金) 20:04:31.30
ほんそれ
2020/03/27(金) 20:09:35.97
"競技"には参加してるけど"競技"には参加してないのを"ゆるふわ勢"って言ってる印象ある
2020/03/27(金) 20:15:13.39
何言ってんの？
2020/03/27(金) 20:15:34.26
狭義の競技と広義の競技の差は大きそう
2020/03/27(金) 20:26:23.89
Atcoderでも何でも提出したことあれば競プロやってるとは言えるだろバカか
2020/03/27(金) 20:34:32.76
わたし灰色コーダーですけど競技プログラマー名乗っていいですか
2020/03/27(金) 20:48:21.82
名乗って良いに決まってるだろ
2020/03/27(金) 20:51:21.73
黒色未満は競プロerじゃない
2020/03/27(金) 21:06:49.29
人が勝手に思っているだけの定義に対してイライラしている人は “狭義” や “広義” でググって落ち着いて
2020/03/27(金) 21:17:09.63
勝手に思ってるだけならいいですよ、本当に思ってるだけならね
言葉にしてしまえばそれはもう思ってるだけとは言えない
2020/03/27(金) 21:36:58.72
>>890
すまん俺が悪かったからもうぐちぐち言うのはやめてくれまいか
2020/03/27(金) 22:50:46.52
>>890
まぁ「〇〇色はカス！」→「煽りじゃなくて自分の事だけど」のコンボは正直ウザい
2020/03/27(金) 23:04:05.49
優秀なプログラマーって結構な確率で優越コンプレックスを患ってるよな
実は凄いんだけどその凄さが万人に伝わらずむしろコミュ下手で全然尊敬されないからますます拗らせちゃう
2020/03/27(金) 23:05:38.29
まったくだ
2020/03/27(金) 23:57:53.31
病気と思うぐらい自己肯定感が低い人を見てアレ
2020/03/28(土) 00:06:31.75
どれだよ
2020/03/28(土) 01:41:48.37
* https://twitter.com/syakejs/status/1243568434421600257
* https://archive.is/ijaIb (魚拓)

これすごいな、いい年した大人が他人の鍵垢のツイートを晒して気持ち悪いと言い放つって...
こんな過激なことお前らでもやらないだろ
https://twitter.com/5chan_nel (5ch newer account)
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況