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

■ このスレッドは過去ログ倉庫に格納されています
1仕様書無しさん
垢版 |
2020/05/09(土) 00:48:33.62
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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
※前スレ
競技プログラミングにハマるプログラマのスレ 24
https://medaka.5ch.net/test/read.cgi/prog/1585409967/
2020/05/15(金) 21:00:44.88
こどふぉの初期ratingは1500定期
234仕様書無しさん
垢版 |
2020/05/15(金) 21:35:13.69
コドフォ一回だけ出て履歴書に青ですって書くの良さそう
2020/05/15(金) 21:57:02.64
こどふぉの初期レート下げるらしいぞ
https://codeforces.com/blog/entry/77130#comment-618402
2020/05/16(土) 00:25:26.80
>>235
ワンチャン900まで初期レート下げるのか
まだ登録してない人は今のうちに初期レート1500貰っとくのが得っぽいな
2020/05/16(土) 03:32:11.19
5/23 AGC044
5/30 NOMURAコン
6/7 AGC045 ←New!!
6/20 AGC046 ←New!!

ここにきて怒涛のAGC連打は草
これで延期になった042と合わせて目標の年6回に対して5回を既に消化することになるのか
2020/05/16(土) 05:14:16.14
起きたらAGC生えてて草
予定通りAGC6回ならペース悪すぎるなあ
俺はABCratedだから関係ないけど
239仕様書無しさん
垢版 |
2020/05/16(土) 10:11:15.80
ARCはもう開催されないのか
2020/05/16(土) 10:19:25.83
ARCは企業コンと統合するとか言ってなかったっけ
2020/05/16(土) 10:38:10.15
累積和で解ける問題をセグ木で解いたり、
オイラーツアーで解ける問題をHL分解で解いたりと、
オーバースペック気味に解いてしまいます
これは、問題をたくさん解くことで徐々に改善されていくものでしょうか？
2020/05/16(土) 10:47:59.35
パソコン甲子園、何故解説を公開しない?
作る時間はいくらでもあるよね?
参加者のことを何だと思ってるんだろうね
2020/05/16(土) 12:00:06.44
>>241
どのデータ構造を使うかの慣れの問題なので，たくさんといてれば思いつくようになる
解けるなら別になんでもいいと思うけどな
244仕様書無しさん
垢版 |
2020/05/16(土) 12:11:45.14
>たくさんといてれば思いつくようになる
ってのは認知バイアスじゃねえか？

