競技プログラミングにハマるプログラマのスレ 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/
49仕様書無しさん
垢版 |
2020/05/09(土) 19:32:27.21
最近競プロ初めてあまり精進せずに緑はいけそうだけど、
水色って競プロ民にはどういう評価？
2020/05/09(土) 19:35:31.94
普通
ちな緑
2020/05/09(土) 19:48:13.43
>>48
頭悪い
2020/05/09(土) 19:50:47.44
>>49
天才
ちな青
2020/05/09(土) 19:51:47.41
200問くらいといて緑なんですけどどう思いますか？
2020/05/09(土) 20:03:03.88
どうも思わん
2020/05/09(土) 20:44:59.66
以下の問題について質問です

【問題】
敵の体力はXで、体力を0以下にすると倒せる
選択できる攻撃手段は、通常攻撃と必殺攻撃の2つある
・通常攻撃：確実に敵の体力をA減らす
・必殺攻撃：2/3の確率で敵の体力をB減らす
最適に攻撃を選んだとき、敵を倒すために必要な攻撃回数の期待値はいくつか？

答えは min(X / A, X / (2 / 3 * B)) だと思ったのですが、
正しくは「dp[i] := 体力iを0にするために必要な回数の期待値」とおいてDPをすることでした
なぜ min(X / A, X / (2 / 3 * B)) では期待値が正しく求められないのでしょうか？

どこが間違っているかわからないため質問いたしました
回答よろしくお願いします
2020/05/09(土) 20:49:58.42
私の求めた min(X / A, X / (2 / 3 * B)) が期待値でないなら、いったい何なのか？
というのがわからないです…
57仕様書無しさん
垢版 |
2020/05/09(土) 20:50:40.32
どこの問題？できればURL貼ってくれ
2020/05/09(土) 20:52:42.03
https://yukicoder.me/problems/no/23
こちらです
2020/05/09(土) 20:54:29.79
X=101, A=1, B=100のときの最善手は...？
2020/05/09(土) 21:00:47.78
オーバーキルしそう
2020/05/09(土) 21:02:34.80
>>59
必殺攻撃が1度でも当たれば通常攻撃1回、が最善手ですかね…
そう考えると、確かに期待値2.5回が正しそうだなという感じがしますが、
そうなると min(X / A, X / (2 / 3 * B)) はいったい何なのか？というのが気になります
これは期待値ではないのでしょうか？
62仕様書無しさん
垢版 |
2020/05/09(土) 21:03:27.22
通常攻撃と必殺攻撃を組み合わせるのが最適な場合もあるから,
その貪欲だと通らないってことか
2020/05/09(土) 21:05:50.73
>>61
期待値ではありません
64仕様書無しさん
垢版 |
2020/05/09(土) 21:06:11.14
min(X / A, X / (2 / 3 * B))

