X

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

■ このスレッドは過去ログ倉庫に格納されています
0001仕様書無しさん
垢版 |
2020/06/30(火) 01:11:14.00
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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
※前スレ
競技プログラミングにハマるプログラマのスレ 26
https://medaka.5ch.net/test/read.cgi/prog/1592148203/
0383仕様書無しさん
垢版 |
2020/07/10(金) 06:43:32.55
すべてたのしい理想的な職場があるのか？想像上以外で
0384仕様書無しさん
垢版 |
2020/07/10(金) 09:37:29.81
>>378 は仕事が全部楽しくないって言ってるんじゃないと思うんですけど
0386仕様書無しさん
垢版 |
2020/07/10(金) 10:04:39.21
競プロはネトゲという前提を忘れてる奴多くないか
0387仕様書無しさん
垢版 |
2020/07/10(金) 10:41:23.45
ゲームと仕事の差に苦しむ奴も沢山いるだろうからな
0388仕様書無しさん
垢版 |
2020/07/10(金) 11:31:19.74
アクチュアリー試験、結局統計とかの数学出来るかどうかなので、特に競プロ関係ないがち（相関はあるけど）
0389仕様書無しさん
垢版 |
2020/07/10(金) 11:37:40.38
数学強い→競プロ強いとなるが、逆は必ずしも真ならずかもな
いや、多少の保証はできるか 数学だめなら暖色とかなれないだろうし
それはともかく、まだ発展途上だから俺達が盛り上げていくんだぞ
0390仕様書無しさん
垢版 |
2020/07/10(金) 12:23:07.94
理学部数学科を出てもプログラムできない人は山ほどいるだろ
0391仕様書無しさん
垢版 |
2020/07/10(金) 13:27:07.94
整数NをL以上H以下の整数の集まりに分割したい。
ただしA+BをAとBに分割するときA*Bというコストがかかる。
コストを最小化するための分割方法はどのようなものか。
解がない場合は考えない。


半分に分割し続けるのが良いかなと直感では思ったが、証明ができない。
有名問題っぽいので考え方分かる人がいたら教えてください。
0392仕様書無しさん
垢版 |
2020/07/10(金) 13:40:32.61
>>391
6を2以上2以下の整数に分割するとき、
6→3,3→(1,2),(1,2) コスト13
より
6→4,2→(2,2),2 コスト12
の方がコスト小さいからそのやり方は正しくないでしょ。
0394仕様書無しさん
垢版 |
2020/07/10(金) 14:02:16.27
a_1,...,a_nに分割するコストは分割する順番によらずΣa_i*((Σa_j)-a_i)/2=(N^2-Σ(a_i)^2)/2だからa_iの2乗和を最大化すればいい
だからたぶん各a_iができるだけ大きくかつ均等になるようにするとかが答え
0395仕様書無しさん
垢版 |
2020/07/10(金) 14:47:28.52
a_i の2乗和を最大化するのであれば a_i はなるべく偏っていた方がよいのでは？
例: N=6, L=2, H=4 のとき 6 -> 2+4 ならコストは 8 ですが 3+3 ならコストは 9 です
0396仕様書無しさん
垢版 |
2020/07/10(金) 15:17:06.84
できるだけHで埋めて、余りがL以上ならLを1つ用意して終わり
L未満なら調整してどうにかする
例えばN,L,H=100,6,8なら分割は13個で、8×12+4なので最後に4が余る→8×11+6×2に調整
N=97なら8×12+1→8×9+25→8×9+7×1+6×3
これが嘘解法でなければN,L,H<=10**9でも解けそうだが果たして
0401仕様書無しさん
垢版 |
2020/07/10(金) 21:16:23.78
>>395
偏ってた方が良いってのは、LとHを沢山作ったほうが良いってことか？
N → L,H,L,H,L,H,L,H,...
証明わからん


