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

レス数が1000を超えています。これ以上書き込みはできません。
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/06/12(金) 11:32:08.19
dp[0][0] = 1
for i in [1, R*S]
　for j in [1, R]
　　if i ≦ j*S
　　　dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
return dp[R*S][R] * factorial(R)
2020/06/12(金) 11:33:24.85
行数の規制かと思ってレスを小分けにしてしまったことを先に謝罪しておきます。
すみませんでした。
2020/06/12(金) 12:16:51.71
dp[i][j]の解釈は正しいと思うぞ(より正確に言うとroom winnerの順位でroomをソートすることを考えている)

更新は
- i人目がj部屋目の room winner になる
もしくは
- i人目がj部屋目の room winner にならない
のいずれかで、それぞれ
- i-1人目までをj-1部屋に入れた時の room winner の順列の通り数
と
- i-1人目までをj部屋に入れた時の room winner の順列の通り数
を足せばよい と解釈できる
2020/06/12(金) 12:17:06.32
んー分からん
俺が考えた方針だけ書くか
対称なのでroom winnerの順位を降順に並べてルーム1〜Rとし、最後にR!をかける
dp[i][j]:=i部屋目のroom winnerが全体でj位の場合の数　とする
このときj<=(i-1)*Sが成り立つのでこれで条件分岐
遷移はdp[i][j]=dp[i-1][1]+…+dp[i-1][j-1]
これは累積和で高速に求められるので全体でO(SR^2)

何か間違ってたら言ってくれ
2020/06/12(金) 12:19:24.19
>>905
累積和の部分を整理してi,jを入れ替えたら >>902 のコードと同じになる
2020/06/12(金) 12:28:30.33
>>906
サンクス
言われてみるとそうだな
自分としてはこのdpの持ち方のが自然に見えるな
2020/06/12(金) 14:03:02.76
問題のURLはってくれな
2020/06/12(金) 14:16:38.00
解決したから要らなくね
2020/06/12(金) 14:39:42.06
一般に問題について聞く人はという意味でした
911899
垢版 |
2020/06/12(金) 15:30:06.90
>>904
たとえば「i人目がj-1部屋目のroom winnerになる」は「i人目がj部屋目の room winner にならない」に入ってる？
2020/06/12(金) 15:53:15.84
1位から順に人間を部屋に押し込む
i位目までの人間を部屋に押し込んだとき、j部屋に（部屋の区別は考えない）人がいる場合の数がdp[i][j]
i位目の人は人のいる部屋に入るか（dp[i-1][j]から遷移）誰もいない部屋に入るか（dp[i-1][j-1]から遷移）のどちらか
2020/06/12(金) 16:30:02.18
あとこだのマラソン楽しみ
2020/06/12(金) 16:44:21.65
2時間て短いなあ
自分なりの開発サイクル回してスコア上げてくのが醍醐味だと思ってるから、少なくとも1日くらいくれないとやる気起きない
2020/06/12(金) 16:50:17.94
Introductionなんだから2時間くらいでいいだろ…
数日かけるマラソンマッチが敷居高いと感じる人のためのコンテストだぞ
2020/06/12(金) 23:57:19.01
すぬけさんの解説好き
2020/06/13(土) 00:23:30.38
abcの解説放送見てないマン
2020/06/13(土) 02:02:39.90
すぬけさんは頭悪いとか言わないから好き
2020/06/13(土) 08:52:58.29
速いと噂のjuliaですが、
atcoderの実行時間を見るとpythonより遅い気がしますが
どうですか
2020/06/13(土) 10:53:28.06
ネタが古い
2020/06/13(土) 13:08:09.31
>>26
そういえばこれのソースないの？
ないならid入れてほしいんだけど
2020/06/13(土) 14:47:08.29
https://info.5ch.net/index.php/SETTING.TXT
https://medaka.5ch.net/prog/SETTING.TXT
雑にググったけどもBBS_NO_ID=checkedになってるから強制非表示なんじゃない
2020/06/13(土) 16:30:59.01
>>919
コンパイル時間が必要なのと、コンパイル結果をテストケース毎にジャッジサーバ内でクリアするから、毎ケースコンパイル実行してあまり早くないとチョクダイが言ってた記憶
2020/06/13(土) 16:37:01.53
>>922
板としてのデフォルトであってスレごとに変えられるんじゃないの？
2020/06/13(土) 16:40:27.87
pythonと比べればjavaもc#もpypyも遅いんやで
2020/06/13(土) 17:17:40.63
そうして、C++/Python併用が流行るわけですね
2020/06/13(土) 17:29:30.25
捨てスレでも立ててみたらわかるんでない
2020/06/13(土) 20:23:21.15
入れてほしい奴がスレ立てるなりすれば良いんじゃねえの？
2020/06/13(土) 22:39:55.23
別に落ちるの待たなくてもいつでも建てればいいじゃん
俺は非表示で次スレ立てるけど
2020/06/13(土) 23:19:54.12
ID非表示にしたがるやつなんか後ろめたいことでもあるんか？
2020/06/13(土) 23:26:30.65
今日の難易度で毎週やってくれ
2020/06/13(土) 23:26:35.85
なんで後ろめたいとかそういう話にもってくんだろう。非表示がいい人はこのままで、表示が良い人は新しい方で、で終わるでしょ。
2020/06/13(土) 23:52:27.27
もうすぐこどふぉ
2020/06/14(日) 00:12:32.59
Dがpythonだとかなーり辛かった
新しい言語習得しようかなあ
2020/06/14(日) 00:44:21.61
1位でも海外だと賞金貰えないのかわいそう
2020/06/14(日) 00:46:41.94
まだ初心者も初心者なんだけど、今日のC問題いもす使うところまではわかったんだけど、kの回数を減らせることに気がつかずACできなかった
こういうのって、精進していけば気がつきやすくなるものなんでしょうか？
今はまだ典型的な解法覚えつつABCのC埋めしてる段階です
2020/06/14(日) 01:04:16.82
実験コードを書くようにすればいいんじゃね
2020/06/14(日) 01:50:50.18
>>930
なんで非表示スレに居座ってるんだ？
とっととIDスレに行けよ
2020/06/14(日) 03:06:01.43
今日のCは

