第6回 ドワンゴからの挑戦状 予選

　AとBはそこそこ早く解けたものの、それ以後何もできずに終了。主にCを考えていたけど、Dを考えた方が良かったか。とりあえず、黄色維持には成功しました。

コンテストへのリンク

A - Falling Asleep

　実装問題

B - Fusing Slimes

　期待値系の問題。ABC150のEやABC151のEと似た考え方で解ける。

　このときはABC150のEの復習が済んでおらず、問題を見たとき、「そのせいで解けなかったらどうしよう」と焦った。それより簡単な問題だった（と思う）ので助かった。

C - Cookie Distribution

・かけ算のままでは扱いにくいのでどうするか。

　コンテスト中はあまり良い方法が思いつかず、logを取ったらどうだろう？　などと考えてしまったが、和と積が混じった式なので当然上手くいかない。

　解説動画のように、積を場合の数へ言い換えるのがポイントで、DPに帰着できる。maspyさんのブログを見ると、式計算でもできるようだけど、結構テクニカルに見えてしまう……。

　とりあえず、

・積を場合の数へ言い換えできることがある

　を頭に入れておきます。

D - Arrangement

　コンテスト後に考えたとき、解法ツイートが目に入っていたこともあって、ダメなパターンが、

1.（入力例2のように）残り二個で互いが互いを禁止している場合

　と、

2. 残っている数字のうちにaがあって、X以外の全ての数字が、Xを禁止している場合（は、まずXを選択しないとハマる）

　なことは分かった。厳密な証明は難しくても、ちゃんと考えればここまでは辿りつけそう。

　だけど、その後の実装も結構難しいと思う。

　私は、まず、リストAの各要素の出現回数をカウントしたもの（PythonだとCounter(A)）をリストでもち、heapqにそれらの(カウント数, index)という組を入れて、最大値を管理しました。

　出現回数をカウントしたリストは常に更新していきます。

　なので、heapqで出てきた最大値がMでそれを取る要素がxとなっているけど、それがリストと異なっているときは、リストの方が正しいので、一度heapqから抜き、正しい値をheapqに入れ直します。

　それでも、2.の条件に抵触した場合に限り、2.の条件を適応（つまり、次をXにする）します。

　また、最後は、残り三要素を全探索することで、1.の条件を満たすようにできます。

　これ実装しているときは、こんな大変なことしなくちゃいけないのかなぁ、と思ったけど、今ここにまとめると結構自然な実装な気もする。(もっと簡単に書けますか？）

E - Span Covering

　 解説動画を見てAC。

・とりあえずソート

　今回は、大きい順に見た方が分かりやすそう（早めに全体が埋まったら、後は簡単に計算できることなどから予想できる）

→制約を見るとDPしそう

　というところまではコンテスト中に考えていて、そこまでは正しかった。

　後は何を状態に持てばDPできるか？　ということだけど、今回は、「区間が何個に分かれているか」「区間の長さの総和」を持てば良い。（それが分かれば遷移は書ける）

　確かに、DPで解けるとしたら、状態として持てるものはこれくらいしかなさそうか……。

　これが思いつきにくいのは、途中の計算が問題文の処理中に現れる場合の数と一致していないためだと思う。

　たとえば、入力例1では、最初に2の区間を置くけど、このとき（区間：1、長さの総和：2）のときの場合の数は1。全体5の区間に2を一個置く場合の数4とは異なる。

　なのに、最終的に、（区間：1、長さの総和：全体X）を調べれば答えになっているというのは不思議な感じがしてしまう。

　問題通りの処理をするDPではなく、途中は違っても、

・最終的に答えが一致するDP

　をしなくてはいけない。

　何を使ってDPすれば良いか、柔軟に考えるのが重要か。

　ところで、これと似たDPをどこかで解いたことがある気がしたんだけど、どこだったのかなぁ……。