AtCoder World Tour Finals 2019 E eを解いたのでメモ

こんにちは。

AtCoder World Tour Finals 2019のE問題である「e」をACしたので、解説と違う解き方をした部分を書き残しておきます。（まあ本質は一緒だと思いますが）

問題はこれ↓

https://atcoder.jp/contests/wtf19-open/tasks/wtf19_e

 

大まかな考え方や流れは公式解説と同じなので省きます。なので先にそちらを見ないと何のこっちゃだと思います。

DP部分が解説を見てもよく分からなくて唸っていたら自分なりの方法で何とかできたのでそこの部分を紹介します。

 

公式解説のDPは

dp[i][j][k][l] = 「X_i=xのとき、sのi番目まで条件を満たす確率、ただしj,k,lに応じた条件も付く」

というものでした。（正確にはdp[i][j][k][l](x)ですが(x)は省略して書きます）

 

考えた結果、添え字がiのみでDPが組めたので、以下で説明します。

簡単のため、sの両端は’X’（すなわち人が座る）とします。

dp[i] = 「X_i=xのとき、sのi人目（左から数えてi番目の’X’）まで条件を満たす確率」

とします。（0-indexedです）

まず、dp[0]=e^(-x)です。

 

dp[i]からdp[i+1]を求める時には次のようにします。

i人目と(i+1)人目の間の空席が1または2でないと確率は0となることに注意して下さい。

間の空席が1の時

X-X

のようになっています。

それぞれの確率変数をX_j, X_{j+1}, X_{j+2}とおくと、あり得る大小関係は

X_j < X_{j+1} < X_{j+2}

X_j < X_{j+1} > X_{j+2}

X_j > X_{j+1} > X_{j+2}

の3つです。（X_j > X_{j+1} < X_{j+2} だとj+1番目の席に人が座ってしまいます）

よって、dp[i+1]は

「dp[i]を<<の順で積分したもの」、「dp[i]を<>の順で積分したもの」、「dp[i]を>>の順で積分したもの」

の和となります。

ただし、「<で積分」と言ったら f(x) を ∫[0 to x]f(y)dy に、「>で積分」と言ったら f(x) を ∫[x to 1]f(y)dy にする操作だと思って下さい。

 

間の空席が2の時

X--X

のようになっています。

それぞれの確率変数をX_j, X_{j+1}, X_{j+2}, X_{j+3}とおくと、あり得る大小関係は

X_j < X_{j+1} < X_{j+2} > X_{j+3}

X_j < X_{j+1} > X_{j+2} > X_{j+3}

の2つです。（X_j > X_{j+1} と仮定するとj席目に人が座るためにはj+2席目に人が座らなければならず、矛盾します。他も同様。）

よって、dp[i+1]は

「dp[i]を<<>の順で積分したもの」、「dp[i]を<>>の順で積分したもの」

の和となります。

 

これらが連なった時も上手くいってるのか？と思ってしまいますが、上記の大小関係を満たしていればいくつ連なっていても目標の席配置になることが分かります。

 

この遷移によってdp[k]（右端に座る人をk人目とした）を求め、それにe^(-x)をかけて0から1まで積分すれば答えが求まります。（私は部分積分を実装しました）

 

さて、先ほど両端に人が座ると仮定しましたが、そうでない場合はどうすればよいでしょうか？

実はうまく両端に文字を追加することで解決できます。

例えばs="X--X-"だったとします。

この時、s1="X--X-X"とs2="X--X--X"について問題を解き、それらを足すことで元のsに対する答えが求まります。

実装においては、先頭に付ける候補"X", "X-", "X--"と末尾に付ける候補"X", "-X", "--X"の組み合わせを全て試して足し合わせることで場合分けをなくすことができます。

 

実際の提出はこれ↓（見せる用に書いたわけではないので参考程度に…）

https://atcoder.jp/contests/wtf19-open/submissions/10927232

 

終わり

数式の、書き方が、分からない。

この下手な説明で理解できる人は普通に公式解説を理解できると思います。

【MHWI】闘技大会はいいぞ【MHWアイスボーン】

MHWアイスボーン MHWI 闘技大会

こんにちは。

皆様、MHWアイスボーン（モンスターハンターアイスボーン）やっておられるでしょうか？

本日はMHWアイスボーンのコンテンツの1つである、闘技大会について語りたいと思います。

勢いで書いたので、イタい文章になっているかもしれません。

 

そもそも闘技大会って？

闘技大会とは、集会エリアの受付嬢（左）から受注することのできる特殊なクエストで、

  • フィールドは闘技場
  • 装備とアイテムのセットは用意された5種類から選ぶ
  • 参加人数が2人まで
  • 参加人数によらずモンスターの強さは一定
  • 8回まで力尽きられる
  • クリアタイムに応じてSランク・Aランク・Bランクの評価が得られる
  • クリアタイムは早い方から5つギルドカードに記録される
