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

■ このスレッドは過去ログ倉庫に格納されています
1仕様書無しさん
垢版 |
2020/05/09(土) 00:48:33.62
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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
※前スレ
競技プログラミングにハマるプログラマのスレ 24
https://medaka.5ch.net/test/read.cgi/prog/1585409967/
2020/05/18(月) 07:34:56.21
>>290
有難うございます。式はあってそうなのでテストケース公開を待ってみます
292仕様書無しさん
垢版 |
2020/05/18(月) 08:07:22.52
多重派遣偽装請負損害を助長して
稼働増やして収入減らした
安売り貯金なしドカタは
コロナ恐慌で制裁を受けるべき
2020/05/18(月) 08:27:48.48
>>291
ちなみに出力例は複数あるからテストケースのoutのみが正解ではないからね。
2020/05/18(月) 09:11:00.48
昨日のdiffはよ
2020/05/18(月) 11:33:07.97
経験上、x問目のdiffはx完最遅のパフォ-100〜200くらいのことが多いから
D600
E1600
F2400
くらいっぽそう
2020/05/18(月) 11:44:38.21
過去のBFSって1000くらい無かったっけ。
2020/05/18(月) 12:08:12.26
dfsするだけ、bfsするだけみたいなのは競プロの基本中の基本だから
もっと前のほうで出したらいい
2020/05/18(月) 12:11:04.13
295は適当だったな、D700E1700F2400くらいかな
2020/05/18(月) 12:13:46.01
きたぞ。
750、1800、2500くらい。
2020/05/18(月) 12:36:38.30
DいぇすだけじゃなくＮＯも作って欲しかった
連結成分がひとつじゃないやつ
301仕様書無しさん
垢版 |
2020/05/18(月) 12:48:55.23
昨日のEについて、解説にある連想配列までは作れたのですが、その後の『基礎的な数え上げ』ができませんでした…
数え上げって何か勉強の仕方ありますか？あまり競プロの解説記事もない気がするのですが…
高校数学からやり直せ、という話でしょうか？

>したがって，”仲の悪いつがい” になる傾きのペア (高々 N 通り) 全てについて，連想配列などを 使って各傾きになるイワシの個数が求まれば，その後は基礎的な数え上げの範疇です.
302仕様書無しさん
垢版 |
2020/05/18(月) 12:56:08.70
ここはwriterも説明足りなかったかなって反省してたとこだね
ある集合から自由に選べるのが2^n通りなのがわかれば
集合(S,T)から取り出したとき、すべてが片方の集合に属する場合の数は
Sのみ: (2^s)*1 (sはSの要素数)
Tのみ: (2^t)*1 (tはTの要素数)
になって、ここから両方空集合になる1通りを除いて
(2^s)+(2^t)-1になる
2020/05/18(月) 12:58:49.77
Dで非連結を判定するのは考察の量に比べて実装が重いからなあ
304仕様書無しさん
垢版 |
2020/05/18(月) 13:03:11.66
そんなに重いか？
1からBFSし終わって訪れてない点があればNoで終わりじゃない？
2020/05/18(月) 13:08:49.39
UnionFindでやっても良さそう
2020/05/18(月) 13:36:02.58
BFS だけで連結性判定終わってるのに Union Find 持ち出す理由がなくね
2020/05/18(月) 13:38:59.50
連結リストに出てこなかった数字は非連結（嘘解法）
308仕様書無しさん
垢版 |
2020/05/18(月) 15:02:20.50
>>302
書いていただいてありがたいのですが、集合S,Tをどう扱えば良いのかがわかりませんでした
例えば、傾き1/3,2,3,5のイワシがいるとしたら、1/3と3をペアにしてはならず、また1匹以上という制約からペアのルールを無視すると全体で2^4-1というのはわかるのですが、
そこから書いてもらってるS,Tの議論にどう紐づければ良いのでしょうか？
Sのみ、Tのみという考え方をするのであれば、1/3と3が別れるように、S=[1/3,2,5]、T=[2,3,5]とするのでしょうか？（ただこの場合は2,5を含んだケースをダブルカウントしてしまいそうな…）
2020/05/18(月) 15:07:18.29
一旦互いに仲が悪いようなペアだけで考えて、それぞれをかけて答えにする

