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

■ このスレッドは過去ログ倉庫に格納されています
2020/06/15(月) 00:23:23.42
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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
※前スレ
競技プログラミングにハマるプログラマのスレ 25
https://medaka.5ch.net/test/read.cgi/prog/1588952913/
2020/06/22(月) 21:42:51.50
>>477
xor分からなくてもコピペでACできる
灰色が大量に解いてるし
2020/06/22(月) 21:45:44.39
本当に強くなりたいと思ってるなら学歴との相関がどうとか嘆いてる間に1問考察したり実装したほうがいい
480仕様書無しさん
垢版 |
2020/06/22(月) 22:27:30.37
atcoderはまだそこまで歴史が長くないから、ずっと停滞してたけど長年やって赤になったみたいな人はまだ出ないでしょ、黄色以上のRatedも少なすぎだし
2020/06/22(月) 23:07:06.74
レートとAGCが安定して5年経ったかな？
2020/06/22(月) 23:30:13.91
Eはコピペじゃなくて未証明提出だろ
2020/06/23(火) 00:04:49.55
どのレート帯でも結論が単純だと思ったより通されがち
484仕様書無しさん
垢版 |
2020/06/23(火) 00:08:25.63
今の方がdifが昔より結構低くなりがちという説が多いのですが、今の青dif下位(この前のFぐらい)が解けるようになるには、昔の何difぐらいを精進するのがオススメですか？
2020/06/23(火) 01:19:04.86
直近のABCから埋めてけばヨロシ
2020/06/23(火) 08:24:10.02
競技数学パズラー・豆コーダー
2020/06/23(火) 12:13:28.24
2020のように、ある文字列の2回以上の繰り返しとして表せる自然数を「2020に似た数」と呼ぶことにします。
Q個のクエリA_iとB_iが入力されたとき、A_iとB_iの間に2020に似た数が何個含まれるか求めなさい。
制約
1≦Q≦1e+5
1≦A_i≦B_i≦1e+5
入力
Q
A_1 B_1
...
A_Q B_Q

