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

■ このスレッドは過去ログ倉庫に格納されています
2020/10/12(月) 04:03:29.63
競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ

・次スレは>>950

# オンラインジャッジ・コンテストサイト
## 日本語
AtCoder https://atcoder.jp/
yukicoder https://yukicoder.me/
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>>984

Codeforces http://codeforces.com/
CS Academy https://csacademy.com/
Project Euler https://projecteuler.net/

※前スレ
競技プログラミングにハマるプログラマのスレ　31
https://medaka.5ch.net/test/read.cgi/prog/1600743367/
2020/10/26(月) 12:23:57.69
参加者半分以上東大京大じゃねえの
参加者の学歴の統計出たら面白いのにね
2020/10/26(月) 12:34:13.88
IQになんの意味もないと思っているけど競プロ参加者はIQ高そう
2020/10/26(月) 12:38:38.81
sabaさんって人が大学別のデータまとめてるけど、それ使って自分が調べた記憶では、青以上(の所属出してる大学生・院生)でも東大がせいぜい30〜40%とかだった気がする
全参加者の中央値はいいとこ地方旧帝・筑波あたりじゃないの
2020/10/26(月) 12:39:47.13
珍しい大学だなと思ってもツイ垢をよく見ると医学生だったりするので…
2020/10/26(月) 13:03:52.60
きょうぷろ界の東大こと会津大もあるからな
2020/10/26(月) 13:10:42.25
東大の平均緑とかだっけ
2020/10/26(月) 16:44:35.34
>>533
GP30稼ぎたいんじゃないの
2020/10/26(月) 19:39:48.84
汎用性が高くて使いやすいアルゴリズムとデータ構造
UnionFind（茶）
セグメント木（緑）
遅延セグメント木（水）
最大流（青）
2020/10/26(月) 19:40:59.50
灰: array, set, dict
2020/10/26(月) 19:47:15.15
茶：繰り返し二乗法、二分探索、最短距離（BFS・ダイクストラ）
緑：組合せ、逆元、最短距離（ベルマンフォード）
もだろうな
2020/10/26(月) 20:01:01.79
AtCoder灰色にできること

基本：入出力、繰り返し、条件分岐、四則演算、ライブラリ関数の利用
数学：整数の割り算（切り上げ）、約数の列挙、modを取る
アルゴリズム：全探索、状態を持つ繰り返し
2020/10/26(月) 20:21:39.23
その辺の知識は以前より1色下がってそう
2020/10/26(月) 20:32:14.99
灰色は意欲だけだよ
2020/10/26(月) 20:41:40.41
本当に意欲があったらいろんなアルゴリズムをささっと学んで緑まで行くだろ
2020/10/26(月) 20:42:18.05
緑は言いすぎたな　今の情勢だと茶までは行く
2020/10/26(月) 20:49:25.37
裾野を広げる意味で茶の下にもう一色欲しいけど茶と灰の間に入りそうな色が思いつかない
2020/10/26(月) 21:15:00.76
そのうち茶でもACLのアルゴリズムを使いこなせることが必須になるかもー
2020/10/26(月) 21:19:28.25
もう全部色温度でいいよ　レート×4+2000度くらいで
585仕様書無しさん
垢版 |
2020/10/26(月) 22:07:21.19
亜麻色
栗色
2020/10/26(月) 22:56:43.14
データ構造はなんやかんや工夫すれば連想配列、ハッシュ、unionfind、セグ木、優先度付きキューあたりで青diffまで戦える印象ある
2020/10/26(月) 23:08:13.52
>>576
ダイクストラも逆元もよくわからんけど緑なれたわ
ベルマンフォードに至っては聞いた事もない
2020/10/26(月) 23:09:24.25
素集合データ構造、LinkCutTree使うか
2020/10/26(月) 23:11:47.18
ベルマンフォード使う問題ってABCでは最近出てない気がする
2020/10/26(月) 23:19:59.54
組み合わせで逆元は使ってるはずー
ってもこれはコピペでいけるしな
2020/10/26(月) 23:24:35.95
>>566
これは思う
精進とか言ってるけど単なるガリ勉だしな
2020/10/27(火) 00:33:35.83
優先度付きキューって使ったことがない気がする？multisetだとまずい場面ってある？
2020/10/27(火) 01:04:35.69
multiset(setもだけど)は必然的に全要素の順番を保持することになるわけだから、「最大値『だけ』がわかれば良い」って状況では計算量的に優先度付きキューの方が良いんちゃうかな

