E問題をC++とPythonで解いてみました。ABC298は、2023年4月15日21:00に実施されました。紹介はこちらに、プログラミングの方針はこちらに記事があります。1341)問題はリンク先をご覧ください。Sugoroku確率DPです。ゴールから値を決めていきます。確率DPとして解いていきます。0のときは高橋君の手番、1のときは青木君の手番とし、高橋君の勝つ確率を表します。明らかに以下が成り立ちます(手番に関係なく高橋君が勝っています)。N-1)また以下も成立します(手番に関係なく青木君が勝っています)。N-1)確率を表す漸化式は、以下となります。1からPまでは同じ確率となるため、加えてからPで割っています。青木君の場合も同様です。プログラム例(ABC298E)考察した式をもとにプログラムを実装します。プログラムの補足です。すごろくはNを超えないため、Nを超えた場合はNとする。乗を求めています(フェルマーの小定理)。以下が、C++プログラムとなります。Library(ACL)を使ったプログラムも紹介します。コンテストで使えるライブラリです。計算することができます。AC(Accepted=正しいプログラム)と判定されました。求めることができます(16、20行目)。MODprint(dp[a][b][0])こちらも「AC」と判定されました。最後にこの問題は、漸化式が頭の中で納得できるまでに時間がかかりました。DPで確率(または期待値)を処理する問題は一定の頻度ででるため、手の内化できればと思います。問題を紹介していきます。コメントをキャンセルメールアドレスが公開されることはありません。付いている欄は必須項目です上に表示された文字を入力してください。Contest)記事一覧ソフトウェア技術者アナダパンチ組込み製品の開発に従事しているソフトウェア技術者です。仕事でソフトウェア開発に従事しながら、趣味でもプログラミングを楽しんでいます。