B問題も少し難しかったのでそちらも備忘録。色々あって（コンテストは数ヶ月前）ところどころ何があったか忘れてるかも。
B問題
6面サイコロ3つを振り、「4」「5」「6」の目が一つずつ出る確率を誤差10-6以下で出力。
しかも6面に書かれる目は指定される。制約で1以上6以下。
出目の通り数は6×6×6=216通りしかないので、全探索すればよい。
解き方は色々あるが、筆者は456を並び替えた全6通りと合致するかを比較し、確率を算出した。
C問題
同じ文字が隣り合わないものの個数を数え上げ、998244353で割った余りを出力する。
尺取法を使うことで解ける。
尺取法の中の処理は、文字列の長さをnとして三角数様に増えていくので計算は楽。組み合わせを考えたりしなくていいし。
あとは同じ文字が隣り合う状況を回避するように実装すればよい。
尺取法で実装する上での細かい注意点は別の記事で。
与えられる文字列Sの末尾にテキトーな（制約上ありえない）文字を追加すると、尺取法の終了判定と計算などが簡潔に済む。
感想
B問題、問題文を読み、これ計算できんの……？ と戦慄したが、全探索すれば簡単ということに気付くまでにまあまあの時間を要した。
C問題、解法はあっていたが、WAの原因が時間内に分からずAB2完。原因は制約上の考慮漏れ、計算中の算術オーバーフローといういつものミス。C#では数値のオーバーフローは例外をスローしないのがデフォルトの仕様となっている。（ｎ敗）
コメント