といった特徴があります。

常設されている闘技大会クエストはMHWからの9個と、アイスボーンで追加された7個があります。

 

闘技大会の現状

さて、私は闘技大会が好きで、よく野良闘技大会部屋に入ったり、無ければ自分で作ったりしています。

しかしこの闘技大会、面白いにもかかわらず非常に過疎っています。

MHWアイスボーンのサーバーの仕組みはよく分からないですが、私のプレイする時間帯ですと検索して出てくる闘技大会部屋は多くて3つ（そして高確率で機能していない）、少ないと0です。

 

なぜ野良闘技大会部屋がこんなに過疎っているのか考えたところ、大きな原因は以下なのではないかと思いました。

  • 闘技大会の面白さに気づいてない人が多い
  • 闘技大会ガチ勢は固定メンバーで遊んでいる

こういった現状を少しでも打破しようと、この記事では闘技大会の面白さとタイムに関する考え方を紹介します。（まあこんな記事誰も見てないと思いますが、思い立ったので書いています）

 

軽い自己紹介？

で、おまえはガチ勢なのかという問いに答えると、エンジョイ勢です。

モンハンは大好きですが上手くはありません。（具体的にはソロSランクは取ったことがありません）

通常クエストでは生存スキルを積んでいます。

そんな感じです。

 

闘技大会の魅力

では話を戻して、闘技大会をあまりやらない人に「やってみよう」と思ってもらうことを目的として、闘技大会の面白さを語っていきます。

（一応言っておくと、私は通常のクエストも普通に楽しんでプレイしています）

 

  • 準備不要

闘技大会では装備・アイテムが固定で食事効果もないので何の準備もなくクエストに行くことができます。

また、通常クエストにおいて、ネット上で「○○のスキルがついてない奴は蹴る」とか息巻いてる人もいます。怖いですよね。

しかし闘技大会では装備固定。そんなことを気にする必要はないのです！

 

  • 相方との絆ができる

参加人数が2人までというのは賛否あると思うのですが、いいところを挙げるとするとこれでしょうか。

友達が1人しかいない人にはうってつけですし、野良で組んだ人ともクエストを回していくうちに親近感を覚えます。フレンドが欲しい人もおすすめです。

 

  • アクション部分のみを抽出している

モンスターハンターというゲームは「ハンティングアクション」というジャンルに属しているそうです。その中でも「アクション」の部分を取り出したのが闘技大会だと思っています。「ハンティング」の部分にあたる素材集めは目的のものが手に入ればやることがなくなってしまいます。一方「アクション」部分にはゴールがありません。

そう考えると、闘技大会はモンハンの構成要素のかなりの部分を占める「真のエンドコンテンツ」であると言えます。

また闘技大会をやると、ゴリ押ししていると気が付かないようなモンスターのモーションなども分かるようになり、モンハン全体を更に楽しめるようになります。

 

  • 「装備固定」それはすなわち「土俵は同じ」

動画サイトなどで通常クエストのTA(タイムアタック)動画を見る人も多いと思います。

私もよく見るのですが、「すげー」「うめー」と感じると同時に、こう思うのです。「でも自分がプレイするときは、（装備の関係上）こんなにダメージ出ないし都合よく怯みもしないから、参考にはならない」と。

これは立ち回りで競うのが目的のTA wiki rulesでも同じです。（再度言いますが、私はよくTA動画を見ますし、すごいとも感じます）

しかしながら！闘技大会では！！装備が固定なので！！！動画の動きを「目指せる」のです！！！！

通常クエストでTAの動きや装備を真似しようものなら3乙が関の山。一方闘技大会のTAは立ち回りを真似してもいい、いや、真似することがいいことなのです！

そしてこれは人それぞれかもしれませんが、MHWアイスボーンの環境下では、闘技大会ソロの動画が一番見ていて面白いと感じます。

 

  • 普段使わない武器を使うきっかけになる

最近のモンハンはどの武器も操作が複雑で、なかなか新しい武器種を試そうと思いません。

しかし闘技大会では5種類しか選べる武器がないので、普段使わない武器を使わざるを得なかったりします。

始めは「なんで○○（普段使う武器）が用意されてないんだよう」とか思うのですが、そのうち「この武器、結構楽しいぞ」となることでしょう。

 

  • タイムを更新すると嬉しい

TA動画を上げているような人たちはなぜTAをやっているのでしょうか。

それはやはりタイムを更新したりライバルに勝ったりするのが楽しいからだと思われます。

通常のクエストは素材を得ることが目的のため、多くのプレイヤーはTAをしようと思いません。

しかし闘技大会はTAが目的です。自信を持ってTA勢の楽しみを味わえるのです！

 