これABCのレベルで言ったらどの問題？
2020/06/23(火) 12:18:21.80
あー、「2020に似た数」というのだったらもっと良い性質あったかもな・・・
・連続する4つの素数の平方和で表せる　とか
・連続する10個の偶数の平方和で表せる　とか
2020/06/23(火) 12:21:22.56
累積和とか使う想定なら400くらいありそう
2020に似た数が少ないからクエリごとに全部見たら間に合っちゃうけど
(ちゃんと解析せず通す人が大量発生して灰diffになるパターン)
2020/06/23(火) 12:30:40.23
Cかと思ったのでタイトルをCにしてしまった
https://gist.github.com/surpace/ad36203282aabfa3a0597d03b17b7fc8
2020/06/23(火) 12:32:26.70
これって愚直に1から試すより生成した方が速いんだろうか
2020/06/23(火) 12:39:45.43
ABC-Dくらいだと思うけど今だとかなり解かれそうな気はする
2020/06/23(火) 12:44:15.11
どうでもいいけど文字列の長さの制約ないぞ
2020/06/23(火) 12:44:55.96
AとBが10^18以下だったら緑になるかな
数学色強いしならんかな
2020/06/23(火) 12:45:23.68
1≦A_i≦B_i≦1e+18にしよう
2020/06/23(火) 12:50:55.55
>>495
それだ
2020/06/23(火) 13:08:54.86
てす
2020/06/23(火) 13:14:05.23
問題作ってみたはいいが解けんｗｗｗｗ
生成してみたらしてみたで被るしどうすればｗｗｗｗｗｗｗ
2020/06/23(火) 13:24:18.63
10万までなら答え用意しとけるかな
2020/06/23(火) 14:24:13.90
twitterでまた学歴の話してるよ
2020/06/23(火) 14:26:32.33
　　　　　　　　　　　|
　　　　　　　　　 　 |　　彡⌒ミ
　　　　　　　　　　　＼ (´･ω･`)　
　　　　　　　　　　　　　(|　　　|)::::
　　　　　　　　　　　　 　(γ　/:::::::
　　　　　　　　　　　　　　 し ＼:::
　　　　　　　　　　　　　　　　　 ＼
2020/06/23(火) 15:18:47.66
手応えがあって数学力関係ない問題でも作ろうぜ
2020/06/23(火) 15:19:44.58
数学から逃げるな
2020/06/23(火) 15:22:22.24
コドフォの問題はABC前半のやるだけではなく、
少し考える作業が発生するので良い気がする。
単純に英語だからそう感じるだけかもしれないが。
2020/06/23(火) 15:43:53.59
こどふぉの前半にありがちなこと
非自明な場合分け
何らかの操作をする問題で10^9回の操作が与えられるが実際影響するのは10^5回以下
構築
複雑に見えるが貪欲でいいやつ
2020/06/23(火) 15:57:24.48
競プロが実務に役立たないんじゃない
実務が競プロに役立たないんだ
2020/06/23(火) 16:20:50.65
大体の目安を教えて欲しいんだけど、E問題くらいまで埋めれば青いく？それとも水くらい？
2020/06/23(火) 16:32:00.01
速度によるが水上位くらいじゃね
2020/06/23(火) 16:34:03.43
古いABCまでを全部埋めれば青いくだろ
2020/06/23(火) 20:04:27.31
古いABCもって、ARCの分も埋めるってこと？
2020/06/23(火) 20:39:37.83
ARCはARCじゃんなにいってだ
2020/06/23(火) 20:57:19.72
併設ARCのEFまで埋めたら黄色くらいは行けそう
2020/06/23(火) 21:01:25.21
高校数学のテキスト
https://www.collegium.or.jp/~kutomi/_pdf/ko/math1.pdf

毎日3時間勉強したら1週間でできるかもしれない
2020/06/23(火) 21:02:21.61
・・・いや、1ヶ月はいるかもしれない？
2020/06/24(水) 01:02:46.57
できない人って基本落ちこぼれで土台ができてないんだから
小学生の基礎や九九からやり直すので
1年間毎日6時間ぐらい真面目に勉強しないと競プロ数学に特化した脳力つかないよ。

出来る人はできて当然だから毎日3時間程度で一ヶ月とか言っているけど
できない人から見たらどれだけ高所から言ってんだって恨み買うだけだよ。
516仕様書無しさん
垢版 |
2020/06/24(水) 01:30:44.81
>>513
高校数学Iね。

高校数学は
I・A
II・B
III・C
まである
2020/06/24(水) 01:50:07.85
理系学生は高校三年間＋受験勉強＋大学で1000時間は数学に費やしてるから
そう簡単に挽回できないよ
2020/06/24(水) 02:18:44.73
かなりの割合を占める微積とかとりあえずは要らんからそこまでではない
519仕様書無しさん
垢版 |
2020/06/24(水) 03:01:49.24
微積を使わないアルゴリズム人材・・・
2020/06/24(水) 07:13:22.81
×　微積を使わないアルゴリズム人材・・・
〇　微積を使えないアルゴリズム人材・・・
2020/06/24(水) 09:26:48.12
数値微分のニュートン法の収束速くてすごいのにね。問題に出せなさそう
AOJにはあるのかなあ
2020/06/24(水) 10:35:16.89
atcoderじゃないけどニュートン法が想定解だった問題知ってるよ
数値積分も対象によっては余裕で15桁合うし、FFTよりよっぽど安全に問題作れそう
523仕様書無しさん
垢版 |
2020/06/24(水) 10:53:44.73
newtons methodは数学単体やってるだけだとその有用性よーわからんけど
ニューメリコウな問題プログラムで解くときとかたまに物凄い収束の速さ見せるよな
しかもその単純さからマルチバルでもかなり綺麗なフォームに帰着してちょい興奮するよね(´・ω・`)
2020/06/24(水) 14:27:50.94
AtCoderは数値計算みたいな知識ゲーはまず出さないだろうな
その結果パズルコンテストになるわけだが
2020/06/24(水) 16:14:09.64
AI人材ならニュートン法くらい知ってないとね。Tensor flowの中やらで使っとるで
2020/06/24(水) 18:04:45.97
また論点のすり替えして
解説の不備の正当化しようとしてるな
2020/06/24(水) 18:55:44.64
AtCoderの教育コース、数年前から作りたいとか言ってるけど
一向に作ってる気配ないよな
ベンチャーなんだから、もう少し多めに働いてもいいんでない?
2020/06/24(水) 18:58:42.76
ブラックユーザーかな？
2020/06/24(水) 19:09:24.30
レートが低い人は公式解説を望んでるって伝わってるようだから、何かするんじゃないかい?
2020/06/24(水) 19:10:18.27
教育ならAOJとleetcodeがいいな
2020/06/24(水) 19:11:34.62
アリ本のatcoder版も待たれてると思う
2020/06/24(水) 19:46:15.95
蟻本のatcoder版って、例題のGCJとかPOJをatcoderの問題に置き換えるってこと？
そんなもんの為に改訂するとか、アホの考えることはよーわからん
2020/06/24(水) 20:05:27.32
今のAtCoderで戦うには、蟻本の知識じゃ到底足りない
赤コーダーの誰か、蟻本2を出版してくれ
2020/06/24(水) 20:11:29.08
蟻本Atcoderの問題にして、Pythonのコードも書いてくれんかな
頼むよつよい人たち
2020/06/24(水) 20:12:11.52
>>533
言うてもあの本の中身理解してたら黄色はいけるだろ？
2020/06/24(水) 20:20:32.88
蟻本に書いてなくて赤になるために必要と思われる知識って例えばなに？
2020/06/24(水) 21:14:33.55
>>536
これな
しかもそれがわかってるんだったら自分で勉強すればいいし
2020/06/24(水) 21:15:03.08
O(3^N)系DPとか高速ゼータ変換とか
2020/06/24(水) 21:44:28.51
beats,ntt,mo,binary trie,hld, monotone minimaとか
2020/06/24(水) 21:47:17.31
赤レベルだと個人差ありすぎて"必要な知識"はなさそう
2020/06/24(水) 21:53:42.73
monotone minima ほとんど見たことないんだけどどこで出てるん
2020/06/24(水) 22:00:48.98
AtCoder赤の話ならNTTやらbeatsやら使う機会ほぼないでしょ
ARCAGCによく出てくるDPと構築のが大事
蟻本には桁DPとかも載ってないんだよね
2020/06/24(水) 22:04:53.88
NTT は AtCoder でも割と出てる
2020/06/24(水) 22:05:32.83
まだ100問ぐらいしか埋めてないけど、さすがにコドフォとかと合わせて
数千問解く気になれない、重要テクを本にまとめてくれると助かる
2020/06/24(水) 22:07:07.02
>>543
え、うそ
Ratedで出たことあるなら問題教えてくれると助かる
2020/06/24(水) 22:10:51.87
AtCoder女装勢多すぎない？
しょっちゅうRTで画像流れてきてキツい
2020/06/24(水) 22:13:02.58
>>545
Ratedの話か、すまん
自分が出た、解いた範囲でNTT要求するものが無いのは確か
2020/06/24(水) 22:15:24.34
僕は数学パズラー 豆コーダー
数え上げるし 構築するよ?(いつ、どこで使うんですか、それ?)

