競技プログラミングにハマるプログラマのスレ 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/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
あっとこにないので
2020/07/17(金) 22:16:47.89
え、飽きたらやめるけど何の強制力？
2020/07/17(金) 22:17:48.06
AtCoderの過去問を解くのに飽きただけで競技プログラミングに飽きたとは言ってないでしょおじいちゃん
2020/07/17(金) 22:30:35.80
読解力灰色コーダー定期的に出るな
2020/07/17(金) 23:43:32.02
灰色に失礼だろ
2020/07/17(金) 23:57:18.41
読解力Atcoder退会
2020/07/18(土) 02:58:49.50
#BlackLivesMatter
2020/07/18(土) 05:28:47.61
#GrayLivesMatter
2020/07/18(土) 08:54:33.20
寒色の人権←？
2020/07/18(土) 09:49:14.80
>>605

かけ算の順序問題とか好きそう

笑
2020/07/18(土) 09:57:35.51
確かに笑
677仕様書無しさん
垢版 |
2020/07/18(土) 10:40:06.38
就職のためだけ考えて競プロやるなら何色目標がおすすめですか。
2020/07/18(土) 10:49:41.37
青
TOEIC600みたいなもんで、緑とか水色ですって言ったら「ブームに当てられて一応やってみた人」みたいに映ると思う
2020/07/18(土) 11:04:59.52
ICPCに出ようと思って一生懸命やってる人でも青から黄くらいで止まる人がたくさんいるわけで
ほぼ努力を必要とせずに水とか青になれる人はいいけど
普通の人が就活のために競プロに参入するのはおすすめしない
680仕様書無しさん
垢版 |
2020/07/18(土) 11:38:20.80
まじですか、ちょっとやってみて精進しなきゃ伸びなそうだったらやめます
2020/07/18(土) 11:48:08.71
数学が得意な人に聞きたいのですが、
x / x = 1 という式は、x が 0 のときでも成り立つものでしょうか？

https://www.slideshare.net/chokudai/arc033
こちらのスライドショーにある以下の式が疑問の発祥元です
Qi(x) = (x-0)*(x-1)*...*(x-N)/(x-i)（ただし i=0~N）
2020/07/18(土) 11:56:11.02
数学苦手だけど0で割っちゃいけないと思う
2020/07/18(土) 11:56:32.56
>>667
この読解力のなさ競プロ純粋培養感あってええな
2020/07/18(土) 11:59:25.74
>>677
アルゴリズム重要視されない分野なら茶か緑で十分
そっち系目指すなら最低黄色じゃない？橙で失敗する人もいるけど
2020/07/18(土) 12:08:59.60
重視されない会社なら自分で目標立てて達成していく努力過程が評価になるから色は関係ないな
茶色は鼻で笑われそうだけど
2020/07/18(土) 12:09:51.07
>>682
ですよねー
リンク先のスライドに「ただしx/x=1はx=0のときでも成立するものとする」という文言が欲しかったです
2020/07/18(土) 12:10:13.82
>>681
スライド見てないけどx≠iなんじゃないの？
2020/07/18(土) 12:18:52.87
>>687
いえ、x=iもあり得ます

正しくは次のように書くべきだと思います（kmjpさんもこのように書いている）
Qi(x) = (x-0)*(x-1)*...(x-(i-1))*(x-(i+1))*...*(x-N)

次のように書いてしまうと、先ほどの注意書きが必要になると思います
Qi(x) = (x-0)*(x-1)*...*(x-N)/(x-i)
2020/07/18(土) 12:34:05.50
https://codeforces.com/contest/461/problem/A
Appleman and Toastman みたいな問題、解けることには解けるけど、
答えが最大値であることの証明ができない…
こういう貪欲を証明する力ってどのようにすれば身に付きますかね？
類題の「ハフマン符号が最適符号であることの証明」を理解すればいいのかな、とか思ったりしています
2020/07/18(土) 12:55:08.88
>>688
多項式として約分したものを考えて、代入とかはその後にやるという暗黙の約束のもとにそう書いてるだけだよ。先に代入すると分母がゼロになってそれはダメ。
2020/07/18(土) 12:56:44.37
>>686
そんな注釈は正しくないので書いちゃダメw
2020/07/18(土) 13:01:00.39
>>690
なるほど、理解しました
ありがとうございます
2020/07/18(土) 13:05:58.84
どうせ解析接続で値は一意
694仕様書無しさん
垢版 |
2020/07/18(土) 13:11:37.96
>>677
算数パズルコンテストなのでatcoderだと茶色上、PASTだと上級でアルゴリズム人材です
695仕様書無しさん
垢版 |
2020/07/18(土) 14:01:46.90
PAST上級なら水色余裕じゃね
2020/07/18(土) 14:08:01.71
>>690のような最小限の文章量で的確に間違いを指摘できる人が黄や橙で、
>>693のようなほとんどの人が理解できない単語を突然出す人は水色以下であって欲しいと思う今日この頃
まあ現実はそう単純じゃないんだろうけど…
2020/07/18(土) 14:32:26.29
説明能力と競技プログラミング力には多少相関はあるかもしれないけどそれくらいだからな

