競技プログラミングにハマるプログラマのスレ 25
■ このスレッドは過去ログ倉庫に格納されています
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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/ テンプレ続き
# 書籍
プログラミングコンテストチャレンジブック (蟻本)
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (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) 頭悪い人を相手にする商売に自ら頭悪いと教えてあげたからな
さすがにお客さん怒っちゃうわ 「頭悪い」発言に切れてる人多いの？
俺は全く気にならなかったが
自分が言われたわけでもないし >>1乙
できれば次スレからは>>1の1行目に
!extend:checked::1000:512
を挿入してもらいたい 自分が理解できないものを「天才向け」と言う方が喧嘩売ってるようなもんだと思うけどな 天才向けで解けなかったら天才ではないだけで、解けなかったら頭が悪い称号が付くのとどっちがいいか 内心でこいつ頭悪いとか思われながら教えられるのはきついな ツイ消しされて確認できないだけかもしれないがそんなにひどい発言ある？
あ、慶応卒のchokudaiについて物凄い能力があるが受験適性は尋常じゃないくらい低い、
みたいに言ってたのは能力の偏りという趣旨にしてもなヤバいと思いました 前スレ終盤から頭悪いブーメランで草
どんだけ頭悪い奴いるんだ 3月に発表して最近例の発言があり直後のオンライン化
さすがに擁護しようがない 来週からGCJR2, AGC, ARCと続くからしっかり精進しような 人の商売なんて儲からなければ勝手に廃れるだけ
いつまでも粘着してるやつは頭悪い 「天才向け」と勝手に決めつけることが「頭悪い」と言ってるんだと思うよ
まあ、売られた喧嘩に過剰に反応するのも良くないとは思うけど 俺赤でサークルの時にタダで教えてたんだけど、これから1回1000円ってギャグやっていい？ >>11
残念ながらこの板だと強制id非公開設定になるんだなこれが
移住しかないけどどうせここの人はしたがらないし受け入れ先もない >>25
赤色の考え方を1回見れるなら安いな
1回5000円のプログラミング講座は高過ぎる 情報学板や数学板にあってもいいけど
競プロスレの本家はマ板やム板に絶対必要！ 競技プログラミングやってて頭悪いって感じたことない天才ばっかなんすかねここは >>32
頭悪いか天才かの二択なんて小学生みたいな発送だな。
自分の実力で解けない問題があったところで、普通の人は今の自分には難しい問題だと思うだけだろ。 天才向けって何なら褒め言葉だったかもしれないのに
気難しい人だな 解説コンテンツが天才向けはどう読んでも褒め言葉じゃないだろ… id表記があろうがなかろうが大して変わらんと思うけどな
完全に匿名だと思い込んでひどい発言してると痛い目見るよ 批判すら許されない空気になってほしいのかな、であればツイッタしてれば良いのでは 批判が許されない空気で治安が良くなるならその方が良い 批判するとファンネルに叩かれるツイの治安が良いかというと ファンネルは全ミュートで気にせず批判すればいいのでは？ 自分は治安がいい方が好み
twitterも5chもめんどくせー流れはスルーの精神で健康的
まあ火中の人間になったことがないだけかも知らんが ここの場外戦、空中戦ばかりの僻みっぽく鬱屈した雰囲気はげんなりする
くだらない
ときどき相談や親切な回答を見ると掃き溜めに鶴に見える
idやワッチョイで糞コメントのカジュアルな連投が減るだけでも嬉しい 最近競プロ初めてあまり精進せずに緑はいけそうだけど、
水色って競プロ民にはどういう評価？ 200問くらいといて緑なんですけどどう思いますか？ 以下の問題について質問です
【問題】
敵の体力は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)) では期待値が正しく求められないのでしょうか？
どこが間違っているかわからないため質問いたしました
回答よろしくお願いします 私の求めた min(X / A, X / (2 / 3 * B)) が期待値でないなら、いったい何なのか？
というのがわからないです… X=101, A=1, B=100のときの最善手は...？ >>59
必殺攻撃が1度でも当たれば通常攻撃1回、が最善手ですかね…
そう考えると、確かに期待値2.5回が正しそうだなという感じがしますが、
そうなると min(X / A, X / (2 / 3 * B)) はいったい何なのか？というのが気になります
これは期待値ではないのでしょうか？ 通常攻撃と必殺攻撃を組み合わせるのが最適な場合もあるから,
その貪欲だと通らないってことか min(X / A, X / (2 / 3 * B))
これ 2と3 逆では？ >>64
一回の必殺攻撃で減らせる体力の期待値は 2/3*B だからあってるんじゃないの？ >>61
その値に意味はないんだけど、なぜ意味がないかを考察したいならX=1, A=1億, B=100の場合で考えてみたらいい 蟻本p.123 Millionaireが近いことを説明してる気がする >>67
代入してみると、なんとなく意味のない値だということが理解できました
回答ありがとうございました 無意味ってことはないな
Xを無限に大きくしたときの近似値ではある 期待値難しいね. 俺も最初の解法何が間違ってるのか分からなかった
数学の教科書読み直そうかな 減る体力の期待値と回数の期待値をごっちゃにして考えたのがいけなかったのかもしれません 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は回数の期待値としては変わらないはずです。 >>55
お前さんの答えでは、通常攻撃のみ、または必殺攻撃のみのケースしか考慮してない。
例えば途中までは必殺攻撃を連発した方が効率的に体力を減らせたとして、残り体力がA以下になったなら、外れる可能性のある必殺攻撃を使うのは最適な攻撃でないから通常攻撃を選択しなければならない。 CodeforcesのDiv4というのに出てみたいんですが、参加経験が1度しかないです
rateが変わらないだけで普通に参加はできるのでしょうか？ コドフォ出るなら CF-Predictor っていうブラウザ拡張入れるのおすすめ 問題が理解できません
AtCoder Beginner Contest 087C
＞ 左上および右下のマスにもアメが置かれており、あなたはこれらのマスに置かれているアメも回収します。
移動先マスとその左上・右下の3か所からアメを回収できると思うのですが、
回答例だと移動先マスしか集計していません
上記の記述はどういう意味なんでしょうか？ > 左上および右下のマスにもアメが置かれており、あなたはこれらのマスに置かれているアメも回収します。
(1,1) ,(2,N)のアメも回収するということ。
書き方があいまいだと思うけど、問題文には移動中のマスの左上および右下のマスとは書いていない。
入出力例から察して。 いや問題文に左上のマス＝(1.1)、右下のマス＝(2,N)と書いてあるわ。
書き方があいまいとか言ってすみません。 >>84
開始と終了の地点って意味だったんですね
ありがとうございます！ めんどくさいから質問するならリンクを貼って欲しいな testcase -> 玉
multi testcase -> 箱 と読み替えて
大きさ M_i (1 <= i <= n, 1 <= M_i <= k) の玉があります
玉を箱に詰めようと思ってます
一つの箱に入れられる玉には条件があります
条件: サイズ j (1 <= j <= k) 以上の玉はC_j 個までしか入れることができない
全ての玉を箱に入れるために必要な箱の最小数とそのときの玉の配置を求めてください Codeforceって初期レート1500なんですか？ >>88
ありがとうございます！
コンテスト中はさっぱり理解できなかったですがこれで解き直せます！ コドフォ1回しか参加してないのに昨日のratedになってた
よくわからん もしAtCoder社が、解説の公開を2年も完全放置していたら、
ユーザーからのクレームで大変な思いをするだろうに、
某公立大学は呑気でいいですねえ
さぞかし「仕事」が捗るんでしょうなあ! なんか某社長の発言的に今日のABCも負荷でおじゃんになるのかしら 15000まで大丈夫って言ってて今回は15000行きそうにないんだからおじゃんにはならないだろ 無課金ユーザーは高負荷時にキックされるようにすればいいのでは？ 最高パフォ更新は気持ちいいなあ
AGCARCまでに黄色になりたいねえ >>99
マイプロフィール＞直近のコンテスト成績証＞ツイッターアイコン ■ このスレッドは過去ログ倉庫に格納されています
