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

■ このスレッドは過去ログ倉庫に格納されています
1仕様書無しさん
垢版 |
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/
478仕様書無しさん
垢版 |
2020/07/12(日) 11:25:01.92
E天才すぎる
こういう貪欲どうやって思いつくんだよ
2020/07/12(日) 12:24:22.02
>>477
2進数の10101=2^4+2^2+2^0
なので、それぞれに繰り返し二乗法を用いて足し合わせればよいです
今回の制約なら、2^nを0<=n<=桁数まで計算しておいて足し合わせるのでも良いです
2020/07/12(日) 13:11:24.93
D改めて見てるけどかなり難しいだろこれ…
これスラスラできたら青レベルだろ
2020/07/12(日) 15:22:21.97
C灰diffなのもすげえな、、。一昔前なら緑はありそう。
2020/07/12(日) 15:33:11.54
c灰なのか。落ち込むわ…
2020/07/12(日) 16:23:11.49
といってもx,y,zの全探索だからな
2020/07/12(日) 16:24:53.06
普段のABCと違って企業コンなのが難易度予想を狂わせたところはあるかもね
2020/07/12(日) 17:26:30.70
このスレ来てる人でC出来なかった人いる？
2020/07/12(日) 17:41:35.33
ノ
2020/07/12(日) 17:55:17.44
自分も
2020/07/12(日) 18:34:01.04
n,x,yがわかったらzが求まる、ってやり方(Otoshidama)でもできる
2020/07/12(日) 18:41:49.07
10^8になると思うん、だけど通るんやろか
2020/07/12(日) 18:44:06.38
10^6だろ…
2020/07/12(日) 19:21:41.56
探索範囲を絞ればそこまで落ちるかもしれないが、それを全探索というか?
2020/07/12(日) 19:24:33.65
nが10^4でx,yが100だから10^8じゃない？
2020/07/12(日) 19:29:44.32
配列とかで個数カウントすればx,y,zで10^6
2020/07/12(日) 19:33:26.29
あーx,y,z全探索で10^6に収まるのか
N,x,yでx<=yに絞ってやって1200msで通したわ
2020/07/12(日) 19:34:09.65
いや、>>488を受けての発言だったのよ。
c++なら通るんだろうけど自分rubyだったんで諦めた
496仕様書無しさん
垢版 |
2020/07/12(日) 19:35:31.86
全探索とはいえ見た目が因数分解できそうな引っ掛けやf(1)から順に求めようとすると詰むところとか灰diffって感じはしないよね
2020/07/12(日) 20:02:20.10
>>495
実はN<=10^4まで全て求まれば数値を埋め込めるのでコンテスト時間に間に合えばokという解法もある
2020/07/12(日) 20:17:20.52
解説放送はよ
2020/07/12(日) 20:26:03.92
>>497
おー、なるほど
2020/07/12(日) 20:30:41.55
Ruby・・・getsをgets.to_sに書き換えてCrystal使え
2020/07/12(日) 21:04:30.96
Aは入出力、Bはif文、Cはfor文
となると全探索しかないだろ
2020/07/12(日) 23:58:32.93
>>479
実装できました、ありがとうございます
ちなみに、「2進数のmodが各桁のmodの和と等しい」というのは何かの定理なんでしょうか？
調べたら合同式というのが出てきたんですがよくわからず…
2020/07/12(日) 23:58:51.60
おいこどふぉ落ちてるが、寝て良いか？
2020/07/13(月) 00:05:54.08
数学がちょっと得意な人がPython覚えて何回か参加したら青や黄になれるのにプログラマの能力の何が保証できるの？
2020/07/13(月) 00:08:49.93
>>502
一般的に整数a,b,Mに対して、a mod M=A, b mod M=Bとしたとき、
a+b mod M = A+B mod Mが成り立ちます
これは、足し算の他に引き算、掛け算、累乗などで成り立ちます
合同式で調べるのが早いと思いますが、a=xM+A, b=yM+Bと分解でき、代入すると証明できます
2020/07/13(月) 00:22:49.19
数学がちょっと得意なことが保証できる
2020/07/13(月) 00:28:49.86
すごく得意な人がすぐ橙になったりも
2020/07/13(月) 00:33:43.44
逆に言うと競技プログラミングがあるから入試数学がなくなっても理系人材の能力評価に支障はなくなった
文科省が入試改革で好き勝手やってもその辺のリスクはもはやない
2020/07/13(月) 00:38:13.60
微分積分・ベクトル「」
2020/07/13(月) 00:42:53.54
ちょっとのレベルが高すぎる
2020/07/13(月) 01:01:36.08
ちょっと＝東大か京大の理系
2020/07/13(月) 01:02:15.15
東大京大でも上位1%だろ
2020/07/13(月) 01:03:28.22
または筑駒とか灘とかの数強だがそれらは普通の東大理系より圧倒的に上だし。
2020/07/13(月) 02:13:59.47
東大理系なら無精進で青はそれなりにいそうだけどな
2020/07/13(月) 02:15:47.36
でも実情は東大でも青は上位20%なんだよね
2020/07/13(月) 03:08:11.07
他に山程やること、面白いことがある中で競プロを選んだ人の割合が20%なんだろうな
2020/07/13(月) 03:23:56.72
多杉内
2020/07/13(月) 03:29:14.74
黄色なんだけど東大京大理系の平均よりは数学力高いってことでいい？
2020/07/13(月) 04:00:27.04
ちゃんと微積できますか
2020/07/13(月) 04:18:02.02
ある整数nが他の整数の4乗であることの判定ってどうする？
pow((int)pow(n, 1.0/4.0), 4) が n であるか調べる？
割と長いしキャストとかミスりそうで嫌なんだが
2020/07/13(月) 04:28:30.14
それでやるかなあ
2020/07/13(月) 04:32:30.51
ABCでギリなりましただったらダメ
2020/07/13(月) 04:34:21.35
ll x=pow(n,0.25)+0.5;
return x*x*x*x==n;
2020/07/13(月) 04:48:42.64
10^18位のオーダーなら全探索でも余裕だろうけど
2020/07/13(月) 05:09:54.46
余裕があれば全探索
なければにぶたん
2020/07/13(月) 05:15:00.01
>>522
黄だまりを否定するならratedコンテストをくれ
2020/07/13(月) 08:28:11.48
参加回数10回超えた後って、レーティングってどのくらい変動するものなの？
現在のレートx 獲得パフォyとすると、大体abs(x-y)/10くらいの変動幅？
2020/07/13(月) 09:22:35.80
>>527
AtCoder Rating Simulatorで調べてみて
2020/07/13(月) 09:54:49.92
数学の実力の証明がしたいなら数検1級でもとればいい
2020/07/13(月) 12:34:19.79
>>529
数検1級はどっちかというと計算力みたいな方向性で
数学的な論理力はあまり問われないから純粋な数学の実力の証明とは言えないと思うな
2020/07/13(月) 12:34:42.50
もちろん計算力は実用上とても重要だが
532仕様書無しさん
垢版 |
2020/07/13(月) 13:24:44.92
微積も出ないうえに超重要な線形代数さえ黄色になるのに使うのは行列累乗と吐き出しぐらいなので...（特異値分解どころか固有値の計算すら出ない）
算数力の保証にはなる
2020/07/13(月) 13:52:00.83
競技中学受験数学
2020/07/13(月) 16:39:16.85
「日本が世界各国に追いつけなくなる」　日本版シリコンバレー設立へ
https://asahi.5ch.net/test/read.cgi/newsplus/1594624492/
４都市圏をグローバル拠点都市として選定

