競技プログラミングにハマるプログラマのスレ 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/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さんが宣伝してくれるから無条件で売れるよ
2020/07/16(木) 09:50:19.76
>>605
typedefとusing併用してるならusingに統一しようぜ
2020/07/16(木) 11:33:30.57
>>620
>>394
2020/07/16(木) 11:40:02.99
>>621
宣伝してもらったが全然売れなかったぞどういうことだ
2020/07/16(木) 13:18:49.67
こういうのってどうせ二次関数だからだいたい真ん中か端っこで最大とるよね
626仕様書無しさん
垢版 |
2020/07/16(木) 13:21:56.79
数学得意な人が競プロはじめてすぐ得意になる例はよく聞くけど
競プロ打ち込んだら数学前より得意になりましたって人聞く？
2020/07/16(木) 17:09:27.30
今週ABCないんかー
モチベーションだださがりやー
今月中に入水する計画ガー
2020/07/16(木) 17:28:35.10
ネトゲやってたら数学得意になりましたってそんな話あると思うか？
2020/07/16(木) 17:59:37.31
競プロに必要な数学を先取りしてる中高生なら多々
2020/07/16(木) 18:20:18.29
今の中学生は怖いわ
K近傍法とか知ってるやつもいるみたいだし
2020/07/16(木) 19:00:36.59
>>611
僕も反応してくれる人いないだろうなーと思って質問したので、
反応してくれる人がいて嬉しいです

なるほど、確かにINFやMODは値を書き換えることがあるので一番下が良さそうですね
今のところ、定数を使う関数はありませんし…

・型定義では vector を使っているので、「using namespace std;」<「型定義」
・関数定義や定数定義で型定義を利用しているので、「型定義」<「関数定義、定数定義」
・インクルードやマクロはプリプロセッサが処理するので、最初に書く
・更に bits/stdc++.h よりも自作マクロを優先させたいので、「include」<「マクロ」
・最も書き換え頻度の多いので、定数定義は最後に書く

以上の理由から、>>605の順序が一番良さそうです

>>622
了解です
2020/07/16(木) 19:12:55.27
競プロのおかげでヨビノリの期待値の動画やグラフ理論の動画が理解できるようになったから
数学が得意になったといえる
2020/07/16(木) 19:15:14.57
競プロじゃあんま関係ないがヘッダファイルをたくさんincludeするときトポソ順にやるかその逆順でやるかというのがある
2020/07/16(木) 19:26:39.71
おれ、棋聖よりプログラミングできるからさ…
2020/07/16(木) 20:41:59.79
棋聖に勝てる将棋AIを0から作れるなら認めてやってもいいぞ
2020/07/16(木) 20:45:45.20
ラズパイみたいなのの計算力で藤井くん倒そうみたいなのは丁度よさそうな目標なんだよな
もう勝てるのかは知らない
2020/07/16(木) 21:21:36.70
1からプログラム書いて勝てるなら偉業だから頑張ってくれ
2020/07/16(木) 21:32:46.74
>>633
逆順でするの面白いです
調べてみると、「依存ファイルのインクルードを忘れたのにコンパイルが通ってしまう」
という事態を避けるためらしいですね
競プロでは意識する必要はなさそうです

