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

**仕様書無しさん** · 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/09(土) 00:49:57.06

テンプレ続き

# 高校生・大学生対象コンテスト
情報オリンピック https://www.ioi-jp.org/
ACM-ICPC http://icpc.iisf.or.jp/

# その他便利なサイト
コンテスト・カレンダー
https://competitiveprogramming.info/calendar
http://clist.by/
AtCoder Problems http://kenkoooo.com/atcoder/
オンライン整数列大辞典 https://oeis.org/?language=japanese
WolframAlpha https://www.wolframalpha.com/
Spaghetti Source
旧: http://www.prefield.com/algorithm/
新: https://github.com/spaghetti-source/algorithm
競技プログラミングwiki http://wikiwiki.jp/kyopro/
AOJ-ICPC http://aoj-icpc.ichyo.jp/
competitiveprogramming.info https://competitiveprogramming.info/
競プロSlack https://competitiveprogramming.info/slack
OnlineJudgeHelper (オンラインジャッジ補助スクリプト) https://github.com/nodchip/OnlineJudgeHelper
Google翻訳 https://translate.google.co.jp/

**仕様書無しさん** · 2020/05/09(土) 00:50:16.15

テンプレ続き

# 書籍
プログラミングコンテストチャレンジブック (蟻本)
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (AOJ本, TLE本, 渦巻本)
最強最速アルゴリズマー養成講座 (チーター本)

# 日本人競技プログラマ
Twitter 競技プログラマリスト
https://twitter.com/kinaba/lists/topcoder-jp
https://twitter.com/kobae964/lists/atcoder
TopCoder Single Round Match (SRM) のランキング
https://community.topcoder.com/tc?cc=392&;sc=&sd=&cc=392&module=AlgoRank&nr=200&sr=
TopCoder Marathon Match (MM) ランキング
https://community.topcoder.com/longcontest/stats/?module=CoderRank&;cc=392
Codeforces ランキング
http://codeforces.com/ratings/country/Japan
https://twitter.com/5chan_nel (5ch newer account)

**仕様書無しさん** · 2020/05/09(土) 00:51:10.10

**仕様書無しさん** · 2020/05/09(土) 00:51:30.09

テンプレ続き

# 関連スレ
【したらば】プロコン・競プロ・ハッカソン・CTFなどについて語り合う掲示板
https://jbbs.shitaraba.net/internet/13109/
TopCoder
https://mevius.5ch.net/test/read.cgi/tech/1333159918/l50
プログラミングのお題スレ Part9 [無断転載禁止]c2ch.net
https://mevius.5ch.net/test/read.cgi/tech/1480579110/
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3c2ch.net
https://mevius.5ch.net/test/read.cgi/tech/1466315249/l50
【会津】パソコン甲子園2004【若松】
https://mevius.5ch.net/test/read.cgi/tech/1094308951/l50
CTFについて語るスレ [無断転載禁止]c2ch.net
https://medaka.5ch.net/test/read.cgi/sec/1476430177/l50

>>1からここまでテンプレ

**仕様書無しさん** · 2020/05/09(土) 15:08:00.65

https://twitter.com/SameproJP
これって競プロやってんのdrken1215さんだけ？
https://twitter.com/5chan_nel (5ch newer account)

**仕様書無しさん** · 2020/05/09(土) 15:08:59.19

スレ立て乙

**仕様書無しさん** · 2020/05/09(土) 15:09:10.91

前スレから治安悪くなってきたな

**仕様書無しさん** · 2020/05/09(土) 15:13:17.81

頭悪い人を相手にする商売に自ら頭悪いと教えてあげたからな
さすがにお客さん怒っちゃうわ

**仕様書無しさん** · 2020/05/09(土) 15:14:50.77

「頭悪い」発言に切れてる人多いの？
俺は全く気にならなかったが
自分が言われたわけでもないし

**仕様書無しさん** · 2020/05/09(土) 15:25:23.49

>>1乙
できれば次スレからは>>1の1行目に
!extend:checked::1000:512
を挿入してもらいたい

**仕様書無しさん** · 2020/05/09(土) 15:25:55.42

自分が理解できないものを「天才向け」と言う方が喧嘩売ってるようなもんだと思うけどな

**仕様書無しさん** · 2020/05/09(土) 15:31:54.15

天才向けで解けなかったら天才ではないだけで、解けなかったら頭が悪い称号が付くのとどっちがいいか

**仕様書無しさん** · 2020/05/09(土) 15:36:19.01

内心でこいつ頭悪いとか思われながら教えられるのはきついな

**仕様書無しさん** · 2020/05/09(土) 15:57:36.71

ツイ消しされて確認できないだけかもしれないがそんなにひどい発言ある？
あ、慶応卒のchokudaiについて物凄い能力があるが受験適性は尋常じゃないくらい低い、
みたいに言ってたのは能力の偏りという趣旨にしてもなヤバいと思いました

**仕様書無しさん** · 2020/05/09(土) 15:59:04.95

前スレ終盤から頭悪いブーメランで草
どんだけ頭悪い奴いるんだ

**仕様書無しさん** · 2020/05/09(土) 16:09:39.71

こういうのはブーメランとは言わないでしょ

**仕様書無しさん** · 2020/05/09(土) 16:10:53.99

3月に発表して最近例の発言があり直後のオンライン化
さすがに擁護しようがない

**仕様書無しさん** · 2020/05/09(土) 16:13:38.97