たくさんやって最適なものを思い付くようになった上位者は必ずそう言う
が、たくさんやったが思い付くようにはならなかった……みたいなヤツもいる
2020/05/16(土) 13:00:42.83
こんなアドバイスは自分の経験で言うしかないでしょ・・・
データなんかないんだから
2020/05/16(土) 13:21:05.27
解けるならいいんじゃないの(適当)
2020/05/16(土) 13:50:20.74
コンテスト中はACさえとれりゃok
殴ったと思ったらちゃんと復習すればよし
2020/05/16(土) 15:48:22.92
オーバースペックで解くのは定数倍以外は何も問題がないし、定数倍のいいライブラリを整備していればそこで詰まることは滅多にない
2020/05/16(土) 16:40:20.71
まあ累積和→セグ木はオーダーレベルで悪くなってるから実害がなくはなさそう
log2つ乗っけてTLEは普通にありうるからなあ
2020/05/16(土) 22:39:18.88
Code Jam Round2ってAtCoder黄色ぐらい？
2020/05/16(土) 23:14:26.33
Code Jam Round2とは
2020/05/17(日) 01:15:30.59
google code jam
2020/05/17(日) 01:32:44.08
2問完答だけじゃ1000番以内無理だった
悔しい
2020/05/17(日) 02:34:57.89
>>252
Code Jam Round2レベルの実力とは
255仕様書無しさん
垢版 |
2020/05/17(日) 04:25:19.74
突破ボーダーでしょ
黄色中位くらいかね
2020/05/17(日) 19:32:40.22
>>230
https://arena.topcoder.com/
2020/05/17(日) 20:09:24.51
社会人になった競プロerが学生時代より弱くなるの、
競プロの能力が実務とは別物であることの、何よりの証明だと思うんだが...
ベテランが無精進で暖色になれるような問題内容でなければ、
レート≒エンジニアリング能力とは言えなくね?
2020/05/17(日) 20:13:26.57
時間が必要なのはなんでもそうなのでそれだけではなんとも
2020/05/17(日) 20:19:05.39
楽しいゲームをやってるのに実務実務うるさいな
2020/05/17(日) 20:30:11.55
実務に有利だエンジニア能力だって言ってるのは運営側なんだよなぁ
2020/05/17(日) 20:34:06.16
実際に必要なのはプログラミングより数学だしな
しょうがない
2020/05/17(日) 20:37:50.53
所詮数学コンテストだもん
2020/05/17(日) 20:55:01.56
数学速ときコンテストたのしー！
2020/05/17(日) 20:55:32.60
パズルたのしー
2020/05/17(日) 20:56:39.67
競プロが強ければ得する会社もあるけどそこに入るのに必要なのは競プロ力じゃなくて学歴だからね
競プロやる前に勉強しなさい学生よ
競プロは高学歴が打ち込む遊びだぞ
2020/05/17(日) 20:59:15.98
まあでも形式に慣れてないとか以外で緑にもなれないような人が同じような分野のコーディングバリバリできます！ってことはあまりなさそう
2020/05/17(日) 22:42:53.17
HとM勘違いして10分とかしてワロタ
2020/05/17(日) 22:44:58.07
言ったそばから数学コンだった
つまんね
2020/05/17(日) 22:48:30.32
まさか余弦定理が出ると思わなくてびっくりした
2020/05/17(日) 22:50:42.90
BFS勉強したばかりで良かった
2020/05/17(日) 22:57:01.46
三角関数くらいこれまでも散々出しただろ？と思われてるな
2020/05/17(日) 22:58:54.72
複素数を使えば頭を使う必要なし
2020/05/17(日) 23:02:50.40
むしろ余弦定理の方がややこしくねえか
わざとややこしく書いてる解説かこれ
2020/05/17(日) 23:08:52.75
余弦定理だと脳死でできるから楽
2020/05/17(日) 23:09:06.12
数え上げ人材育成コンテストだな
276仕様書無しさん
垢版 |
2020/05/17(日) 23:12:29.35
E，arccosの場合分けが辛すぎと思ったら全然違う方法だった・・・
2020/05/17(日) 23:12:54.80
E難しかったな
2020/05/17(日) 23:13:33.99
今日ので数学コンって言われるのは草
2020/05/17(日) 23:16:42.93
EってABC166Eと同じ方法で溶ける？
2020/05/17(日) 23:16:47.42
Atcoder 中学受験 Contest
281仕様書無しさん
垢版 |
2020/05/17(日) 23:21:04.84
D,幅探索で最初にオープンした所の親という方針でなぜ駄目だったのかわからない・・・・
2020/05/17(日) 23:22:54.37
E pairsみたいだな
考慮することが多くて本番で解くのは難しいわ
2020/05/17(日) 23:47:00.08
C問題、間の角度を求めてsqrt(a^2 + b^2 - 2a*b*cos(theta*PI/180.0))ではダメなんでしょうか？
最後の2つのケースだけWAになります

