競技プログラミングにハマるプログラマのスレ 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/17(日) 22:57:01.46
三角関数くらいこれまでも散々出しただろ？と思われてるな
2020/05/17(日) 22:58:54.72
複素数を使えば頭を使う必要なし
2020/05/17(日) 23:02:50.40
むしろ余弦定理の方がややこしくねえか
わざとややこしく書いてる解説かこれ
2020/05/17(日) 23:08:52.75
余弦定理だと脳死でできるから楽
2020/05/17(日) 23:09:06.12
数え上げ人材育成コンテストだな
276仕様書無しさん
垢版 |
2020/05/17(日) 23:12:29.35
E，arccosの場合分けが辛すぎと思ったら全然違う方法だった・・・
2020/05/17(日) 23:12:54.80
E難しかったな
2020/05/17(日) 23:13:33.99
今日ので数学コンって言われるのは草
2020/05/17(日) 23:16:42.93
EってABC166Eと同じ方法で溶ける？
2020/05/17(日) 23:16:47.42
Atcoder 中学受験 Contest
281仕様書無しさん
垢版 |
2020/05/17(日) 23:21:04.84
D,幅探索で最初にオープンした所の親という方針でなぜ駄目だったのかわからない・・・・
2020/05/17(日) 23:22:54.37
E pairsみたいだな
考慮することが多くて本番で解くのは難しいわ
2020/05/17(日) 23:47:00.08
C問題、間の角度を求めてsqrt(a^2 + b^2 - 2a*b*cos(theta*PI/180.0))ではダメなんでしょうか？
最後の2つのケースだけWAになります

分刻みで時針も動かしてるし変数も全部倍精度で取ってるのですが・・・
2020/05/17(日) 23:48:36.16
>>283
間の角度が間違ってそう
2020/05/17(日) 23:49:30.97
theta=min(2pi-theta,theta)したらなおりそう
2020/05/17(日) 23:55:49.06
>>285
その式のpiとかthetaの単位はなんでしょうか？
>>283はPIが3.14…でthetaは角度（0≦theta＜180）なのですが
287仕様書無しさん
垢版 |
2020/05/18(月) 00:00:04.09
theta桁落ちしてそう
288仕様書無しさん
垢版 |
2020/05/18(月) 00:03:55.19
Eは直行したり、近いベクトルを高速に探索するみたいなのがCS的に普通ちゃ
2020/05/18(月) 04:31:56.31
競プロは仕事の役に立つと考える人、、
MBAは起業の役に立つとも考えてそう
2020/05/18(月) 06:35:25.25
>>281
それで平気だったよ
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任せで誰かがチェックとかしてないのかね
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況