ABC194 反省

もう何もかもがダメ。嫌な気持ちになりすぎて昨日精進する気がおきませんでした。

最近調子が上向いていたので、悲しいです。

A問題 I Scream

よく読んでif文を書けという問題。地味に誤読しました。サンプルありがとう。

B問題 Job Assignment

なので二重ループを回せばおしまいです。

C問題 Squared Error

灰色diffってマジ？？？？？？？？？？

あー であることを利用するのか。まったく思いつきませんでした。確かにね。

式変形してホイだけど、地味に実装バグらせて悲しかった。

D問題

問題の問題。いやこれ緑diffってマジです？？何も信じられません。下位層のレベル上がりすぎ。

とりあえず期待値は期待値DPだと思ってうんうん唸ったものの、まあ解けず。

反省として、なにやら上手い式をひねり出すのに固執していたことが悪かったですね。僕の実力でそんなにうまいこと行くわけないのです。

そもそも実質的には全ての頂点を選ぶまでの期待値なので、「サイコロ 全ての目が出る 期待値」とか検索すればよかったです。
これは見えるべきでした。というか見えていたのに、シンプルな問題に換言できませんでした。

取り組んでいる複雑な問題を、明らかに単純そうな問題、或いは明らかに既出な問題に落とし込むのは競プロの基本なので、これが出来なかったのは大反省ですね。

何をすればいいかわからず、視野狭窄な状態になっていたのが最大の敗因でしょう。これは「何をすればいいか分からなくなったときの定石」みたいなものを持っておく必要がありますね。

今までは「単純な問題に切り分けて考えてみる」しか選択肢を持っていなかったのですが、「元の問題の言い換えを考える」ことも意識していきたいです。

さて、「望みの出目が来るまでサイコロを振る期待値は、その出目が出る確率の逆数になる」という有名事実があるらしいです。せめてこのあとは自力で行きたいですね。

出来ませんでした。なるほどここでDP的な考え方を使うのか.......いや難しすぎる。純粋な論理の難しさなら明らかに水色diff以上はあると思います。

残りi個の頂点を選ぶときの期待値と置きます。

ここで「まだ選ばれていない個の頂点から一つ選ばれる」時の期待値はです。

よってと表せて、これが答えです。

https://kimiyuki.net/blog/2016/04/28/dice-and-expected-value/

上記サイトを参考にしました。

E問題 Mex Min

地獄みたいに苦しんだんですが、最初に提出したコードのインデックスを正しいものに変えると2WAまで減って、今持っている数列に番兵入れると全部通りました。敗因はインデックスをきちんとあわせなかったことです。ちゃんと図を書いて確認して実装すればこんなことには.....(10WA)

F問題 Digits Paradise in Hexadecimal

んー何かよくある桁DPなんですが、種類というのが面倒そう？

dp[i][j][l] := 桁目まで見て、でN未満か以下かをフラグとして持って、でその数を含んでいるかどうかを[{2}^{k}]の集合で管理したdpみたいなものをとりあえず考えてみます。

うーん、その数を含んでいるかどうか、というのがの状態を必要としていて、これをどうにかする必要がありそうです。え、こんなの解けるんですか？という気持ちになるので解説を見ると、解けることが分かります(完)

今まで自分が持っていた桁DPのレパートリーにはない考え方を用いて解く必要がありました。解けなかった原因はそこにあります。

今まで自分が理解していた考え方としては、この神記事で紹介されているような「一文字ずつ各桁を決めていく」やり方でした。

普通はこの考え方でうまくいくんですが、今回の場合一文字ずつ決めていくと集合を持つ必要が出てきて、ダメなんですね。

こういうときは自前で新しい遷移を組むしかないので、考えます。

ひとまず、dp[i][j] := 桁目まで見て、種類の数を含んでいる以下の数と扱います。

定石として、leading zeroやlessフラグが真である状態での遷移を考えてみます。

場合分けして考えます。もし桁目に今までに使われていない数が使われた場合の数は

dp[i+1][j+1] += dp[i][j] * (16 - j)

です。同様に、桁目に今までに使われた数を持ってくる場合の数は

dp[i+1][j] += dp[i][j] * j

です。

前者の場合の妥当性ですが、まずleading zeroやlessフラグが常に真である状態を考えているため、桁目には今まで使われていない数であれば何を持ってきても良いです。
そして、dp[i][j]までは既に数えられているので、純粋に末尾に何をくっつけるか？ということのみ考えれば良いです。

よって、dp[i+1][j+1] += dp[i][j] * (16 - j)として状態をまとめられます。

後者の場合も同様です。

さて、これはleading zeroやlessフラグが常に真である状態を考えていたので、次にlessフラグが偽であるときを考えます。

これはまあlessフラグが偽である = とまるきり同じである

ということを意味しているので、適当に今まで出てきた数を管理しておけば

dp[i+1][今の種類数 + 1] +=

dp[i+1][今の種類数] +=

となります。ここで

[tex A := ] 今まで使われておらず、よりも真に小さいものの数

[tex B := ] 今までに使われていて、よりも真に小さいものの数

となります。leading zeroについては、与えられる文字列にleading zeroはないことから考えなくて良いです。

最後にleading zeroですが、今まで全部ゼロで、桁目に初めてゼロ以外が出るという話になります。また、今まで全部ゼロなので、自明に より小さい状態です。

よって dp[i+1][1] += 15 となります。

以上、全ての遷移パターンを網羅できたので、実装するとACになります。