multisetだとまずい具体的な状況はわからんけど
594仕様書無しさん
垢版 |
2020/10/27(火) 01:39:31.07
c++のmultisetはm.erase(5)とかやると5が全部消えてしまうので、イテレータでどうのこうのやるのとかpairで管理するのとかが面倒な時はプライオリティキュー使った方が楽だったりする
595仕様書無しさん
垢版 |
2020/10/27(火) 04:53:42.99
Pythonだとmultisetがないから優先度付きキューは有用だと思う
setは有るがC++のsetとは別物(順序を記憶しない)

一応BITで代用できるが、座標圧縮が面倒なときがある
2020/10/27(火) 06:40:53.36
multisetはpriority_queueの上位互換
dequeはvectorの上位互換
？
2020/10/27(火) 07:36:25.65
りんごさんの3桁問題ってなんですか
2020/10/27(火) 07:57:29.82
AGC012の解説放送の冒頭
2020/10/27(火) 08:32:49.11
multiset の insert は O(log N)
priority_queue の push は O(1)
2020/10/27(火) 09:03:11.35
priority_queueのpushがO(1)というソースってどこかにある？
2020/10/27(火) 09:10:57.76
https://cpprefjp.github.io/reference/queue/priority_queue/push.html
https://cpprefjp.github.io/reference/algorithm/push_heap.html

logだと思う
2020/10/27(火) 09:18:00.16
topがO(1)の勘違いかな
2020/10/27(火) 09:32:30.52
multisetが優秀すぎるんだよな
2020/10/27(火) 09:59:41.48
pushも平均はO(1)だった気がする
2020/10/27(火) 10:11:39.69
ソースが無いと信じない
606仕様書無しさん
垢版 |
2020/10/27(火) 10:20:05.88
今回のARCのDみたいな式変形問題ってどこで演習できるの
典型って言ってる人よくいるけど
2020/10/27(火) 10:37:15.03
あーだーこーだー聞いてるんだけどちょくだいさん舌足らずなのかな
2020/10/27(火) 10:43:45.67
典型要素としては最近だと↓こんなのがあったね
https://atcoder.jp/contests/abc177/editorial/88
2020/10/27(火) 10:51:17.77
「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 を買いました。
会津大学と付いているでだけで買い
2020/10/27(火) 10:56:46.17
色飛ばしてレート上がってるやつなんなの？
2020/10/27(火) 10:57:56.83
>>609
けんちゃん本とどっちがいいんだろうね
両方読んだことないが
612仕様書無しさん
垢版 |
2020/10/27(火) 11:53:59.87
>>608
それはすぐ解けたけど確かに似てるな、ありがとう
応用力がまだまだだったな
2020/10/27(火) 12:12:23.56
回答をtouristに委任してるチーター
2020/10/27(火) 12:30:00.41
回答をtouristに委任してるtourist
2020/10/27(火) 13:13:01.17
データ構造もアルゴリズムも特段定型的な知識要求されないけど数学力が試されるようなやつが全然解けない
2020/10/27(火) 13:14:17.34
multiset（順序付き集合）ってC++以外に持ってる言語ある？
2020/10/27(火) 13:17:07.00
>>600
そもそもC++のSTLって具体的な実装までは規定しないことが多いから、実装次第では一応O(1)になったりもするんじゃないの？
例えばフィボナッチヒープで実装されてる場合とか
普通じゃないけど
2020/10/27(火) 13:25:53.53
二分ヒープだよ
2020/10/27(火) 14:28:08.56
>>615

