競技プログラミングにハマるプログラマのスレ 27
■ このスレッドは過去ログ倉庫に格納されています
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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/ >>541
x1個の○、…、x5個の○から一つずつ●に置き換える方法がx1*...*x5通りということではなく？（馬鹿にしてるわけではないです） 542の言い換えは、普通は知らないと浮かばないレベルの発想だと思います。高度競プロ人材はこういうの得意ですよね。 そこは解説pdfにちゃんと書いてあるから（分割を行った後、〜対応しています？）大丈夫かと思っちゃった 理解できた気がします
解説放送の方針を勘違いしていました
「x1 * x2 * x3 * x4 * x5 = A を満たす A はいくつあるか」を数え上げるわけではなく、
たとえば (x1, x2, x3, x4, x5) = (1, 3, 1, 1, 2) のとき、
(1, 3, 1, 1, 2) が 6 回数え上げられるので自ずと A に一致する、ということだったのですね
難しいです
自力で思いつくのは大変そうです…
回答ありがとうございました >>505
合同式について今日色々調べていたのですが、使えないケースとかありますか？
例えば13mod10は2^3+2^1+2^0に変換できますが、各項を繰り返し二乗法で計算すると
8+2+1＝13となってしまい、期待した答え（余り3）が得られないです >>549
すみません多分私がちゃんと理解できてないのですが…
適当な値が思いつかず13を例にしましたが、64bitに入らないような大きい数の場合は
繰り返し二乗法だけでは最後までは計算できないという事なのでしょうか？
（元々大きい数に対してmodを取りたくて、繰り返し二乗法で計算する(>>471)とコメントを頂いたので） なんか玉石混交過ぎるねここに投げられる質問
>>391とかは結局まだ証明ないし、>>536とかはやるだけ・読むだけっていう 非常に分かり辛い質問になってしまいました…
繰り返し二乗法で計算したXmod10の結果Yが10以上の場合、最終的な余りをどう求めるべきでしょうか？
Y=13なら13%10で3が求まりますが、Yが64bitに入らない数値だとどうすればよいのでしょうか 繰り返し二乗法で計算した値がmodより大きくなるってどういうこと >>552
加算や乗算をするたびにmodを取るようにすれば、
modが10^9+7とかであれば64ビットを超えることはないです 動的計画法と線形計画法はどのような共通点がありますか？ 536がやるだけって緩めに見て上位200.人ぐらい？ >>553>>555
有難うございます（何度もレスしてすみません）
ここで言う「modを取る」とは繰り返し二乗法を使わないで、という事でしょうか？
>>547で挙げた13mod10の場合、2^3+2^1+2^0のどの項も10未満なのでmod取って和が13になってしまいます >>559
modを取った和の13のmodをさらに取ればいい >>560
「13のmodを更に取る」というのは13mod10を計算する、で合っていますか？そうするとまた13になってしまいます(>>547の通り)
（何か私が根本的に勘違いしているのかもしれません）
または、modの計算を1回目は繰り返し二乗法で、1回で答えが出なければ普通に計算（A%B）する、
というルールでやるという意味でしょうか。 1010100....01_(2) みたいな数のmodはすぐに計算できないけど、各桁を繰り返し2乗法でmod取りながら求めた値はmod以下だよね
それを足していく時もmodの2倍より大きくならないから、毎回あまりを取りながら足したらいいよ 例えば、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
と求められる 大きな数のあまりを取るのは難しいけど、小さい数のあまりは％演算子とかで取れるから、それを忘れてるんじゃないかな てか13って2^3+2^2+2^0じゃん
今気づいた >>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、よって示された え、540、542の言い換え天才すぎない？この言い換え典型なの？
典型じゃないとしたら自分には無理だから、形式的冪級数履修するか… >>562>>564
ご丁寧に有難うございます！理解できた気がしました
示して頂いたこの部分（=14+2+1=4+2+1）が「余りを取りながら足す」という事だったんですね
コメントして頂いた方々有難うございました（かなりスレ汚してしまいすみません）
>>566
小さい数が％で計算できるのは分かっているのですが、
その「大きな数」と「小さな数」の判断（どこからが「大きな数」か）をどうすればいいかで悩んでいました
（ここはまだ理解できてないので今後自分で調べようと思います） AtCoder上でパッと自分が思い出せるだけで2問はあるからど典型じゃないかなあ はー天才すぎる無理やろこんなんからの意外とすぐまた出会うってのあるあるだからな すぬけさんすき
他のatcoderのひとだいたいすきじゃない りんごさんとwataさんの外から見て嫌いになる要素何？ 分数の演算を行う構造体を作ろうと思うのですが、使うことはあるでしょうか？ 赤になるまでは〜のツイートは思うところある人いそう
rngさんはmaroonさんにadmin完全に引き継いでもらったあとcontestantで無双してほしいな 分数を表す構造体、足し合わせる分数が多いと通分したときにすぐに分母がオーバーフローしそうで怖い 今の時代に多倍長に対応した分数の構造体を使う問題が出るとは思えない
そんな問題を作る橙以上の人がいるとは思えないし、
もし作ったとしても絶対悪問と言われる
やっぱり分数の構造体（特に多倍長に対応したもの）を作る必要性が見い出せない… ちょくだいは最近就活就活言い過ぎで不快なんだよな、それがないとお金入ってこないのはわかるけど
まわり見てても就活の結果とレートそこまで相関ないし boost/multiprecisionの基本的な使い方押さえときゃよくね 分数の構造体の件、作っても使わなそうですし、
作る過程で得られるものが特になさそうなので作らないことにします
レスしてくださった皆様ありがとうございました
boost/setprecisionの基本的な使い方についてはまた勉強しておきます >>579
現役に未練はないと言ってたし今年のGCJも出てないみたいだから引退気味なんじゃないかなあ… まだ若いのになんで引退気味なん？
衰えとか感じてんなのかな https://codeforces.com/blog/entry/62540
りんごさんではないが引退した人のブログ
衰えはあるみたい、当時30半ばだろうか 参加者も増えた分そろそろ就活に役立たないって事が露見してきた感 就活には初めから役に立たなかっただろ
学生と社会人が、つまりおれたちが力を合わせて盛り上げるんだよ >>582
ちょうどAtCoderでも宣伝されてる、ICFPコンの2016年の問題は
多倍長有理数が必要な問題だったけど良問と言われてるはず
まあAtCoderで出題される可能性は低いとは思うけどね これ突然こんなこと呟かない気がするけどどういう文脈だったんだろう 作問者に対する大量のイチャモンを受けて言ってるんじゃね りんごさんとすぬけさんの解説動画はいつ見てもカッコいいな https://togetter.com/li/1160322
2017-10-12 の付近の呟きみてみたらSRMがクソ回だったらしい 競プロばっかりやってないで研究しろって怒られちまったぜ 競プロは本当にただのネトゲだと思うのがよくて、競プロを使って学習、就職、何かの能力の証明をするって考えは捨てなきゃいけないな… C++のテンプレートの記述順序をどうすればいいかについて悩んでいます
1. ヘッダファイルの読み込み（#include <bits/stdc++.h>）
2. マクロの定義（rep、all）
3. using namespace std;
4. 型定義（typedef、using）
5. 関数定義（chmax）
6. 定数定義（INF、EPS、MOD）
今は上記の順序で記述しています
順序を変えたほうがいいよ、などあれば教えていただきたいです
（定数定義は関数定義の前にあったほうが自然？） レッドコーダーになったらnoteで商材売るわ
ちな緑コーダー >>600
chokudaiが一番愚痴ってて草
粘着質なところ出てるな >>605
それレートに関係あるの？笑みたいな人多いと思うけど気にする人がいて嬉しい
自分は全く同じ順番ですね、INFとMODはいじることがあるから1番最後が便利だし
気になるならGoogleのコーディング規約とか見てもいいかもしれない どうせ商材作るならもっとターゲットが広そうな題材にしたほうがいい これを履修すれば誰でも緑色になれる教科書とかの方が売れそう >>614
本当にできたら売れるだろうけど無作るのは無理だろうな
同じような事うたってる記事が幾らでもあるけど緑未満は幾らでもいるし >>568
a と b に分割するコストは a*b で、c と d に分割するコストは c*d だよね？
なんで a*b と c*d じゃなくて a^2+b^2 と c^2+d^2 を比べるの？
俺今めっちゃ変なこと聞いてる？ 技術書展で競プロ本書いたらchokudaiさんが宣伝してくれるから無条件で売れるよ >>605
typedefとusing併用してるならusingに統一しようぜ >>621
宣伝してもらったが全然売れなかったぞどういうことだ こういうのってどうせ二次関数だからだいたい真ん中か端っこで最大とるよね 数学得意な人が競プロはじめてすぐ得意になる例はよく聞くけど
競プロ打ち込んだら数学前より得意になりましたって人聞く？ 今週ABCないんかー
モチベーションだださがりやー
今月中に入水する計画ガー ネトゲやってたら数学得意になりましたってそんな話あると思うか？ 今の中学生は怖いわ
K近傍法とか知ってるやつもいるみたいだし >>611
僕も反応してくれる人いないだろうなーと思って質問したので、
反応してくれる人がいて嬉しいです
なるほど、確かにINFやMODは値を書き換えることがあるので一番下が良さそうですね
今のところ、定数を使う関数はありませんし…
・型定義では vector を使っているので、「using namespace std;」<「型定義」
・関数定義や定数定義で型定義を利用しているので、「型定義」<「関数定義、定数定義」
・インクルードやマクロはプリプロセッサが処理するので、最初に書く
・更に bits/stdc++.h よりも自作マクロを優先させたいので、「include」<「マクロ」
・最も書き換え頻度の多いので、定数定義は最後に書く
以上の理由から、>>605の順序が一番良さそうです
>>622
了解です 競プロのおかげでヨビノリの期待値の動画やグラフ理論の動画が理解できるようになったから
数学が得意になったといえる 競プロじゃあんま関係ないがヘッダファイルをたくさんincludeするときトポソ順にやるかその逆順でやるかというのがある 棋聖に勝てる将棋AIを0から作れるなら認めてやってもいいぞ ラズパイみたいなのの計算力で藤井くん倒そうみたいなのは丁度よさそうな目標なんだよな
もう勝てるのかは知らない 1からプログラム書いて勝てるなら偉業だから頑張ってくれ >>633
逆順でするの面白いです
調べてみると、「依存ファイルのインクルードを忘れたのにコンパイルが通ってしまう」
という事態を避けるためらしいですね
競プロでは意識する必要はなさそうです
関係ないですけど、競プロer同士だと「トポソ」の三文字だけで意思疎通できるのが面白いです
競プロする理由が自分でもわからなかったけど、
もしかすると好きな競プロerさんと意思疎通したいとかそういう理由なのかも
あまり「競プロそのもの」をする目的は考えないほうがいいかもしれません
（たとえば就職に役立つとか数学が強くなるとかお金になるとか） 将棋も金融も保険もアルゴリズム力は関係あるけど、atcoderの算数パズル問題とは遠いっすよ トポソ＝トポロジカルソートか
競プロerだけど初めて知った 藤井聡太とかものすごい天才だと思うけど日本でしかやってないボードゲームの天才ってどうなんだろうと思ってしまう。touristやりんごさんも同じ。他のことやってればどうだったんだろう。
研究者だったなら人類のフロンティアに貢献できるけど、解ける問題を作って解いてって虚しくならないものなのかな？間接的には大きな影響を与えてるだろうけど。 ■ このスレッドは過去ログ倉庫に格納されています