その例だと
{1/3}←→{3} で 3通り
{}←→{2} で 2通り
{}←→{5} で 2通り

これらをかけて12通りから全部0匹の1通り引いて11通り
310仕様書無しさん
垢版 |
2020/05/18(月) 15:17:43.35
editorialに「基本的な数え上げの範疇」とか「証明は簡単、そうでないと直感的に嫌な気持ちになります」と書いてあったり、問題名が意味不明でわかりにくかったり、今回個人的にかなり不快な要素が多いがあまり燃えていない。
2020/05/18(月) 15:32:41.50
解説って考察の指針くらいしか書かれていないので、解説動画見た方がいいとおもうよ。
低レートが読んでも基礎がないから理解できないと思う。
312仕様書無しさん
垢版 |
2020/05/18(月) 15:40:51.99
>>309
ありがとうございます、わかってきました
仲が悪い組み合わせについてはそれらを一まとまりにして考えつつ、
仲悪い群(複数あっても良い)同志や、2や5などのその他の数字は独立で考えることができるので、それぞれの組み合わせ数をかけていく、という感じですかね

追加で理解を確認させていただきたいのですが、例えば1/3, 3, 3のように片方（あるいは両方）が
複数になった場合、 >>302 で書いているやり方で言うと、
{1/3}の取り方が2^1=2、{3, 3}の取り方は2^2=4、これらは相反する（独立ではない）ので、かけてはならず、
足しあわせて、2+4 =6となります
このあと、-1しているのはどういったケースを排除する目的なのでしょうか？
数え上げると、あり得るのは{}, {1/3}, {3}, {3}, {3, 3} の5通りなので、これで計算合っているとは思うのですが、、
イメージとしては、単純に2+4した時の、{}, {}, {1/3}, {3}, {3}, {3, 3} から最初の空集合の重複を取った感じでしょうか？
2020/05/18(月) 16:10:35.46
しょせんおまけ要素
2020/05/18(月) 16:14:46.97
editorialはわかってる人が読んでわかる程度に書かれていればいいと思う
わからない人にわからせるためにはそれ用にコストを掛けないと無理
315仕様書無しさん
垢版 |
2020/05/18(月) 16:24:16.38
>>312
両方空集合になるものを2回見ちゃってるからそれを引く目的であってる
どんなペアだろうと2^s+2^t通り列挙すると{}が2回出てくるからね
316仕様書無しさん
垢版 |
2020/05/18(月) 16:37:09.54
>>310
燃えるにも才能が必要
2020/05/18(月) 17:40:04.83
某黄色コーダー
「文句言ってんのは、お前がその問題解けないからだろ?」
だとさ
日本社会の基本はどこへ行っても弱い者いじめだね!
2020/05/18(月) 18:02:59.61
また変なの湧いてきたな
2020/05/18(月) 18:14:23.53
赤がこれ言っても燃えないのに黄色がこれ言うとキレるやつが出るあたりやっぱレート主義なんやなって
320仕様書無しさん
垢版 |
2020/05/18(月) 18:33:26.62
弱い者いじめとは思わない
経験の多い人ほど正しいことを言ってる可能性が高い
2020/05/18(月) 18:35:11.16
信者の発想
2020/05/18(月) 18:40:57.23
運営じゃない人を叩くつもりは無いぞ
(´・ω・`)
2020/05/18(月) 18:57:08.59
強くなりたくないけど文句言ってる奴は帰れ
強くなりたいけど文句言ってる奴は問題解け
強くて文句言ってる奴は問題作れ
2020/05/18(月) 19:04:01.91
信者がどうとかそういうのいいから
2020/05/18(月) 19:11:54.72
この話題がどうでもよくね
326仕様書無しさん
垢版 |
2020/05/18(月) 20:14:41.98
>>315
遅くなりましたがありがとうございます！
完全に理解しました、、、！
2020/05/18(月) 21:44:47.09
>>310
要素は多いけど全部小粒だからじゃない？
てか基本的な〜とか原始的な〜とかやめればいいのにな
どこまでが基本的か最初に定義しろ
2020/05/18(月) 21:54:33.19
>>317
黄色ってコンプレックス抱えてる人多そう
AｔCoderでも中途半端だし社会では役に立たないし
2020/05/18(月) 22:04:05.58
黄色は本当に掃いて捨てるほどいるからかなり精神をやられる
2020/05/18(月) 22:10:33.70
すぬけさんの解説は素晴らしい
2020/05/18(月) 22:24:00.44
令和ABC 前ならそれなりに希少だった気がするが現状はなあ
橙渇望してるやつかなり多いんでないか、自分がそうなんだけども
332仕様書無しさん
垢版 |
2020/05/18(月) 22:29:23.78
黄色が掃いて捨てるほどいるは嘘でしょ
2020/05/18(月) 22:45:43.07
黄色の人数は二倍になってるからね
https://mobile.twitter.com/saba_kpr/status/1257351326159319042
https://twitter.com/5chan_nel (5ch newer account)
2020/05/18(月) 22:46:13.53
年収低いし…
https://twitter.com/an_nindouph/status/1261689818376888320
https://twitter.com/5chan_nel (5ch newer account)
2020/05/18(月) 22:59:10.30
こっからのAGC連打である程度減るでしょ
336仕様書無しさん
垢版 |
2020/05/19(火) 00:24:36.84
青で他のスキルも高い人が年収高いご時世
2020/05/19(火) 00:28:16.54
実際どうか分からんけど英語しっかり使えたら年収倍になるみたいな話はよく聞く
338仕様書無しさん
垢版 |
2020/05/19(火) 00:28:39.51
競プロで年収上げたい
2020/05/19(火) 00:31:49.63
>>337
緑でとーいっく900ぐらいが英語喋れない黄色の年収2倍とかでうーんってなった
2020/05/19(火) 00:39:07.08
それは当たり前だろ
前者が灰色でも同じ
2020/05/19(火) 00:40:21.84
TOEICも競プロのレーティングも実力の一部を測る指標でしかないんだからそういうことも起こるだろうなあって感じしかせん
342仕様書無しさん
垢版 |
2020/05/19(火) 00:45:39.43
赤や橙の年収はいくらなんだろう
2020/05/19(火) 00:47:18.61
いや流石にTOEICと競プロは価値が違いすぎ
344仕様書無しさん
垢版 |
2020/05/19(火) 00:47:30.81
jobsに載ってる企業は高い方ということか
345仕様書無しさん
垢版 |
2020/05/19(火) 00:52:12.56
>>339
界隈に染まり過ぎ
普通につよつよな人だぞ
2020/05/19(火) 00:57:27.49
TOEIC800AtCoder黄色だけど高く雇ってもらっていいよ
実務経験？ゼロです
347仕様書無しさん
垢版 |
2020/05/19(火) 01:11:04.33
https://atcoderstats.appspot.com
これ見ると黄色下位(2000-2100)が多いということか
2020/05/19(火) 01:12:13.01
年齢学歴AtCoderとTOEICを説明変数にして年収推定の機械学習やってみたいな
2020/05/19(火) 01:19:30.71
説明変数にコミュ力と容姿を入れると爆上げすることが知られている
350仕様書無しさん
垢版 |
2020/05/19(火) 09:44:47.77
ABC050以前のテストケースってどこにあるの？誰か教えてください
2020/05/19(火) 10:21:04.91
dropboxにないのは公開されてないと思うけど
352仕様書無しさん
垢版 |
2020/05/19(火) 10:59:35.08
>>351
そうなんですね、ありがとうございます
全部公開して欲しいな
2020/05/19(火) 11:22:43.29
テストケースは一部有料でもいいかな

それと遅い言語でTLEが定数倍の問題なのかどうか見極めるためにコンテスト終わった問題は課金で制限時間緩和オプションがあるといいと思う
2020/05/19(火) 14:23:22.38
テストケース公開されてないのがあるのは疑問。
きっと後ろめたいことがあるに違いない。疑惑は更に深まった（野党風）
2020/05/19(火) 14:30:25.93
テストケース非公開の競プロサイト
多いよな
2020/05/19(火) 14:34:24.62
テストケースが合えばいいとは言ってもちゃんと問題を解いてくれたほうが嬉しいからな
2020/05/19(火) 14:59:12.04
入力値に対応した出力するだけでAC出ちゃうしね
2020/05/19(火) 15:04:41.53
そんなことする奴おらんやろ
2020/05/19(火) 15:19:23.39
いるんだよなあ…
2020/05/19(火) 15:47:59.04
なんの意味があるんだ…
2020/05/19(火) 16:32:10.05
ゴルフ勢なら基本テク
362仕様書無しさん
垢版 |
2020/05/19(火) 17:52:53.49
未経験から半年でフリーエンジニアになれる人の特徴
https://www.youtube.com/watch?v=YCxu0jn52Qw
フリーランスか会社員かどっちが簡単かについての最終回答
https://www.youtube.com/watch?v=JA4JNSmIdxI
【エンジニア】正社員/派遣社員/フリーランスのメリット・デメリットについて
https://www.youtube.com/watch?v=fTG-eMpwhCg
月収1000万円オンラインサロンオーナーの日常【飲み過ぎ】
https://www.youtube.com/watch?v=lPfWZLatYus&;t=107s
借金400万円から人生逆転するまでの軌跡
https://www.youtube.com/watch?v=fXdHlFFUjGY
エンジニアはお金を追求してはいけないという年寄りを論破してみた
https://www.youtube.com/watch?v=qJHCmxFv718
プログラミングスクールを否定する老害どもについて
https://www.youtube.com/watch?v=K2SN-Rr0PgY&;t=506s
新人叩きしてる古参勢がすぐ儲からなくなる理由
https://www.youtube.com/watch?v=Ch9Ir8O-iqU&;t=332s
2020/05/19(火) 18:25:46.46
豆みたいなコードばっかり書いて、何の意味があるの?
「競技数学パズル」と名称を改めたまえ
2020/05/19(火) 19:03:36.25
スレチ
2020/05/19(火) 19:39:35.10
競技数え上げ
2020/05/19(火) 21:33:16.31
微分積分も出そう
2020/05/19(火) 21:38:19.62
https://atcoder.jp/contests/yahoo-procon2019-final-open/tasks/yahoo_procon2019_final_a
↑こういうの出していいぞ
2020/05/19(火) 22:03:54.53
その問題数値積分でも通るんだよな
2020/05/19(火) 22:36:58.97
>>310
未だにTLに話題が出るから地味に燻ってるぽい
2020/05/19(火) 22:39:15.58
editorialは完全にwriter任せで誰かがチェックとかしてないのかね
371仕様書無しさん
垢版 |
2020/05/19(火) 22:43:36.03
意味不明な数え上げや整数の問題ばかり出ていて、積分が出ないのは流石に不自然だぬ
2020/05/19(火) 22:54:47.69
積分であることが本質でない問題はなかなか出しづらそう
2020/05/19(火) 23:45:15.95
数え上げも積分だろ
2020/05/20(水) 00:24:45.25
一般の測度で積分すな
2020/05/20(水) 06:14:56.90
数え上げ測度とかいうのあったな
2020/05/20(水) 09:04:54.87
測度が違うだけなんだったら、誤差が本質になってしまわない数え上げのほうがいいよね
377仕様書無しさん
垢版 |
2020/05/20(水) 10:23:56.10
一瞬だけ黄色になってその後周りのレベル上がってくのについていけなくて水色くらいまで落ちても「一生黄色」名乗っていいの？
2020/05/20(水) 10:36:23.81
ワイは許したるぞ
2020/05/20(水) 10:40:02.01
いいよ
2020/05/20(水) 11:11:33.11
個人的にhighestは参考にしてない
2020/05/20(水) 12:55:27.96
UT戦国時代に突入
他人の努力は止められぬ
2020/05/20(水) 14:23:01.66
名乗ってもOK
2020/05/20(水) 17:37:09.62
2年経つとランキングから消されるからそしたら流石にという感じがする
2020/05/20(水) 18:07:33.10
1900台とか1800台ならまだしも水色だったら恥ずかしくて口にできないレベル
2020/05/20(水) 19:31:17.53
atcoderでhighest - 2色ってなかなかキツくね
2020/05/20(水) 23:39:23.37
東大生が高校生以来に他人にマウント取れるフィールドなんだ許してくれ
2020/05/20(水) 23:46:21.09
お前らもちろんPASTリアルタイム受験だよな？
2020/05/20(水) 23:52:21.97
AGCとリアルタイムマークどっちを重視するかよな
2020/05/21(木) 11:51:45.29
5時間って結構キツくない？
2回に分けてくれた方が嬉しい
2020/05/21(木) 12:08:26.49
飲み食い昼寝ok
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況