競技プログラミングにハマるプログラマのスレ 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/
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
普通にあります
2020/07/14(火) 20:28:46.46
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1131&;lang=ja
2020/07/14(火) 20:29:00.88
赤になるまでは〜のツイートは思うところある人いそう
rngさんはmaroonさんにadmin完全に引き継いでもらったあとcontestantで無双してほしいな
2020/07/14(火) 21:01:24.34
分数を表す構造体、足し合わせる分数が多いと通分したときにすぐに分母がオーバーフローしそうで怖い
2020/07/14(火) 21:03:54.53
多倍長整数使えよ
2020/07/14(火) 21:12:20.36
今の時代に多倍長に対応した分数の構造体を使う問題が出るとは思えない
そんな問題を作る橙以上の人がいるとは思えないし、
もし作ったとしても絶対悪問と言われる
やっぱり分数の構造体（特に多倍長に対応したもの）を作る必要性が見い出せない…
583仕様書無しさん
垢版 |
2020/07/14(火) 21:22:22.32
ちょくだいは最近就活就活言い過ぎで不快なんだよな、それがないとお金入ってこないのはわかるけど
まわり見てても就活の結果とレートそこまで相関ないし
2020/07/14(火) 21:38:16.07
boost/multiprecisionの基本的な使い方押さえときゃよくね
2020/07/14(火) 21:58:43.80
分数の構造体の件、作っても使わなそうですし、
作る過程で得られるものが特になさそうなので作らないことにします
レスしてくださった皆様ありがとうございました
boost/setprecisionの基本的な使い方についてはまた勉強しておきます
2020/07/14(火) 22:12:41.05
あれくらいで不快とか、生きにくそう
2020/07/14(火) 22:13:10.52
>>579
現役に未練はないと言ってたし今年のGCJも出てないみたいだから引退気味なんじゃないかなあ…
2020/07/14(火) 22:33:22.58
>>587
まあそうなんだよね
残念
2020/07/14(火) 22:42:38.82
まだ若いのになんで引退気味なん？
衰えとか感じてんなのかな
2020/07/14(火) 23:59:13.96
https://codeforces.com/blog/entry/62540
りんごさんではないが引退した人のブログ
衰えはあるみたい、当時30半ばだろうか
2020/07/15(水) 00:16:13.15
2色上の奴が無い内定でゲラゲラしてる
2020/07/15(水) 02:12:45.60
参加者も増えた分そろそろ就活に役立たないって事が露見してきた感
2020/07/15(水) 02:52:42.84
就活には初めから役に立たなかっただろ
学生と社会人が、つまりおれたちが力を合わせて盛り上げるんだよ
2020/07/15(水) 03:27:14.83
>>582
ちょうどAtCoderでも宣伝されてる、ICFPコンの2016年の問題は
多倍長有理数が必要な問題だったけど良問と言われてるはず
まあAtCoderで出題される可能性は低いとは思うけどね
2020/07/15(水) 03:51:28.35
>>579
赤になるまではって何？
2020/07/15(水) 04:37:53.93
>>595
https://twitter.com/rng_58/status/918485141718052865?s=21
https://twitter.com/5chan_nel (5ch newer account)
2020/07/15(水) 05:06:31.07
これ突然こんなこと呟かない気がするけどどういう文脈だったんだろう
2020/07/15(水) 06:41:19.26
作問者に対する大量のイチャモンを受けて言ってるんじゃね
599仕様書無しさん
垢版 |
2020/07/15(水) 09:46:29.17
りんごさんとすぬけさんの解説動画はいつ見てもカッコいいな
2020/07/15(水) 09:57:21.71
https://togetter.com/li/1160322
2017-10-12 の付近の呟きみてみたらSRMがクソ回だったらしい
2020/07/15(水) 16:53:08.21
りんごさん→かっこいい
すぬけさん→かわいい
2020/07/15(水) 17:14:20.42
競プロばっかりやってないで研究しろって怒られちまったぜ
2020/07/15(水) 17:18:45.45
当たり前
604仕様書無しさん
垢版 |
2020/07/15(水) 17:40:59.22
競プロは本当にただのネトゲだと思うのがよくて、競プロを使って学習、就職、何かの能力の証明をするって考えは捨てなきゃいけないな…
2020/07/15(水) 18:39:25.14
C++のテンプレートの記述順序をどうすればいいかについて悩んでいます

1. ヘッダファイルの読み込み（#include <bits/stdc++.h>）
2. マクロの定義（rep、all）
3. using namespace std;
4. 型定義（typedef、using）
5. 関数定義（chmax）
6. 定数定義（INF、EPS、MOD）

今は上記の順序で記述しています
順序を変えたほうがいいよ、などあれば教えていただきたいです
（定数定義は関数定義の前にあったほうが自然？）
2020/07/15(水) 18:40:14.40
茶色までならプログラミング練習になるしね
2020/07/15(水) 18:57:18.00
>>604
ネトゲの攻略本を書いて稼げるのいいな
2020/07/15(水) 18:59:12.31
レッドコーダーになったらnoteで商材売るわ
ちな緑コーダー
2020/07/15(水) 22:16:05.63
橙で本書いてる人いたな
2020/07/15(水) 23:15:30.06
>>600
chokudaiが一番愚痴ってて草
粘着質なところ出てるな
2020/07/15(水) 23:55:53.27
>>605
それレートに関係あるの？笑みたいな人多いと思うけど気にする人がいて嬉しい
自分は全く同じ順番ですね、INFとMODはいじることがあるから1番最後が便利だし
気になるならGoogleのコーディング規約とか見てもいいかもしれない
2020/07/16(木) 00:14:48.81
どうせ商材作るならもっとターゲットが広そうな題材にしたほうがいい
2020/07/16(木) 00:47:57.00
頭が悪い人の本が売れるのか楽しみ
2020/07/16(木) 01:52:53.45
これを履修すれば誰でも緑色になれる教科書とかの方が売れそう
2020/07/16(木) 01:58:55.56
>>614
本当にできたら売れるだろうけど無作るのは無理だろうな
同じような事うたってる記事が幾らでもあるけど緑未満は幾らでもいるし
2020/07/16(木) 02:05:23.28
有限集合なんだから幾らでもいるは間違い
2020/07/16(木) 02:16:57.25
比喩表現なんだよなあ…
2020/07/16(木) 02:40:45.60
それ蟻本ちゃうの？
2020/07/16(木) 03:05:10.08
誰でも緑というと揉めるからサルでも緑にしよう
2020/07/16(木) 09:31:34.42
>>568
a と b に分割するコストは a*b で、c と d に分割するコストは c*d だよね？
なんで a*b と c*d じゃなくて a^2+b^2 と c^2+d^2 を比べるの？
俺今めっちゃ変なこと聞いてる？
2020/07/16(木) 09:49:17.21
技術書展で競プロ本書いたらchokudaiさんが宣伝してくれるから無条件で売れるよ
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況