>>396
それ>>394と一緒ちゃう？
0405仕様書無しさん
垢版 |
2020/07/10(金) 23:55:50.31
ABC 6完安定する人って色でいうと黄くらいのレベル？
0406仕様書無しさん
垢版 |
2020/07/11(土) 00:00:24.72
ABCの青問題が全部解けたらそれだけで黄色になる
0407仕様書無しさん
垢版 |
2020/07/11(土) 01:25:57.18
自分は黄色中位だけどABCは基本全完できると思う(し、実際ほぼ毎週してる)
たま&#12316;にできない回があるが
でもABCとAGCで見てる能力がちょっと違うように感じてるから2000overでもABC全完安定しない人がいても驚かないな
0408仕様書無しさん
垢版 |
2020/07/11(土) 01:35:50.09
&#12316;！&#12316;！&#12316;！
いあ&#12316;&#12316;！いあ&#12316;&#12316;！はす&#12316;&#12316;&#12316;！
0411仕様書無しさん
垢版 |
2020/07/11(土) 10:14:46.46
>>394-396
大枠はこれでいいでしょ
できるだけ偏らせたほうがいいから、LともHとも違う分割の仕方は高々1つ
分割する個数も減らしたほうがいい(Lをばらしてほかのに割り振る)
だからLからHに分割する方法の中で、Hをたくさん作れる分割の仕方を求めるというのがやりたいことのほとんどなんだけど、
Lがたくさん存在する場合もあるから貪欲でやるのは難しい気がする?それとも>>396の二つ目の例みたいなものは数学的に簡単に求められる?
0413仕様書無しさん
垢版 |
2020/07/11(土) 11:01:56.65
最小分割の個数が、L*x <= N <= H*xを満たす最小のxでそれがわかれば分割の仕方も
出せるから定数で計算できるね
0414仕様書無しさん
垢版 |
2020/07/11(土) 11:14:18.20
実用上はにぶたんO(logn)で十分
場合分け頑張れば定数でいけるだろうけど
0415仕様書無しさん
垢版 |
2020/07/11(土) 11:17:21.74
二分探索って分割回数を二分探索か？
分割回数に対して単調ってなんで分かるっけ？
0418仕様書無しさん
垢版 |
2020/07/11(土) 13:00:25.06
N/Hの商をq,余りをrとする
r=0かL<=r<Hの場合は自明
そうでない場合、(L-r)/(H-L)の商をs,余りをtとする
t=0の場合、H×(q+1-s)+L×s
それ以外の場合、H×(q-s)+(L+(H-L)×t)+L×s
こうかな
0420仕様書無しさん
垢版 |
2020/07/11(土) 14:06:15.69
企業的にはABCのほうが嬉しいのかね、企業が選べるんだっけ
0421仕様書無しさん
垢版 |
2020/07/11(土) 14:20:53.13
参加者はABCの方が多くなるよね
2000以上の人をどのくらい重視するかによるんちゃうかな
0422仕様書無しさん
垢版 |
2020/07/11(土) 14:21:12.07
結果はどうでもよくて宣伝できればいいって感じなのかな
ってか今日か
0423仕様書無しさん
垢版 |
2020/07/11(土) 14:41:31.61
ABCでも暖色の人結構出るし宣伝的にはABCのほうが良さそうか
0425仕様書無しさん
垢版 |
2020/07/11(土) 16:22:38.45
ABCの過去問解いてるんだけど、同じ色でも昔の方が簡単な気がするのだが、正しい？
受験者のレベルが高くなってることを反映してるのかなと思ったのだが
0427仕様書無しさん
垢版 |
2020/07/11(土) 17:10:50.27
最近見かける受験者って表現気になる
正しい正しくないの話じゃなく各人の認識のしかたとして興味深い
0433仕様書無しさん
垢版 |
2020/07/11(土) 20:53:32.05
何よりABCはバズるしな
「エイシング」って単語がトレンド入りする可能性すらある
0437仕様書無しさん
垢版 |
2020/07/11(土) 22:45:10.06
パナソニック2020もそうだけど、企業コンABCのFに不可能を置くな
0439仕様書無しさん
垢版 |
2020/07/11(土) 22:52:36.24
コンテスト中にdifficulty予測出来るツールってありますか？
0446仕様書無しさん
垢版 |
2020/07/11(土) 23:20:05.85
Dコンテスト終了直後に投げたのが通ったわ、3分伸ばしてくれ
0451仕様書無しさん
垢版 |
2020/07/12(日) 00:03:30.26
先週の解説で日曜はないと思うってすぬけさんが言ってたような
0452仕様書無しさん
垢版 |
2020/07/12(日) 00:03:57.40
CDのdiff茶色って言ってるけどabc173のdiffと勘違いしてない？
エイシングのdiffもう出てる？
0453仕様書無しさん
垢版 |
2020/07/12(日) 00:04:15.84
英語版の解説pdfまだ出来てないの、外国の人かわいそうに…
0458仕様書無しさん
垢版 |
2020/07/12(日) 00:29:22.13
参加者7000人ちょっとか
なんで今日こんなに少ないの？普段のABC1万超えなのに
0459仕様書無しさん
垢版 |
2020/07/12(日) 00:37:54.02
企業コンだからABCって分からなかった人が相当数いるんちゃうかな
0462仕様書無しさん
垢版 |
2020/07/12(日) 00:50:18.89
賞金もないと普段のABCと変わらんからありがたみないな。宣伝効果的にどうなんだろ
0463仕様書無しさん
垢版 |
2020/07/12(日) 00:50:32.47
最近の企業コンはARCだったから、最近始めた人が勘違いしてもおかしくない
0464仕様書無しさん
垢版 |
2020/07/12(日) 00:54:53.06
ところで今回なぜ参加情報の登録項目があったんだ?
0465仕様書無しさん
垢版 |
2020/07/12(日) 01:09:49.99
コンテストの後って興奮しちゃってるのかなんなのか寝つけないわ
わかるやついる？
0466仕様書無しさん
垢版 |
2020/07/12(日) 01:13:26.19
そのせいでコドフォ出ると生活リズムが終わる。
0468仕様書無しさん
垢版 |
2020/07/12(日) 01:38:15.60
学生だったら良かったんだけどなあ。
社会人にはきつい
0470仕様書無しさん
垢版 |
2020/07/12(日) 03:40:09.11
Dのpopcount()なんですが、最大200000桁の割り算ってどう実装すればいいんでしょうか
2の200000乗だと64bit整数でも溢れますよね？
0471仕様書無しさん
垢版 |
2020/07/12(日) 03:42:38.41
繰り返し二乗法というアルゴリズムでaのK乗 mod MをO(log K)で計算できます
0472仕様書無しさん
垢版 |
2020/07/12(日) 05:11:42.35
普通に累乗のテーブルを作ったほうがいいんだよな
0473仕様書無しさん
垢版 |
2020/07/12(日) 05:13:31.64
modpowでもいいし頭から割り算の筆算みたいにmod取っていけばいい
0474仕様書無しさん
垢版 |
2020/07/12(日) 09:19:19.50
昨日のD問題はどうやって方針立てれば良かったんだ？
普通に問題文のまま実装しようとしてTLEになっちゃったんだが、その前に計算量オーバーしてるって気がつかなきゃいけなかったのか？
0475仕様書無しさん
垢版 |
2020/07/12(日) 09:35:46.96
2*10^5桁の数値を2*10^5回除算しようとした時点で負け
0476仕様書無しさん
垢版 |
2020/07/12(日) 10:26:51.53
さすがにDは愚直が許されないイメージ
自分の書いているコードの計算量を常に把握していれば気づくと思う
まあ中には計算量解析が難しくてそこが本質みたいな問題もあるけど
0477仕様書無しさん
垢版 |
2020/07/12(日) 11:23:53.29
>>471
ありがとうございます
2のK乗ということは最上位bitが1（「100」とか「10000」）が対象だと思うんですが、
「10101」のような値にはどうやって適用するのでしょうか？
0478仕様書無しさん
垢版 |
2020/07/12(日) 11:25:01.92
E天才すぎる
こういう貪欲どうやって思いつくんだよ
0479仕様書無しさん
垢版 |
2020/07/12(日) 12:24:22.02
>>477
2進数の10101=2^4+2^2+2^0
なので、それぞれに繰り返し二乗法を用いて足し合わせればよいです
今回の制約なら、2^nを0<=n<=桁数まで計算しておいて足し合わせるのでも良いです
0480仕様書無しさん
垢版 |
2020/07/12(日) 13:11:24.93
D改めて見てるけどかなり難しいだろこれ…
これスラスラできたら青レベルだろ
0481仕様書無しさん
垢版 |
2020/07/12(日) 15:22:21.97
C灰diffなのもすげえな、、。一昔前なら緑はありそう。
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況