来週からGCJR2, AGC, ARCと続くからしっかり精進しような

**仕様書無しさん** · 2020/05/09(土) 16:17:52.01

数学徒の方ばかり向きすぎ

**仕様書無しさん** · 2020/05/09(土) 16:23:00.97

人の商売なんて儲からなければ勝手に廃れるだけ
いつまでも粘着してるやつは頭悪い

**仕様書無しさん** · 2020/05/09(土) 16:46:01.96

何処ぞのオンラインサロンと変わらないな

**仕様書無しさん** · 2020/05/09(土) 16:54:17.22

頭悪い奴が頭悪い奴に教える地獄絵図

**仕様書無しさん** · 2020/05/09(土) 16:55:36.99

「天才向け」と勝手に決めつけることが「頭悪い」と言ってるんだと思うよ
まあ、売られた喧嘩に過剰に反応するのも良くないとは思うけど

**仕様書無しさん** · 2020/05/09(土) 17:03:54.90

俺赤でサークルの時にタダで教えてたんだけど、これから1回1000円ってギャグやっていい？

**仕様書無しさん** · 2020/05/09(土) 17:04:04.98

>>11
残念ながらこの板だと強制id非公開設定になるんだなこれが
移住しかないけどどうせここの人はしたがらないし受け入れ先もない

**仕様書無しさん** · 2020/05/09(土) 17:06:48.71

情報学板、数学板は？

**仕様書無しさん** · 2020/05/09(土) 17:09:58.16

学歴板でいいんじゃね

**仕様書無しさん** · 2020/05/09(土) 17:10:42.76

>>25
赤色の考え方を1回見れるなら安いな
1回5000円のプログラミング講座は高過ぎる

**仕様書無しさん** · 2020/05/09(土) 17:18:16.25

>>26
マジで？ソースある？

**仕様書無しさん** · 2020/05/09(土) 17:29:06.53

情報学板や数学板にあってもいいけど
競プロスレの本家はマ板やム板に絶対必要！

**仕様書無しさん** · 2020/05/09(土) 17:30:17.96

競技プログラミングやってて頭悪いって感じたことない天才ばっかなんすかねここは

**仕様書無しさん** · 2020/05/09(土) 17:35:35.93

急にどうした

**仕様書無しさん** · 2020/05/09(土) 17:48:34.88

読解力灰色コーダーでしょ

**仕様書無しさん** · 2020/05/09(土) 17:52:32.93

>>32
頭悪いか天才かの二択なんて小学生みたいな発送だな。
自分の実力で解けない問題があったところで、普通の人は今の自分には難しい問題だと思うだけだろ。

**仕様書無しさん** · 2020/05/09(土) 17:54:58.92

天才向けって何なら褒め言葉だったかもしれないのに
気難しい人だな

**仕様書無しさん** · 2020/05/09(土) 18:05:03.77

解説コンテンツが天才向けはどう読んでも褒め言葉じゃないだろ…

**仕様書無しさん** · 2020/05/09(土) 18:23:15.29

皮肉以外の受け取り方する方が不自然すぎる

**仕様書無しさん** · 2020/05/09(土) 18:26:05.18

id表記があろうがなかろうが大して変わらんと思うけどな
完全に匿名だと思い込んでひどい発言してると痛い目見るよ

**仕様書無しさん** · 2020/05/09(土) 18:33:41.24

そんな問題になるような酷い発言あるか？

**仕様書無しさん** · 2020/05/09(土) 18:40:27.70

暴言の類は無意識に読み飛ばす人間になってしまった

**仕様書無しさん** · 2020/05/09(土) 18:42:03.78

批判すら許されない空気になってほしいのかな、であればツイッタしてれば良いのでは

**仕様書無しさん** · 2020/05/09(土) 18:50:56.74

批判が許されない空気で治安が良くなるならその方が良い

**仕様書無しさん** · 2020/05/09(土) 18:54:31.25

批判するとファンネルに叩かれるツイの治安が良いかというと

**仕様書無しさん** · 2020/05/09(土) 18:59:32.22

ファンネルは全ミュートで気にせず批判すればいいのでは？

**仕様書無しさん** · 2020/05/09(土) 19:04:00.72

みんな治安が悪いのが好きなんか？

**仕様書無しさん** · 2020/05/09(土) 19:10:47.47

自分は治安がいい方が好み
twitterも5chもめんどくせー流れはスルーの精神で健康的
まあ火中の人間になったことがないだけかも知らんが

**仕様書無しさん** · 2020/05/09(土) 19:31:29.90

ここの場外戦、空中戦ばかりの僻みっぽく鬱屈した雰囲気はげんなりする
くだらない
ときどき相談や親切な回答を見ると掃き溜めに鶴に見える
idやワッチョイで糞コメントのカジュアルな連投が減るだけでも嬉しい

**仕様書無しさん** · 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)) が期待値でないなら、いったい何なのか？
というのがわからないです…

**仕様書無しさん** · 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)) はいったい何なのか？というのが気になります
これは期待値ではないのでしょうか？

**仕様書無しさん** · 2020/05/09(土) 21:03:27.22

通常攻撃と必殺攻撃を組み合わせるのが最適な場合もあるから,
その貪欲だと通らないってことか

**仕様書無しさん** · 2020/05/09(土) 21:05:50.73

>>61
期待値ではありません

**仕様書無しさん** · 2020/05/09(土) 21:06:11.14

min(X / A, X / (2 / 3 * B))

これ 2と3 逆では？