僕は数学パズラー 豆コーダー
Xorには詳しいよ?(いつ、どこで使うんですか、それ?)

こんなに賢い僕だけど(競数パ専門知識があるだけでは?)
役に立たないとか言われると ガチでキレるよ?(IPA資格より更に現実離れしてますよ?)
2020/06/24(水) 22:16:33.63
>>547
>>543とは別人？(英字と日本語の間にスペース入れてないから気になった)
2020/06/24(水) 22:17:17.36
ネトゲが役に立つとかいう妄想を捨てろ
2020/06/24(水) 22:18:16.11
>>549
同一人物です
慌ててレス返したらこうなった
2020/06/24(水) 22:18:52.50
って書いたけども証明のしようがないな、まあ気にすることでもないが
2020/06/24(水) 22:23:08.11
プログラム勉強しようと思って始めてスレ見に来たら会話が異次元過ぎた
2020/06/24(水) 22:27:37.10
最近「数学パズル」とかいう独特の語法のアンチ目立つな
同一人物が暴れてるだけ？
2020/06/24(水) 22:29:52.89
スルースキルがないやつが多すぎる
2020/06/24(水) 22:30:21.80
NTTくらいは普通に出てるんだよなあ
https://atcoder.jp/contests/agc005/tasks/agc005_f
https://atcoder.jp/contests/agc019/tasks/agc019_e
2020/06/24(水) 22:36:43.83
NTTなんてトップコーダーでも出るレベル
2020/06/24(水) 22:37:41.31
>>554
アンチは語彙の無いヒキニートだから
妄想を繰り返し書きまくる
2020/06/24(水) 22:39:40.54
>>556
問題の意味がわからない
2020/06/24(水) 22:50:07.67
緑以下勢と青以上勢で話題が隔絶してる感じ
仕方ないけど
2020/06/24(水) 22:52:34.60
なんか橙以上?赤以上?がいるっぽくてびっくりしてる
2020/06/24(水) 23:54:48.63
>>556
それぞれ銀diffと金diffだし、赤になるために必要かと言われたらかなり怪しいだろ
せめて赤diff以下で持ってきてくれ
2020/06/24(水) 23:55:44.35
両方銀だったわすまん
2020/06/25(木) 00:14:35.23
本当に出題されるトピックだけを勉強して上手くいく、ましてや赤に到達するとかあり得ないから
2020/06/25(木) 00:41:33.24
楽しい受験対策みたいなもんだな
2020/06/25(木) 00:45:29.84
一度も銀パフォ出さずに赤になった人おるんか？
2020/06/25(木) 00:50:51.08
計算問題ならdc最強説ある
2020/06/25(木) 01:14:51.69
>>566
銀パフォ取れなくても赤になれるなんて言ってないぞ
毎回銀diff解けなきゃ赤になれないわけじゃないよね？って言ってる
2020/06/25(木) 01:45:50.82
ナンプレ好きな人にそれ役に立たないよね？っていう人は少ないのに競プロになると途端に役に立たない連呼が湧くのは何なんだ
2020/06/25(木) 01:48:37.14
AtCoderが就活でアピールできるよ！とか言ってるからだろ
2020/06/25(木) 02:41:36.19
プログラマーの能力の一つにアルゴリズム力があって、AtCoderはそれがメインなわけだが
ほかの能力にはどういうのがあるだろうか、とりあえず思いついたのを挙げてみる
・書くスピード・・・・開発速度に影響するかも？
・コメント力・・・・・わかりやすいのを書ける
・構造化能力・・・・・読みやすいソースコードを書ける　
・リーディング力・・・コードから何をしているか理解できる
・テスト力・・・・・・異常系を想定したり、コーナーケースを書いたりできる
・設計力・・・・・・・要件を満たすシステムを設計できる