とまあ闘技大会の魅力をいろいろ語ってみたので、1人でも闘技大会好きが増えると嬉しいです。

あ、注意点として、ソロはなかなか大変なので基本的には2人でクエストに行くといいと思います。

それから、MHWから存在するクエストはMHW時代の仕様を想定して作られていたり、始めから2頭同時のクソゲーだったりするので、マスターランクの方をおすすめしておきます。

 

闘技大会の記録の捉え方

ではここからは「闘技大会の記録の捉え方」について書きます。

闘技大会をある程度やっていると、タイムが煮詰まってきます。

そうなると野良での記録更新は絶望的なので、ガチ勢はガチ勢同士でペアを組むようになり、結局野良闘技大会部屋は賑わいません。

これは多くの人が、闘技大会の記録は「クエストに対して自分と相方が出すもの」と考えるからです。

しかし私は少し違う考え方をしています。

それは、闘技大会の記録は「クエストと相方に対して自分が出すもの」という考えです。

違いが分かるでしょうか？

後者は（クエスト, 相方）の組をある種のクエストとみなしているのです。

 

例を挙げてみます。

慣れている人同士でペアを組むと、Sランクは安定して取れます。

さて、あなたが野良で相方を募ってクエストに行ったところ、Sランクが取れなかったとします。

前者の考えだと「相方が下手だから不甲斐ない記録になった」と思ってしまいます。

後者の考えだと、あなたの記録と比べることは意味も持ちません。重要なのは相方のギルドカードに載っている記録です。もし一番上の記録があなたとのものならば、あなたは（クエスト, 相方）の組に対する世界記録保持者です。もしあなたではないAさんとの記録が一番上にあれば、あなたはAさんよりも下手というわけです。

 

なんとなく気持ちが伝わったでしょうか…？

この考えによって、私は記録の更新という楽しみを野良でも味わい続けているのです。

記録の確認のためにギルドカードをもらう必要がありますが、2,3回クエストに行った後にこちらから渡せばほとんどの人は返してくれます。

みんながこの考えなら野良闘技大会部屋は賑わい、コインが集まらなくて苦しむ人も減るのになぁーと思います。

 

妄想

何のことはない、妄想です。チラシの裏とも言います。（まあこの記事全体がチラシの裏みたいなものですが…）

モンハンシリーズがこれからも続くならば、闘技大会をおまけのコンテンツではなくメインのエンドコンテンツにしてほしいと思います。

完封できるようなクエストがあってもいいですが、やっぱり立ち回りで競う方が「闘技大会」って感じがします。つまり、罠・落石・撃龍槍・ぶっ飛ばしは無くていいと思っています。

あと2頭同時は運ゲー過ぎるのでやめてほしいかな…

まあこれらのことは明日には違う考えになってるかも…

 

終わり

それでは野良闘技大会部屋で待っています。

AtCoder ProblemsのLongest Streakが1000になったのでそれについて書く

AtCoder 競技プログラミング

こんにちは。

abc050というIDでAtCoderをやっている者です。

東京工業大学の修士1年もやっています。（もうすぐ修士2年になるけど）

ブログを書くのは初めてなので、間違いや改善点があったら教えて下さい。（誤字脱字、個人情報が漏れてる、文章が読みずらい、など）

 

 

AtCoder ProblemsのLongest Streakとは

既に知っているかもしれませんが、タイトルに出てきた用語の説明をしておきます。

AtCoderとは、競技プログラミングのコンテストを開催している日本最大の企業およびそのサービスのことです。

AtCoder Problemsとは、AtCoder上の問題が見やすく掲載されているサイトです。AtCoderのIDを入力すると、その人が今までにどの問題を解いたか、などの情報も見ることができます。

AtCoder ProblemsのStreakとは、AtCoder上の問題を何日連続で解いたかを表す値です。AtCoder ProblemsのUser Pageから確認できます。注意点として、既に解いたことのある問題を再度解いてもこの値は変動しません。

AtCoder ProblemsのLongest Streakとは、AtCoder ProblemsのStreakの最大値です。

 

 

ここでようやくタイトルに戻りますが、本日2020年3月16日に、AtCoder ProblemsのLongest Streakが1000になりました。

 

言い換えると、1000日間AtCoderの問題を被りなく解き続けた、ということになります。

何の根拠もありませんが、この記録はあと半年は抜かれない気がしています。

1000は十進法でキリがいいことに気づいたので、（需要はさておき）ブログを書くことにしました。

というわけで（？）、Streakを続けることの利点と欠点について感じたことを書き並べてみます。

 

Streakを続けることの利点

  • 問題を解く習慣がつく

最大の利点はこれだと思います。

僕は、AtCoderの問題を解くのは好きだけど、解こうという気になるまでに時間がかかる、という人間なのでStreakを続けることで解く問題量が増えて実力も上がったと確信しています。