分刻みで時針も動かしてるし変数も全部倍精度で取ってるのですが・・・
2020/05/17(日) 23:48:36.16
>>283
間の角度が間違ってそう
2020/05/17(日) 23:49:30.97
theta=min(2pi-theta,theta)したらなおりそう
2020/05/17(日) 23:55:49.06
>>285
その式のpiとかthetaの単位はなんでしょうか？
>>283はPIが3.14…でthetaは角度（0≦theta＜180）なのですが
287仕様書無しさん
垢版 |
2020/05/18(月) 00:00:04.09
theta桁落ちしてそう
288仕様書無しさん
垢版 |
2020/05/18(月) 00:03:55.19
Eは直行したり、近いベクトルを高速に探索するみたいなのがCS的に普通ちゃ
2020/05/18(月) 04:31:56.31
競プロは仕事の役に立つと考える人、、
MBAは起業の役に立つとも考えてそう
2020/05/18(月) 06:35:25.25
>>281
それで平気だったよ
2020/05/18(月) 07:34:56.21
>>290
有難うございます。式はあってそうなのでテストケース公開を待ってみます
292仕様書無しさん
垢版 |
2020/05/18(月) 08:07:22.52
多重派遣偽装請負損害を助長して
稼働増やして収入減らした
安売り貯金なしドカタは
コロナ恐慌で制裁を受けるべき
2020/05/18(月) 08:27:48.48
>>291
ちなみに出力例は複数あるからテストケースのoutのみが正解ではないからね。
2020/05/18(月) 09:11:00.48
昨日のdiffはよ
2020/05/18(月) 11:33:07.97
経験上、x問目のdiffはx完最遅のパフォ-100〜200くらいのことが多いから
D600
E1600
F2400
くらいっぽそう
2020/05/18(月) 11:44:38.21
過去のBFSって1000くらい無かったっけ。
2020/05/18(月) 12:08:12.26
dfsするだけ、bfsするだけみたいなのは競プロの基本中の基本だから
もっと前のほうで出したらいい
2020/05/18(月) 12:11:04.13
295は適当だったな、D700E1700F2400くらいかな
2020/05/18(月) 12:13:46.01
きたぞ。
750、1800、2500くらい。
2020/05/18(月) 12:36:38.30
DいぇすだけじゃなくＮＯも作って欲しかった
連結成分がひとつじゃないやつ
301仕様書無しさん
垢版 |
2020/05/18(月) 12:48:55.23
昨日のEについて、解説にある連想配列までは作れたのですが、その後の『基礎的な数え上げ』ができませんでした…
数え上げって何か勉強の仕方ありますか？あまり競プロの解説記事もない気がするのですが…
高校数学からやり直せ、という話でしょうか？

>したがって，”仲の悪いつがい” になる傾きのペア (高々 N 通り) 全てについて，連想配列などを 使って各傾きになるイワシの個数が求まれば，その後は基礎的な数え上げの範疇です.
302仕様書無しさん
垢版 |
2020/05/18(月) 12:56:08.70
ここはwriterも説明足りなかったかなって反省してたとこだね
ある集合から自由に選べるのが2^n通りなのがわかれば
集合(S,T)から取り出したとき、すべてが片方の集合に属する場合の数は
Sのみ: (2^s)*1 (sはSの要素数)
Tのみ: (2^t)*1 (tはTの要素数)
になって、ここから両方空集合になる1通りを除いて
(2^s)+(2^t)-1になる
2020/05/18(月) 12:58:49.77
Dで非連結を判定するのは考察の量に比べて実装が重いからなあ
304仕様書無しさん
垢版 |
2020/05/18(月) 13:03:11.66
そんなに重いか？
1からBFSし終わって訪れてない点があればNoで終わりじゃない？
2020/05/18(月) 13:08:49.39
UnionFindでやっても良さそう
2020/05/18(月) 13:36:02.58
BFS だけで連結性判定終わってるのに Union Find 持ち出す理由がなくね
2020/05/18(月) 13:38:59.50
連結リストに出てこなかった数字は非連結（嘘解法）
308仕様書無しさん
垢版 |
2020/05/18(月) 15:02:20.50
>>302
書いていただいてありがたいのですが、集合S,Tをどう扱えば良いのかがわかりませんでした
例えば、傾き1/3,2,3,5のイワシがいるとしたら、1/3と3をペアにしてはならず、また1匹以上という制約からペアのルールを無視すると全体で2^4-1というのはわかるのですが、
そこから書いてもらってるS,Tの議論にどう紐づければ良いのでしょうか？
Sのみ、Tのみという考え方をするのであれば、1/3と3が別れるように、S=[1/3,2,5]、T=[2,3,5]とするのでしょうか？（ただこの場合は2,5を含んだケースをダブルカウントしてしまいそうな…）
2020/05/18(月) 15:07:18.29
一旦互いに仲が悪いようなペアだけで考えて、それぞれをかけて答えにする

その例だと
{1/3}←→{3} で 3通り
{}←→{2} で 2通り
{}←→{5} で 2通り

これらをかけて12通りから全部0匹の1通り引いて11通り
310仕様書無しさん
垢版 |
2020/05/18(月) 15:17:43.35
editorialに「基本的な数え上げの範疇」とか「証明は簡単、そうでないと直感的に嫌な気持ちになります」と書いてあったり、問題名が意味不明でわかりにくかったり、今回個人的にかなり不快な要素が多いがあまり燃えていない。
2020/05/18(月) 15:32:41.50
解説って考察の指針くらいしか書かれていないので、解説動画見た方がいいとおもうよ。
低レートが読んでも基礎がないから理解できないと思う。
312仕様書無しさん
垢版 |
2020/05/18(月) 15:40:51.99
>>309
ありがとうございます、わかってきました
仲が悪い組み合わせについてはそれらを一まとまりにして考えつつ、
仲悪い群(複数あっても良い)同志や、2や5などのその他の数字は独立で考えることができるので、それぞれの組み合わせ数をかけていく、という感じですかね