AtCoderはアルゴリズム力と書くスピードが試される
Codeforcesはそれに加えテスト力
Paizaのスキルチェックはアルゴリズム力少々と適宜設計力
572仕様書無しさん
垢版 |
2020/06/25(木) 02:50:24.33
確率とか統計っぽい問題もあるけど、数え上げ問題に絡みがちて、データサイエンスに必要な素養とはあまりにかけはなれてるみたいな・・・
2020/06/25(木) 03:00:46.31
>>571
テキトーすぎる
2020/06/25(木) 03:01:00.08
すぬけくんは抜け毛に悩んでいます。そこで、抜け毛の原因を調査することにしました。
N日分の調査データH_i（抜けた毛の本数）とその日のM種類のある統計データD_ijが与えられます。
どの統計データが抜け毛の本数と最も関連しているか見つけなさい。

入力：
N M
H_1 D_11 D_12 ... D_1M
...
H_N D_N1 D_N2 ... D_NM

出力：
j

みたいな感じ？
2020/06/25(木) 03:14:37.98
　　　〆⌒ ヽ彡　　　　　
　　　(´・ω・`)　
2020/06/25(木) 04:51:44.57
>>574
やめろおおおおおおおお
2020/06/25(木) 08:22:41.61
>>575
実名出しちゃいかん
しかし、時々付けているヘアピンを見て、
「おや、これは…?」と思うこともあることは否定しない
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況