二辺a,bがありその角度Θでできる三角形の
対辺cを求めよ
c＾2　=a＾2+ｂ＾2　-　2*a*b*cosΘ
2020/10/27(火) 18:27:05.78
atcoder界隈の民、普通高校数学は高校卒業までに終わらないってこと知らなさそうな奴ばっかりでスタートラインの差を感じる
2020/10/27(火) 18:28:41.33
意味がわからん
なんでそんなやつが競プロをやってるんだ
622仕様書無しさん
垢版 |
2020/10/27(火) 18:33:08.25
chokudai(高橋 直大)🍆　@chokudai
びっくりするほど競プロ勢と就活の相性が悪いことが分かったので、もうちょい就活楽にする方法をかんがえる。

https://twitter.com/chokudai/status/1320998922324590592
https://twitter.com/5chan_nel (5ch newer account)
2020/10/27(火) 18:36:48.90
レッドコーダーが登録したらGAFA内定が降ってくるようなサービスが必要
2020/10/27(火) 18:50:50.64
就職のためにやってた人かわいそう
いるのか知らないけど
2020/10/27(火) 19:49:29.68
競プロと就活
じゃなくて
競プロ”勢”と就活なんだな・・・(涙
2020/10/27(火) 19:59:46.12
就活するなら競プロは諦めろって、はっきりいう方が誠実やで
2020/10/27(火) 20:08:38.60
精進とか言って就活とは正反対の努力をしてたらそれはね
2020/10/27(火) 20:20:08.29
テレビゲームで就活を楽にするとか言ってるのと大して変わらんよな。
2020/10/27(火) 20:25:53.88
ネトゲですのでー
まあ仕事もゲームっちゃゲームではあるけど
2020/10/27(火) 21:08:16.23
ネトゲ中毒のチー牛が就活と相性いいわけないだろ
2020/10/27(火) 21:33:58.50
>>629
その例えに乗っかるなら
「FFでレベル上げたのになんでドラクエではレベル1からなんだよ！」
とか言い出す馬鹿と同じだぞ。
2020/10/27(火) 21:37:08.41
例え話でもなくね
競プロはネトゲ、ただの事実
2020/10/27(火) 21:50:26.00
>>620
IF(atcoder界隈の民)
　IF（普通高校数学は高校卒業までに終わらない）
　　IF（知らなさそう）
　　　　IF(奴ばっかりで）
　　　　　スタートラインの差を感じる
　　　　ELSE
　　　　　奴ばかりでないばあいは差を感じない
　　ELSE
　　　知っているので大学の数学を履修
　ELSE
　　ユークリッド幾何は証明なので苦手だった、公式の解法で点を取った
2020/10/27(火) 21:51:59.67
競プロはネトゲ
チョクダイにもそう書いてある
2020/10/27(火) 22:23:55.02
他よりは役に立つネトゲだけどそれだけでなんとかなるわけでもないんだなあ
2020/10/27(火) 22:36:11.12
レッドコーダーは東大数学100点安定するレベルは最低求められるっての面白いな
ポテンシャルのレベル感的にはそんなもんなんだろうね
2020/10/27(火) 22:39:46.14
数オリ勢が競プロに切り替えて中高生の時間をプログラミングに割くようになれば社会全体の生産性は微増するはずなので
競プロは有意義
2020/10/27(火) 22:46:29.76
競プロなんかに時間使うよりか数学に時間使う方が社会全体の生産性上がるわ。
639仕様書無しさん
垢版 |
2020/10/27(火) 22:50:48.22
競プロ以上に天才以外お断りパズルコンテストだぞあれ
2020/10/27(火) 22:59:00.04
逆に東大数学100安定しても全然赤になれない人はいそう
流石に黄くらいまでは苦労しないだろうけど
2020/10/27(火) 22:59:34.74
同じネトゲでもどっかのギルドで調整役でもしてた方が実社会の役に立ちそう
2020/10/27(火) 23:21:21.33
数え上げは役に立ちそう
2020/10/27(火) 23:39:50.94
むしろ最も役に立たないだろ
644仕様書無しさん
垢版 |
2020/10/28(水) 00:14:32.66
業プロerだけど直接役に立ったのはまさかの枝狩りだったよ
2020/10/28(水) 00:23:37.25
>>637
りんごがまさにそんなかんじでは？
2020/10/28(水) 00:32:47.46
まさかではないだろ
強いていえばマラソン系の方が実務寄りとは聞くし
647仕様書無しさん
垢版 |
2020/10/28(水) 01:41:36.00
ネトゲと就職という、離れているものを結び付けようとするからこそビジネスになるのでは
就活に直結するスキル持ってる人は既存サービスで就活するだけだし
648仕様書無しさん
垢版 |
2020/10/28(水) 01:55:43.85
業プロerってなーに？
枝狩りってなーに？
2020/10/28(水) 02:03:05.31
業プロerは敗北者のこと
枝狩りは手足を切り落とすこと
2020/10/28(水) 07:19:33.27
気に入らん同期を視界から消すことやで
2020/10/28(水) 08:45:46.61
枝狩りがなんだこちとら首狩りだぞ

首狩りされたい
2020/10/28(水) 11:36:22.08
>>611
問題文
逆ポーランド記法は、演算子をオペランドの後に記述する数式やプログラムを記述する記法です。例えば、一般的な中間記法で記述された数式 (1+2)*(5+4) は、逆ポーランド記法では 1 2 + 5 4 + * と記述されます。逆ポーランド記法では、中間記法で必要とした括弧が不要である、というメリットがあります。

何をいっているのかわかりますか
で、会津大学の本は
こうした問題文の意味を教えてくれます
2020/10/28(水) 12:35:56.08
分からないわけないだろ。それ以上どんな説明が必要なんだ？
2020/10/28(水) 13:42:46.18
>>647
役に立つと思わせて馬鹿を騙すのが一番儲かるという結論
2020/10/28(水) 14:00:50.64
演算子とオペランドって知らない人からしたらよくわからん単語じゃね
2020/10/28(水) 14:22:02.58
プログラミングをする人としてはそれくらいは前提知識として要求しても問題ないだろう
2020/10/28(水) 15:40:36.35
>>653
>>(1+2)*(5+4) は、逆ポーランド記法では 1 2 + 5 4 + *
>分からないわけないだろ。
十二　プラス　五十四　プラス　コメと読めます
2020/10/28(水) 15:56:28.84
そういった常識含めて問題解いたり本読んだりして分かるようになっていくならなによりやね
こういうのは一冊だけと言わず, けんちゃんも蟻本もどんどん手に取ってみるのがええと思う
(順に読破したいタイプなら別やが)
2020/10/28(水) 19:04:21.53
けんちゃん今黄色じゃん
秋葉さん監修にしといて良かったな
2020/10/28(水) 19:06:57.65
けいちょん本
2020/10/28(水) 19:08:19.49
ちょがつく人
2020/10/28(水) 19:08:29.50
青の次が黄で橙赤？
2020/10/28(水) 19:13:10.06
>>652
> 逆ポーランド記法は、演算子をオペランドの後に記述する数式やプログラムを記述する記法です
この一文が読みにくいわ
前提知識なしでさっと読んだときに1つ目の「記述する」が最後の「記法」にかかってると気づくのに3秒かかる
2020/10/28(水) 19:44:56.87
正直逆ポーランド記法なんて問題文で説明するもんでもないやろ。親切すぎて雑魚がつけ上がる構図
2020/10/28(水) 20:05:42.34
黄色が書いた競プロ本ありがたがる層って…
ま、自由ですがｗ
2020/10/28(水) 20:06:00.37
競プロ界は名前にちょが付く人とけんが付く人によって支配されています
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況