それぞれが影響しあって範囲がどんどん広くなるな〜
2つ目のサンプル見るに倍々くらいで増えてもおかしくなさそうだな〜
logだけ見ればいい感じかな？
これ最大ケース書くのすごい楽だな、愚直で試してみよう
やっぱり最大ケースでも100回やる前にカンストするんだな、じゃあ愚直に書けばいいか

みたいな感じで解いた
2020/06/14(日) 04:33:48.83
atcoder3回目でまだimos法まで勉強が及んでなかったんだけど、解説の通りにやってみたらほんとにきれいに揃うので感動した
2020/06/14(日) 05:34:29.61
わかる
imos法は感動したし今でも好き
2020/06/14(日) 06:28:52.69
C問題は
「愚直にやるとO(NK)で間に合わんな、ということは

1. 複数回操作した結果を高速で求める方法がある
2. 実はそのうち収束するから実際にK回操作しなくてもいい

のどっちかやな。」
「1は思いつかんから多分2なんやろ。証明できてないけどええかｗ」
って感じでエスパー気味に解いた
2020/06/14(日) 10:23:20.75
全部Nになるのは分かってたのにいもす法わかんなかった
勉強足りてないな
2020/06/14(日) 10:28:55.98
遅延セグ木でTLEした馬鹿がいたらしい
なんにも理解してなさそう
2020/06/14(日) 10:34:47.51
方針間違えただけでそこまで言うかね
ほぼ晒しじゃん
2020/06/14(日) 10:52:52.85
問題の質チェックの厳しさがWriterのレートに反比例してないか
2020/06/14(日) 11:04:36.06
Dが実装次第でカツカツなこと以外問題あったっけ
2020/06/14(日) 11:06:28.23
ある素数が 25 mod 26 である確率が大体 1/13 くらいっていう主張をよく見るんだけどこれなんで？
2020/06/14(日) 11:09:13.07
素数はほとんど奇数であって、素数を26で割った余りはおそらく一様であることから
2020/06/14(日) 11:14:26.22
>>949
ありがとう
ほとんど奇数っていうの見逃してた(は？)
2020/06/14(日) 11:57:28.17
>>947
Eで論理和と論理積をmapで持つ愚直が通ったらしい
(てかDと若干解法被ってんだな)
2020/06/14(日) 12:04:15.47
>>934
jit使えばどうよ
2020/06/14(日) 12:28:06.63
>> 951
試してみたら確かにっ通った、まあでも通したもん勝ちではあるなこれ
自分の実装だと↓な入力でTLE したがソート とかシャッフルとか挟まされたらどうしようもなさげ
50 50 0 262143
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192
2020/06/14(日) 13:15:18.06
>>953
制約は相異なる整数なのでその入力はinvalid
2020/06/14(日) 13:29:06.74
>> 954
言われて気づいた
なんで相異なる制約にしてるんだこれ
2020/06/14(日) 13:43:01.10
>>955
知らん
相異なる制約じゃないと解けないのかなとか思ってしまったけどそうじゃなくて、なんなんだよとは思った
2020/06/14(日) 15:50:03.13
赤ちゃんライター VS 社会不適合者ライター
2020/06/14(日) 16:45:43.93
SRM710のdiv2-hardをC++でACできる人いる？
C++で通してる人一人もいない
2020/06/14(日) 20:53:00.18
今日のABC、Write的にO(1)問題きそう
2020/06/14(日) 20:59:29.70
教育的とかいいそう
2020/06/14(日) 23:00:44.89
Cの解説、2段落目いらなくねえか
書いた理由がわからんぞこれ
2020/06/14(日) 23:08:27.80
連立方程式解けなくて時間溶かしたｗｗ
2020/06/14(日) 23:13:11.88
何も考えずに二重ループでいい
2020/06/14(日) 23:14:41.18
あの解説は荒れる
2020/06/14(日) 23:14:58.10
chokudaiが解説どこまで手を抜けるか探るなよって言った矢先にこれ
2020/06/14(日) 23:17:59.49
1段落目で解説としては完結してるからなあ
一言多いタイプの人間かこれ
2020/06/14(日) 23:24:11.36
B問題相当ならB問題で出せわかる
2020/06/14(日) 23:24:41.37
C問題解けないレベルの初心者を煽るとかやべえな
何かの病気かな
2020/06/14(日) 23:26:40.58
B,C問題の解説だけわざわざ解説担当の名前まで書いてて、炎上させてくれと言わんばかり。
2020/06/14(日) 23:36:00.59
全探索しましょうって書けばいいのに言い方悪いわ
971仕様書無しさん
垢版 |
2020/06/14(日) 23:38:01.64
E,優先度queだと基本削除できないので違うと思って二分探索と組み合わせて死んだけど、赤黒木みたいな森の奥に生えてる木だと消せるのか・・・
2020/06/14(日) 23:39:06.85
B問題を何とか通してコンテスト終了までC問題をWA連発させながら必死で取り組んだ初心者が、こんな解説読んだら泣いちゃうよ
2020/06/14(日) 23:41:39.59
削除できなくても取り出すときにチェックすればできるよ
974仕様書無しさん
垢版 |
2020/06/14(日) 23:42:11.74
門外漢から質問なんだけど、競プロが強いやつって実務でもすごいの？
2020/06/14(日) 23:43:40.21
↓自演
2020/06/14(日) 23:44:22.94
自分まさにターゲット近辺の雑魚グラマだけど、cの解説読んでもなるほどなぁとしか思わんかったよ。怒ってくれてるのってもっとレベルの高い人の義憤な印象だわ
2020/06/14(日) 23:44:41.61
Googleの競プロ勢はいまいちだってPeter Norvigが言ってた
2020/06/14(日) 23:47:52.56
けんちょんがC解説に便乗した煽りコメントをいいねしまくってて笑う
コイツ性格最悪やな
2020/06/14(日) 23:48:55.58
問題Cを解かれる方にそのような説明は不要、ということは
この問題の説明が必要な方は問題Cを解こうとするべきではない、という事か？
2020/06/14(日) 23:51:31.20
選民
981仕様書無しさん
垢版 |
2020/06/14(日) 23:52:49.61
>>977
回答さんきゅー
2020/06/14(日) 23:53:35.66
高知能アスペばっかりだから意図的にしろそうでないにしろこんなの簡単に解けるだろ？と一言マウント取らないと自我を保てないやつが多いんや
2020/06/14(日) 23:55:46.81
しょせんおまけ要素
2020/06/14(日) 23:57:04.65
大なり小なり不適切な言動はまとめておいてスポンサーに報告してあげると良いと思う
2020/06/15(月) 00:03:29.53
やはり義憤で燃えてる感
2020/06/15(月) 00:04:02.03
ギャフンと言わせたい
2020/06/15(月) 00:05:40.23
>>986
＼ﾄﾞｯ／
2020/06/15(月) 00:06:02.65
無能社長はあーだこーだ理由付けて解説のチェックしたがらないけど
こういう事がそこそこの頻度であるからチェックしろって言われんだよな
挙句それで不満が出たら毎度毎度pdf出さないようにすると脅して擁護させる
社長様、バイトが東大生ばかりで何も言えなかったりするのか？
2020/06/15(月) 00:06:29.96
義ャ憤
2020/06/15(月) 00:10:27.25
解説pdfは非公式、ってスタンスもどうかと思う。
2020/06/15(月) 00:11:35.46
社長本人と社長にpdf廃止しないでください！ってリプか引用RTしてる奴ら全員ブロックすればTwitter快適になるかな
2020/06/15(月) 00:11:45.93
別にこのくらいいんじゃね？
文章が気取りすぎ、痛い、くらいでスルーが妥当だよ
993仕様書無しさん
垢版 |
2020/06/15(月) 00:12:40.78
解説pdfなんてあんなもんでいいと思うけど
被害者ぶるのはなんか違うよな
2020/06/15(月) 00:12:45.70
もしこれが企業スポンサードABCだったら悪いと思うから
社長は解説がAtCoderのコンテンツなのかwriterの好意によるおまけなのかはっきりさせろ
2020/06/15(月) 00:13:49.55
全ABCにスポンサーつければ解決
2020/06/15(月) 00:15:52.78
>>988
人材不足から擁護一択になるのはそうだろうね
余計な一言が問題なのに丁寧な解説は無理〜だの話すり替えてるし
しょうもな
2020/06/15(月) 00:15:56.32
abcは毎週やってる分、解説もこの程度のクオリティでいいと思う
2020/06/15(月) 00:18:06.49
お前らそんな解説読むのか
細かいな
2020/06/15(月) 00:18:28.29
批判の大半はもう少しなんとかならないの？程度なのに
一部の過激な意見を引っ張ってそれはコストがかかりすぎるから無理、無理だからpdf出さないようにしようかな、と
こういう不誠実な対応をよくするよね
2020/06/15(月) 00:18:41.78
1000なら毎回chokudaiが解説を書く。英語も。
10011001
垢版 |
Over 1000Thread
このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 36日 23時間 30分 8秒
レス数が1000を超えています。これ以上書き込みはできません。
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況