・東京都・横浜市
・名古屋市・浜松市
・大阪市・京都市・神戸市
・福岡市
535仕様書無しさん
垢版 |
2020/07/13(月) 17:48:15.97
シリコンバレー目指すなら地方に作りゃいいのに
2020/07/13(月) 22:25:54.36
0 <= x1, x2, x3, x4, x5
x1 + x2 + x3 + x4 + x5 <= N
を満たすすべての (x1, x2, x3, x4, x5) について、Σ(x1 * x2 * x3 * x4 * x5) を求めてください

という問題について質問です

2つの条件を満たすものの個数が Combination(N + 5, 5) であることは理解したのですが、
そこから Σ(x1 * x2 * x3 * x4 * x5) という式を Combination(N + 5, 10) に言い換える方法がわかりません
（n < k のとき、Combination(n, k) = 0 とします）

解説放送を見てもわからなかったのでこちらで質問いたしました
回答よろしくお願いします
2020/07/13(月) 22:40:15.45
質問する人は問題のURLはってくれな
2020/07/13(月) 22:47:01.48
これは問題そのままじゃなくて途中に現れる部分だから仕方ないんでは？
2020/07/13(月) 22:48:09.04
https://atcoder.jp/contests/aising2020/tasks/aising2020_f
こちらの問題です
といっても問題そのままではなく少しシンプルにしたものですが…
2020/07/13(月) 22:51:22.95
○N個と｜5個を並べて、一番右のグループ以外から○を●に置き換える方法に対応
これは
●｜●｜●｜●｜●｜
に○をN-5個挿入する方法と同じ
2020/07/13(月) 22:55:54.05
>>540
回答ありがとうございます
その部分については理解しているのですが、なぜその組み合わせ数が Σ(x1 * x2 * x3 * x4 * x5) になるかが理解できないです…
2020/07/13(月) 22:58:40.95
>>541
x1個の○、…、x5個の○から一つずつ●に置き換える方法がx1*...*x5通りということではなく？（馬鹿にしてるわけではないです）
2020/07/13(月) 23:06:00.40
542の言い換えは、普通は知らないと浮かばないレベルの発想だと思います。高度競プロ人材はこういうの得意ですよね。
2020/07/13(月) 23:07:00.45
542単独の話ではなくこの問題の中でということで
2020/07/13(月) 23:17:47.49
そこは解説pdfにちゃんと書いてあるから（分割を行った後、〜対応しています？）大丈夫かと思っちゃった
2020/07/13(月) 23:28:17.96
理解できた気がします
解説放送の方針を勘違いしていました