ちな解析接続はざっくり言うとx/x=1みたいに定義できるところでの値が等しい関数を同一視する話
1+2+3+…=-1/12みたいなネタと同じ話だな
2020/07/18(土) 14:34:45.20
今回の場合だと除去可能特異点って言ったほうが数学的に正しいけど、そういう話じゃあないんだよな
699仕様書無しさん
垢版 |
2020/07/18(土) 21:26:09.17
初回でパフォーマンス1000ぐらいだったので少し頑張れば緑はいけると思うのでとりあえずそこまでは頑張ります。
ありがとうございます。
2020/07/18(土) 21:26:55.57
単純に説明能力そのものを認めればいいのに
ratism ここに極まれり
2020/07/18(土) 22:34:52.51
初回で緑パフォ出るなら少しやれば青まではいきそう
2020/07/18(土) 22:59:53.73
レート予想するやつ1年後も同じ色でわろた
2020/07/18(土) 23:15:55.37
そんなのあるんだ
ゴリラの人とか3年後も青と水反復してそう
2020/07/18(土) 23:28:57.18
おっさんがウホウホしてるの草生える
705仕様書無しさん
垢版 |
2020/07/19(日) 00:00:36.15
言うほど草生えるか？
小学生erがウホウホしてたら確かにおもしろいが
2020/07/19(日) 00:06:39.43
読解力灰色コーダー定期
2020/07/19(日) 00:14:48.76
同じことしか言えないやつも言語能力大概だな
2020/07/19(日) 00:21:29.48
ウホウホ is 何
please 説明 without ウホウホ
2020/07/19(日) 00:25:11.09
競プロ界隈のおっさん構文だから許して
2020/07/19(日) 00:32:13.95
ゴリラの人頑張ってて尊敬してる。あの人ぐらいよくわかってたらプログラマとして仕事をやっていけるはず。
2020/07/19(日) 00:39:22.11
努力してるとは思うが、10年後にああいう風になりたいとは思わない
2020/07/19(日) 00:42:53.93
好きな仕事してんるだからいいんじゃないの、知らんけど
2020/07/19(日) 00:55:51.84
競プロ就職した人はいつまでプログラミングするんだろうな
マネージャーとか転職とかするんか気になる
2020/07/19(日) 00:57:39.33
赤未満の個人の話は止めようね
2020/07/19(日) 01:01:19.83
教育コンテンツ書いたり、人事でもやるんじゃない？
2020/07/19(日) 01:25:59.12
本書いてもこんなもんなのか…
https://anond.hatelabo.jp/20200716012131
2020/07/19(日) 01:30:36.45
放送出たりキャス頻繁になってるのはこういうことか
大変だな
2020/07/19(日) 01:32:49.24
時間ある学生がいっぱい入ってくる中で社会人が仕事しながら青を維持してたらめちゃくちゃすごくない？ゴリラの人すごいと思う。中高生で黄色とか大学生で学業捨てて橙になれたとかはまあ才能があるとして、そうじゃなくて、ちゃんと仕事しながら青維持だよ？仕事と別にコツコツ頑張ってないとできないことだと思う。マジでえらい。追いつきたい。
2020/07/19(日) 01:41:44.96
おっさん発狂してて草
2020/07/19(日) 02:36:03.19
〜しながらとか他人がわざわざ言い訳をつけるのはかえって失礼ではありませんか？
2020/07/19(日) 03:05:35.70
最近雑談系の板のノリしか知らなそうなキッズ増えたな
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況