追加で理解を確認させていただきたいのですが、例えば1/3, 3, 3のように片方（あるいは両方）が
複数になった場合、 >>302 で書いているやり方で言うと、
{1/3}の取り方が2^1=2、{3, 3}の取り方は2^2=4、これらは相反する（独立ではない）ので、かけてはならず、
足しあわせて、2+4 =6となります
このあと、-1しているのはどういったケースを排除する目的なのでしょうか？
数え上げると、あり得るのは{}, {1/3}, {3}, {3}, {3, 3} の5通りなので、これで計算合っているとは思うのですが、、
イメージとしては、単純に2+4した時の、{}, {}, {1/3}, {3}, {3}, {3, 3} から最初の空集合の重複を取った感じでしょうか？
2020/05/18(月) 16:10:35.46
しょせんおまけ要素
2020/05/18(月) 16:14:46.97
editorialはわかってる人が読んでわかる程度に書かれていればいいと思う
わからない人にわからせるためにはそれ用にコストを掛けないと無理
315仕様書無しさん
垢版 |
2020/05/18(月) 16:24:16.38
>>312
両方空集合になるものを2回見ちゃってるからそれを引く目的であってる
どんなペアだろうと2^s+2^t通り列挙すると{}が2回出てくるからね
316仕様書無しさん
垢版 |
2020/05/18(月) 16:37:09.54
>>310
燃えるにも才能が必要
2020/05/18(月) 17:40:04.83
某黄色コーダー
「文句言ってんのは、お前がその問題解けないからだろ?」
だとさ
日本社会の基本はどこへ行っても弱い者いじめだね!
2020/05/18(月) 18:02:59.61
また変なの湧いてきたな
2020/05/18(月) 18:14:23.53
赤がこれ言っても燃えないのに黄色がこれ言うとキレるやつが出るあたりやっぱレート主義なんやなって
320仕様書無しさん
垢版 |
2020/05/18(月) 18:33:26.62
弱い者いじめとは思わない
経験の多い人ほど正しいことを言ってる可能性が高い
2020/05/18(月) 18:35:11.16
信者の発想
2020/05/18(月) 18:40:57.23
運営じゃない人を叩くつもりは無いぞ
(´・ω・`)
2020/05/18(月) 18:57:08.59
強くなりたくないけど文句言ってる奴は帰れ
強くなりたいけど文句言ってる奴は問題解け
強くて文句言ってる奴は問題作れ
2020/05/18(月) 19:04:01.91
信者がどうとかそういうのいいから
2020/05/18(月) 19:11:54.72
この話題がどうでもよくね
326仕様書無しさん
垢版 |
2020/05/18(月) 20:14:41.98
>>315
遅くなりましたがありがとうございます！
完全に理解しました、、、！
2020/05/18(月) 21:44:47.09
>>310
要素は多いけど全部小粒だからじゃない？
てか基本的な〜とか原始的な〜とかやめればいいのにな
どこまでが基本的か最初に定義しろ
2020/05/18(月) 21:54:33.19
>>317
黄色ってコンプレックス抱えてる人多そう
AｔCoderでも中途半端だし社会では役に立たないし
2020/05/18(月) 22:04:05.58
黄色は本当に掃いて捨てるほどいるからかなり精神をやられる
2020/05/18(月) 22:10:33.70
すぬけさんの解説は素晴らしい
2020/05/18(月) 22:24:00.44
令和ABC 前ならそれなりに希少だった気がするが現状はなあ
橙渇望してるやつかなり多いんでないか、自分がそうなんだけども
332仕様書無しさん
垢版 |
2020/05/18(月) 22:29:23.78
黄色が掃いて捨てるほどいるは嘘でしょ
2020/05/18(月) 22:45:43.07
黄色の人数は二倍になってるからね
https://mobile.twitter.com/saba_kpr/status/1257351326159319042
https://twitter.com/5chan_nel (5ch newer account)
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況