競技プログラミングを始めてみたけど何をしよう…という人にも「とりあえず毎日問題を解く」のは良い目標なのではないでしょうか。

 

Streakを続けることの欠点

  • Streakを意識し過ぎて、1日に2問以上解ける時も1問づつ解いてしまう

おそらくこれが1番の欠点です。Streakを本気で最大化しようとすると、解けている問題が複数問あっても1日ずつ提出することになります。

これは1日2問以上コンスタントに解く人にとっては足枷となります。

一応、「普段は問題をバンバン解いて、1問も解いていない日だけStreakを気にする」ことができれば欠点にはなりません。

ちなみに僕はStreakを続けていなかったら平均1日1問未満しか解かないので、この欠点はあまり気になりませんでした。

また、この「提出を先延ばしにする」行為は意外と悪いことばかりではなく、「いざ提出したらWA」を防ぐために解法の正当性を証明するようになる、提出デバッグができないのでちゃんと考えて正確なコードを書くようになる、問題を脳内に入れている時間が長いので記憶に残る、といった利点もあったりします。

  • AtCoderの問題ばかり解いてしまう

AtCoderのStreakを伸ばそうとすると、他のコンテストサイトの問題を解く暇があったらAtCoderの問題を解こう、という考えになります。ICPCやCodeforcesで結果を残したい人にとっては欠点になり得ます。（1日に2問以上解き続ける人にとっては関係ない話かもしれません）

ちなみに僕はAtCoder以外はあまり熱心でないので、この欠点は気になりませんでした。

 

たまに「Streakを意識すると自明埋め（自分にとって簡単な問題を解くこと）ばっかりしてしまう」という意見を見ますが、僕の考えだと、緊急時にStreakをつなぐために簡単な問題は残しておきたいので、普段は難しい問題を積極的に解く気がします。

 

Q&A的な何か

残りはよくある質問とそれに対する回答を書きます。

 

Q.結局Streakを伸ばすのはおすすめ？

次のような人にはおすすめです。

  • 指標がなければ問題を解くのが1日1問未満の人
  • Streakにとらわれ過ぎず、1日に複数問解くことができる人
  • 競技Longest Streakをやっている人

 

Q.Streak Rankingが全然上がらなくてつまらないんだけど、Streak切ってくれない？

Streakはあくまで自己満足であり、Rankingは（自力で順位を上げるのが不可能という意味で）不毛なので、あまり気にしない方がいいです。

まあ確かに、始めたのがちょっと早かったという理由だけでずっと1位にいるのも申し訳ないので、今から24時間は問題を解かないことにします。

 

Q.Streakとレートって相関あるの？

分かりませんが、客観的事実としてStreak 1000以上の人は全員、橙以上経験者です。

（これは冗談なので、黄以下でStreak 1000を達成する人がいたとしても負の感情は全く抱きません）

真面目なことを言うと、何もなくても平均で1日に何問も解くような人に関してはStreakとレートはあまり関係ない気もします。

1つ言えるのは、僕は特に「精進」をしたことがないけど、Streakを続けていたら橙まで到達できた、ということです。

 

Q.Streakを続けるのって精神的に辛くない？

僕は辛いと感じたことはありません。面白そうな問題ばかり解いてるのもありますが…

辛いと感じたら気軽にやめていいと思いますよ。

 

Q.俺はStreakに意味がないと思っているので、Streakをアピールされるとイライラするんだが？

そういう人がいることは理解しています。ブロックなりミュートなりして下さい。

ちなみに、僕は他の人の「Streak○○日達成しました！」というブログやツイートを見るのは好きです。

 

Q.俺はLongest Streak 15でレート4111だけど、君は？

Longest Streak 1000でレート2414です。

どなたか存じ上げませんが、1勝1敗で引き分けですね。

 

Q.好きな問題を教えて！

いくつか挙げると、

https://atcoder.jp/contests/dwacon2018-final/tasks/dwacon2018_final_d

https://atcoder.jp/contests/jsc2019-final/tasks/jsc2019_final_a

https://atcoder.jp/contests/agc032/tasks/agc032_d

https://atcoder.jp/contests/agc017/tasks/agc017_d

https://atcoder.jp/contests/arc070/tasks/arc070_d

です。

自力で解けたものは1つもありません。

 

Q.「好きな問題教えて！」なんて本当に聞かれたの？

聞かれていません。

僕自身が他の人がどんな問題が好きか気になるので、とりあえず自分から言ってみただけです。

 

こんなところでしょうか。

ここに書いたことは僕個人の（現在の）考えなので、「そこは違うよ」「こういう考えもあるよ」などの意見は大歓迎です。（反応するとは限りませんが）

 

終わり

終わりです。

最後に、AtCoder社とkenkooooさんに感謝！

 

せっかくブログを作ったし、他の記事も書いてみようかなぁ