「x1 * x2 * x3 * x4 * x5 = A を満たす A はいくつあるか」を数え上げるわけではなく、
たとえば (x1, x2, x3, x4, x5) = (1, 3, 1, 1, 2) のとき、
(1, 3, 1, 1, 2) が 6 回数え上げられるので自ずと A に一致する、ということだったのですね

難しいです
自力で思いつくのは大変そうです…
回答ありがとうございました
2020/07/13(月) 23:33:09.07
>>505
合同式について今日色々調べていたのですが、使えないケースとかありますか？
例えば13mod10は2^3+2^1+2^0に変換できますが、各項を繰り返し二乗法で計算すると
8+2+1＝13となってしまい、期待した答え（余り3）が得られないです
2020/07/13(月) 23:47:33.22
アホか？
2020/07/13(月) 23:51:21.27
>>547
最後にmod取るの忘れてるね
2020/07/14(火) 00:05:28.58
>>549
すみません多分私がちゃんと理解できてないのですが…
適当な値が思いつかず13を例にしましたが、64bitに入らないような大きい数の場合は
繰り返し二乗法だけでは最後までは計算できないという事なのでしょうか？
（元々大きい数に対してmodを取りたくて、繰り返し二乗法で計算する(>>471)とコメントを頂いたので）
2020/07/14(火) 00:12:16.49
なんか玉石混交過ぎるねここに投げられる質問
>>391とかは結局まだ証明ないし、>>536とかはやるだけ・読むだけっていう
552550
垢版 |
2020/07/14(火) 00:20:44.44
非常に分かり辛い質問になってしまいました…

繰り返し二乗法で計算したXmod10の結果Yが10以上の場合、最終的な余りをどう求めるべきでしょうか？
Y=13なら13%10で3が求まりますが、Yが64bitに入らない数値だとどうすればよいのでしょうか
2020/07/14(火) 00:22:50.86
1回の演算ごとにmod取ればいい
2020/07/14(火) 00:23:29.04
繰り返し二乗法で計算した値がmodより大きくなるってどういうこと
2020/07/14(火) 00:25:46.53
>>552
加算や乗算をするたびにmodを取るようにすれば、
modが10^9+7とかであれば64ビットを超えることはないです
2020/07/14(火) 00:37:47.33
動的計画法と線形計画法はどのような共通点がありますか？
2020/07/14(火) 00:43:59.56
後ろ3文字が一緒なことくらい
2020/07/14(火) 00:47:34.58
536がやるだけって緩めに見て上位200.人ぐらい？
2020/07/14(火) 00:48:32.81
>>553>>555
有難うございます（何度もレスしてすみません）
ここで言う「modを取る」とは繰り返し二乗法を使わないで、という事でしょうか？
>>547で挙げた13mod10の場合、2^3+2^1+2^0のどの項も10未満なのでmod取って和が13になってしまいます
2020/07/14(火) 00:52:25.45
>>559
modを取った和の13のmodをさらに取ればいい
2020/07/14(火) 01:07:55.85
>>560
「13のmodを更に取る」というのは13mod10を計算する、で合っていますか？そうするとまた13になってしまいます(>>547の通り)
（何か私が根本的に勘違いしているのかもしれません）