これ 2と3 逆では？
65仕様書無しさん
垢版 |
2020/05/09(土) 21:07:50.32
ごめん。なんでもない
変なこと言った
2020/05/09(土) 21:07:50.64
>>64
一回の必殺攻撃で減らせる体力の期待値は 2/3*B だからあってるんじゃないの？
2020/05/09(土) 21:09:18.21
>>61
その値に意味はないんだけど、なぜ意味がないかを考察したいならX=1, A=1億, B=100の場合で考えてみたらいい
2020/05/09(土) 21:14:10.67
蟻本p.123 Millionaireが近いことを説明してる気がする
2020/05/09(土) 21:15:09.65
>>67
代入してみると、なんとなく意味のない値だということが理解できました
回答ありがとうございました
2020/05/09(土) 21:25:12.66
無意味ってことはないな
Xを無限に大きくしたときの近似値ではある
71仕様書無しさん
垢版 |
2020/05/09(土) 21:25:34.78
期待値難しいね. 俺も最初の解法何が間違ってるのか分からなかった
数学の教科書読み直そうかな
2020/05/09(土) 21:38:20.26
減る体力の期待値と回数の期待値をごっちゃにして考えたのがいけなかったのかもしれません
2020/05/09(土) 21:43:19.63
Bだけ使う場合の期待値は、ceil(X/B) = m として、
Σn・cobination(n-1, m-1)・(2/3)^m・(1/3)^(n-m) from n = m to inf
ですね。B=100のとき、X=101とX=200は回数の期待値としては変わらないはずです。
2020/05/09(土) 21:45:16.15
強くなりたいのですが何すればいい
2020/05/09(土) 21:45:53.06
精進
2020/05/09(土) 21:52:35.09
m/(2/3)と等しくなるんじゃないの
2020/05/09(土) 22:01:20.93
>>55
お前さんの答えでは、通常攻撃のみ、または必殺攻撃のみのケースしか考慮してない。
例えば途中までは必殺攻撃を連発した方が効率的に体力を減らせたとして、残り体力がA以下になったなら、外れる可能性のある必殺攻撃を使うのは最適な攻撃でないから通常攻撃を選択しなければならない。
2020/05/09(土) 22:17:48.73
CodeforcesのDiv4というのに出てみたいんですが、参加経験が1度しかないです
rateが変わらないだけで普通に参加はできるのでしょうか？
79仕様書無しさん
垢版 |
2020/05/09(土) 22:20:00.36
できるよ
80仕様書無しさん
垢版 |
2020/05/09(土) 22:39:36.21
コドフォ出るなら CF-Predictor っていうブラウザ拡張入れるのおすすめ
2020/05/09(土) 22:44:47.52
ありがとうございます
2020/05/10(日) 09:47:55.40
問題が理解できません
AtCoder Beginner Contest 087C
＞ 左上および右下のマスにもアメが置かれており、あなたはこれらのマスに置かれているアメも回収します。
移動先マスとその左上・右下の3か所からアメを回収できると思うのですが、
回答例だと移動先マスしか集計していません
上記の記述はどういう意味なんでしょうか？
2020/05/10(日) 10:08:50.87
> 左上および右下のマスにもアメが置かれており、あなたはこれらのマスに置かれているアメも回収します。

(1,1) ,(2,N)のアメも回収するということ。
書き方があいまいだと思うけど、問題文には移動中のマスの左上および右下のマスとは書いていない。

入出力例から察して。
2020/05/10(日) 10:11:13.17
いや問題文に左上のマス＝(1.1)、右下のマス＝(2,N)と書いてあるわ。
書き方があいまいとか言ってすみません。
2020/05/10(日) 10:13:21.94
>>84
開始と終了の地点って意味だったんですね
ありがとうございます！
2020/05/10(日) 13:55:19.92
めんどくさいから質問するならリンクを貼って欲しいな
2020/05/10(日) 16:44:16.77
https://codeforces.com/contest/1342/problem/D
この問題文の意味がさっぱり分からなかったので、問題概要を教えてください
2020/05/10(日) 17:00:35.65
testcase -> 玉
multi testcase -> 箱 と読み替えて
大きさ M_i (1 <= i <= n, 1 <= M_i <= k) の玉があります
玉を箱に詰めようと思ってます
一つの箱に入れられる玉には条件があります
条件: サイズ j (1 <= j <= k) 以上の玉はC_j 個までしか入れることができない
全ての玉を箱に入れるために必要な箱の最小数とそのときの玉の配置を求めてください
2020/05/10(日) 18:11:02.55
Codeforceって初期レート1500なんですか？
2020/05/10(日) 18:21:57.54
>>88
ありがとうございます！
コンテスト中はさっぱり理解できなかったですがこれで解き直せます！
2020/05/10(日) 18:34:57.79
コドフォ1回しか参加してないのに昨日のratedになってた
よくわからん
2020/05/10(日) 19:01:12.33
もしAtCoder社が、解説の公開を2年も完全放置していたら、
ユーザーからのクレームで大変な思いをするだろうに、
某公立大学は呑気でいいですねえ
さぞかし「仕事」が捗るんでしょうなあ!
2020/05/10(日) 19:15:25.75
なんか某社長の発言的に今日のABCも負荷でおじゃんになるのかしら
2020/05/10(日) 19:51:12.53
15000まで大丈夫って言ってて今回は15000行きそうにないんだからおじゃんにはならないだろ
2020/05/10(日) 19:56:20.47
無課金ユーザーは高負荷時にキックされるようにすればいいのでは？
2020/05/10(日) 22:47:52.64
Fcodeforceで見た
2020/05/10(日) 22:55:28.50
最高パフォ更新は気持ちいいなあ
AGCARCまでに黄色になりたいねえ
2020/05/10(日) 22:59:34.44
Fの貪欲パートはAtCoderの過去問にもあるよ
2020/05/10(日) 23:42:19.20
コンテストの結果ってどうやってツイートするの
2020/05/10(日) 23:43:35.56
>>99
マイプロフィール＞直近のコンテスト成績証＞ツイッターアイコン
2020/05/10(日) 23:47:09.12
>>100
ありがとう！
でもツイッターアイコンなかったわ
初参加だからかも
102仕様書無しさん
垢版 |
2020/05/10(日) 23:48:24.08
？？？「E問題は数学なのだ。」