関係ないですけど、競プロer同士だと「トポソ」の三文字だけで意思疎通できるのが面白いです
競プロする理由が自分でもわからなかったけど、
もしかすると好きな競プロerさんと意思疎通したいとかそういう理由なのかも
あまり「競プロそのもの」をする目的は考えないほうがいいかもしれません
（たとえば就職に役立つとか数学が強くなるとかお金になるとか）
639仕様書無しさん
垢版 |
2020/07/16(木) 21:36:44.90
将棋も金融も保険もアルゴリズム力は関係あるけど、atcoderの算数パズル問題とは遠いっすよ
2020/07/17(金) 00:37:04.90
トポソ＝トポロジカルソートか
競プロerだけど初めて知った
2020/07/17(金) 01:33:53.36
藤井聡太とかものすごい天才だと思うけど日本でしかやってないボードゲームの天才ってどうなんだろうと思ってしまう。touristやりんごさんも同じ。他のことやってればどうだったんだろう。
研究者だったなら人類のフロンティアに貢献できるけど、解ける問題を作って解いてって虚しくならないものなのかな？間接的には大きな影響を与えてるだろうけど。
2020/07/17(金) 01:47:35.38
本人が楽しくてしょうがないんだからそれでいいだろ
他人がとやかく言うことじゃねえ
2020/07/17(金) 02:06:27.95
天才ではないお前の存在はもっと虚しくならない？
2020/07/17(金) 02:16:28.87
国内だけだろうと将棋は稼げるからええわ。競プロは確かに人材の無駄遣い感ある。atcoder社員なんて塾講みたいなもんだしな
2020/07/17(金) 03:11:02.38
競技プログラミングのトップの賞金ってどれぐらいなんだっけ？
2020/07/17(金) 03:51:03.43
競技プログラミングの人口は将棋を超えているのか？
2020/07/17(金) 04:12:34.49
競技プログラミングの世界にもチェスや将棋のレーティングがあるそうですが
プログラミングの勝負ってのうがど素人には全く想像出来ないのですが簡単に言うとどんな感じなんでしょうか？
将棋だとレーティング差１２０は２勝１敗、１９０は３勝１敗くらいの実力差って簡単にわかるけど
2020/07/17(金) 04:29:09.36
スレタイを、読もうね！
2020/07/17(金) 04:42:15.14
>>647
単に一対一じゃなく全体の順位でレートを出してるだけだよ。6問のうちたくさん解いた人が上位。同点なら解いた時間の早い人が勝ち。レートの分布や価値も24のレートと似てる気がするなぁ
2020/07/17(金) 06:52:13.10
>>644
これはある。でもatcoder無くなったら困る
2020/07/17(金) 07:51:36.96
>>647
400差の人が同じコンテストに出続けたら6勝1敗くらいになるようになってるよ
2020/07/17(金) 08:55:48.17
確かにすぬけさん塾の優しい先生感やばいな
653仕様書無しさん
垢版 |
2020/07/17(金) 15:35:25.94
ICFPどうでもいいからコンテストやって
654仕様書無しさん
垢版 |
2020/07/17(金) 17:07:17.91
るびくんさんあーだこーだーに登場するのワロタ
Atcoder的には過激発言や学業崩壊はいいんかw
まあどんなこと話すかむっちゃ楽しみだけど
2020/07/17(金) 17:13:50.67
>>641
アカデミア至上主義だな
競プロで新しい解法や問題を生み出すこと、将棋で新しい戦術を編み出すことにも新規性はあるだろ
逆に、学会における新規性もほとんどは既存手法の組み合わせや小さな変更だからそんなにロマンチックなものではない
2020/07/17(金) 19:23:28.44
>>641
こういう「解ける問題を解いてるだけ」みたいな意見は全然信用できない
難しい問題を作るのは研究と同じくらいかそれ以上に創造的だし、全く簡単な話じゃない
解ける問題を作ったことも研究をしたこともないんじゃないかと思えてしまう
2020/07/17(金) 19:27:13.29
解ける問題といっても大多数の人は解けないし
2020/07/17(金) 19:45:15.37
新規性の有無とか簡単かどうかなんていう話じゃないのに論点をずらしてるのはわざとなのか天然なのか。いずれにせよ一部の人にはなんか効いてるようだ。
2020/07/17(金) 19:49:37.11
スレチ
2020/07/17(金) 20:15:07.40
今週のABCは土曜？日曜？
2020/07/17(金) 20:27:40.23
無い
2020/07/17(金) 20:40:58.84
>>661
ありがとうございます。
楽しみにしていたんですけど、仕方ないですね。
2020/07/17(金) 20:51:37.84
リリアンさんって女性なの？
2020/07/17(金) 20:54:28.69
妖精だよ
2020/07/17(金) 21:02:12.21
現在青です
黄色になるためにAtCoderの過去問を解いていたのですが、少し飽きてきました
気分転換にCodeforcesの過去問を解こうと思うのですが、どの問題から解き始めるのがおすすめでしょうか？
2020/07/17(金) 22:15:45.63
appleman and toastman
あっとこにないので
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況