または、modの計算を1回目は繰り返し二乗法で、1回で答えが出なければ普通に計算（A%B）する、
というルールでやるという意味でしょうか。
2020/07/14(火) 01:11:15.74
1010100....01_(2) みたいな数のmodはすぐに計算できないけど、各桁を繰り返し2乗法でmod取りながら求めた値はmod以下だよね
それを足していく時もmodの2倍より大きくならないから、毎回あまりを取りながら足したらいいよ
2020/07/14(火) 01:11:36.67
13 mod 10 は 3 だよ
2020/07/14(火) 01:13:38.72
例えば、27=11011_(2) mod 10 を求めたかったら、
2^0=1 mod 10
2^1=2*2^0=2 mod 10
2^2=(2^1)^2=2*2=4 mod 10
2^3=2*2^2=8 mod 10
2^4=(2^2)^2=4*4=16=6 mod 10
を利用して、
27=2^4+2^3+2^1+2^0
=6+8+2+1
=14+2+1
=4+2+1
=6+1
=7 mod 10
と求められる
2020/07/14(火) 01:20:24.61
皆親切すぎだろ
2020/07/14(火) 01:21:43.80
大きな数のあまりを取るのは難しいけど、小さい数のあまりは％演算子とかで取れるから、それを忘れてるんじゃないかな
2020/07/14(火) 01:23:17.83
てか13って2^3+2^2+2^0じゃん
今気づいた
2020/07/14(火) 01:26:32.11
>>551
>>396じゃお気に召さないかね、証明ではないからか？
二乗和の最大化なので、できるだけ最大の数字を増やした方が良い(a+b=c+d,a>b,c>dのときa>cであればaとbに分けた方が良い)
a^2+b^2-c^2-d^2=(a+c)(a-c)-(d+b)(d-b)
a-c=d-bより(a+c-d-b)(a-c)>0、よって示された
569仕様書無しさん
垢版 |
2020/07/14(火) 01:28:16.23
え、540、542の言い換え天才すぎない？この言い換え典型なの？
典型じゃないとしたら自分には無理だから、形式的冪級数履修するか…
2020/07/14(火) 01:39:47.97
>>562>>564
ご丁寧に有難うございます！理解できた気がしました
示して頂いたこの部分（=14+2+1=4+2+1）が「余りを取りながら足す」という事だったんですね

コメントして頂いた方々有難うございました（かなりスレ汚してしまいすみません）

>>566
小さい数が％で計算できるのは分かっているのですが、
その「大きな数」と「小さな数」の判断（どこからが「大きな数」か）をどうすればいいかで悩んでいました
（ここはまだ理解できてないので今後自分で調べようと思います）
2020/07/14(火) 01:55:13.38
AtCoder上でパッと自分が思い出せるだけで2問はあるからど典型じゃないかなあ
572仕様書無しさん
垢版 |
2020/07/14(火) 01:59:07.16
典型ならこの手法も覚えておくか、ありがと
2020/07/14(火) 02:09:35.13
はー天才すぎる無理やろこんなんからの意外とすぐまた出会うってのあるあるだからな
574仕様書無しさん
垢版 |
2020/07/14(火) 17:56:13.86
すぬけさんすき
他のatcoderのひとだいたいすきじゃない
2020/07/14(火) 19:33:29.89
りんごさんとwataさんの外から見て嫌いになる要素何？
2020/07/14(火) 20:18:09.43
分数の演算を行う構造体を作ろうと思うのですが、使うことはあるでしょうか？
2020/07/14(火) 20:24:38.59
普通にあります
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況