だよなぁ
103仕様書無しさん
垢版 |
2020/05/10(日) 23:50:44.70
さすがに数学率高すぎない？
104仕様書無しさん
垢版 |
2020/05/10(日) 23:57:19.26
高校数学っぽくしないとエリート受験生様の勉強の邪魔になってしまうからの
2020/05/10(日) 23:57:40.10
これが競技プログラミングや　就活に役立つ？　実装力を問う？　
そんな小っちぇえものじゃねぇ、競プロは数オリなんだ、数学オリンピックなんだってことを、分からねぇやつに容赦なんざぁするわけがねぇだろうがよ
2020/05/11(月) 00:02:12.57
赤コーダー様のお言葉だ
2020/05/11(月) 00:05:09.69
>>101
Adblock入れてたら消えてたことあるからそれかもよ
2020/05/11(月) 00:23:33.61
>>107
でた！ありがとう！
2020/05/11(月) 00:30:57.99
Dまで最速でも1400パフォとかなのな
2020/05/11(月) 00:38:10.71
>>106
自他ともに認める老害の人じゃん
2020/05/11(月) 05:06:15.93
某、素人である学生に作問を任せるのを辞めろ
アルゴリズムの問題はアルゴリズムの専門家が作れ
近年如実に問題の質が低下してるじゃねーか
2020/05/11(月) 06:58:38.04
某は知らんがTopCoderもCodeforcesも大体学生じゃね
2020/05/11(月) 08:13:25.03
昨日のABCは特に荒れなかったしいい問題セットだったってことかな
2020/05/11(月) 11:44:54.13
昨日は灰灰茶茶水青でうまい具合に傾斜ついてるし良いセットだと思った
2020/05/11(月) 12:03:55.86
月1ぐらいで、実装&アルゴリズム重視の3H3〜4問コンテストみたいの
やってくれないかな JOIぐらいの実装の重さ、
ボス問題がレベル8ぐらいで
2020/05/11(月) 12:49:05.22
競プロの問題なんだから競プロ強い人が作ってれば十分
2020/05/11(月) 12:57:58.51
https://yukicoder.me/problems/no/995/editorial
こちらの解説にある「二項係数の定義を用いて変形する」の部分がわからないのですが、
どのように変形すれいいでしょうか？
2020/05/11(月) 13:18:48.39
二項係数の定義知ってる？
2020/05/11(月) 13:20:07.30
>>117
((1-p/q)+p/q)^K+((1-p/q)-p/q)^K
の第一項と第二項をそれぞれ二項定理を使って展開
2020/05/11(月) 13:20:47.01
nCk = (n * (n - 1) * ... * (n - k + 1)) / (k * (k - 1) * ... * 1)
ということくらいしか…
2020/05/11(月) 13:21:46.43
まあこの解説は「二項係数の定義」って言うより「二項定理」って言った方が親切かもしれんな
2020/05/11(月) 13:40:59.47
Σ_{j=0}^{floor(K/2)} _KC_{2j} * (1-p/q)^{K-2j} * (p/q)^{2j}
みたいにCの右側が2jなので、そのまま二項定理を適用しようとしてもうまくいきません…
どのように二項定理を適用すればいいでしょうか？
123仕様書無しさん
垢版 |
2020/05/11(月) 14:42:34.50
解説なんて読んでないが二幸係数の定義ってのはちょっと面白解説のたぐいだなw
パスカル三角に定義もくそもないしなそう次々と定義ぶっこんだら数学の理論体系早晩破綻する(´・ω・`)
2020/05/11(月) 14:43:28.07
>>122
>>119 の式を展開したら偶数の項だけ残らない？
2020/05/11(月) 19:46:13.25
青:優秀/黄:スーパー優秀/橙:天才/赤:怪物/冠:スーパースター
AtCoderの難しさに打ちのめされたわ、Chokudaiさんの各色に対する評価は正しかった
黄色で十分過ぎるぐらいに凄いわ,外から見てた時には分からなかった...
2020/05/11(月) 19:47:58.87
緑のぼくは？
2020/05/11(月) 19:51:51.14
頭悪い
2020/05/11(月) 19:53:20.45
酷い
競プロやめます
2020/05/11(月) 20:03:47.62
来週で黄色になるぞー
青でもすげーって言われるし黄色になったらめっちゃすごいと思われるんだろうな
2020/05/11(月) 20:04:22.28
>>128
俺は嫌な思いしてないから
それにお前が嫌な思いをしようが俺の知った事ではないわ
だって全員どうでもいい人間だし
大袈裟に言おうがお前が死んでもなんとも思わん
それはリアルでの繋がりがないから
つまりお前に対しての情などない
2020/05/11(月) 20:07:17.08
>>128
安心しろ
お前は天才だ
2020/05/11(月) 20:45:31.15
こどふぉとあっとこーだーの色の関係ってどれくらいある？
2020/05/11(月) 20:53:00.23
あっとこ赤のchokudaiがこどふぉ橙
2020/05/11(月) 20:58:38.83
それは英語が...
2020/05/11(月) 21:16:34.76
https://codeforces.com/blog/entry/70116
2020/05/11(月) 22:53:34.55
AtCoderは初期内部レート下がった影響あるから7ヶ月前より200くらい低く出るイメージ
2020/05/12(火) 08:05:38.69
ABC167-F,415人も解ける人いるのかよ
全く手がつかなかったんだが
黄色は遥かに遠いなあ(泣)
138仕様書無しさん
垢版 |
2020/05/12(火) 11:25:48.65
開始前に甘酒飲んでるんだけど脳みそに効果あると思う？
2020/05/12(火) 11:35:48.32
ルーティーンレベルの意味ならあるんじゃない
2020/05/12(火) 13:48:41.82
酒飲んだら悪い効果があるだろ
2020/05/12(火) 13:52:21.82
甘酒って酒か？
2020/05/12(火) 14:40:46.65
風呂入ったら高いパフォ出た！とか思ってたけど風呂にも入らず睡眠も十分じゃない状態でそれ以上のパフォ出たわ
コンディションより直前までにどれだけ演習積んでたかのが大事だった(体感)
2020/05/12(火) 15:16:05.54
まず得意問題が出るかがデカくて惑わされがちだけど、同じ問題セットならコンディション良い方が良いに決まってる
144仕様書無しさん
垢版 |
2020/05/12(火) 16:34:28.68
>>130
久々すぎて誰の発言だったかググってしまった
145仕様書無しさん
垢版 |
2020/05/12(火) 16:38:37.27
>>137
俺いつもFまで辿りつかないからなんとも言えないけど
これ単に各Siの(と)の個数を調べて(の数が多いやつから貪欲なんだよね？
解法の証明とか正当性の担保とかは抜きにすると、内容的にはDとかEで出てもおかしくない気もするけど、そんな難しい箇所があるの？
2020/05/12(火) 16:45:41.07
>>145
(
))))))))))))))((((((((((((((((
さあどうなる？
2020/05/12(火) 16:56:06.72
F問題はわかれば簡単だけどわからないと死ぬ
順位表のペナ数が物語る
実装は難しくないからやってみて
2020/05/12(火) 16:56:17.99
>>145
こういうそれっぽい貪欲がいくつも思いつくから証明しないとWAが大量に出るタイプの問題なんだと思う
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況