20190120_ABC116

ABC116感想

解説放送

• A問題は珍しく入力を一つ使わなくても解ける問題。
  • Goは使わない変数があるとCEするので、 _ で受け取らなければいけないのを思い出す。
• B問題はちょっと解釈するのに時間がかかってしまったが、落ち着いて解くほうが大事なのでOK。
  • コラッツの問題なるものらしい。
    • 初項によらず収束する（？）のは確かに不思議で面白い。
      • 余談：コラッツ問題の概要を知っていると半分以下の時間でACできそうな気がする。
• C問題はかなり時間がかかってしまった。
  • Dが難しくて正解者が少なかったため、もったいなかった。
  • 水色になるまではCの安定速解きが最重要なのを再認識。
  • 自分はシミュレーションでやったが、シミュレーションを書くときはアルゴリズムを日本語で整理しきってから書くと良いのかもしれない（？）
    • こういった問題を早く解くためにはどうすべきだったかを反省すること。
  • PDFにあるようなスマートな解法も理解すること。
    • PDFは証明をきっちりやってくれているもの（多分）。
  • 解説放送のすぬけさんのやり方は面白いし参考になりそうだが、自分の脳にはあまりなじまなかった。
• D問題は実装も大変な貪欲法。
  • 模範解答のやり方だと、priority queueが必要だったりする。
    • 解説ブログなどを散策すると、累積和などを使って解く方法もある模様。
  • 「自分で自然な想起をするにはどこがポイントになるか？」はちょっとむずかしい（貪欲法なのでそういうものかもしれないが）。
    • 種類数を固定してそのときの満足ポイントの最大値を（何らかの方法で効率的に）求め、最後に全種類数に渡ってチェックし、最大のものを答えとして採用する。
      • ARMERIAさんのブログ解説の方法。個人的には解説PDFの手法よりもしっくり来る。
      • しかし、この方法は計算量の見積もりが難しいように思える（ソートも多用する必要がある（ように見える）ため、結構怪しい気がしてしまう）
        • 実装力が十分にあっても本番ではなかなか手を動かし始めづらい解法に思える。
      • k種類確保した後の選択に関しては、全部の種類の寿司をまとめずに、それぞれの種類に関して2番手以降を「比較しながら」みていけば、なんとか実装できそう。
  • なんとなくだが、貪欲法で解くタイプの問題は、コードを書きながら考えると明後日の方向へ向かいやすい気がする。
  • 解法がわかってもとにかく実装がつらい。
    • 結局の所、priority queueを使う実装方法はよくわからない。。
  • moheiさんのコードが、考え方もコードも一番簡潔に感じられた。
    • 最も貪欲法っぽいコードに見える。
    • わかりやすいと入っても、管理すべき変数がかなり多く、本番で1発で通すのは至難に思われるので、もっと簡潔なコードがあれば知りたいところ。

自分がやったC問題の実装

コンテスト中に慌てて通したコードは余計なものがあって分かりづらかったため、後日整理したやり方。

maxHight := Max(H...)
ans := 0
for i := 0; i < maxHight; i++ {

  for j := 0; j < n; j++ {
    if H[j] > 0 {
      H[j]--

      if (j+1 < n && H[j+1] == 0) || j+1 == n {
        ans++
      }
    }
  }

}

ans のインクリメントするタイミングが難しくて本番では時間がかかってしまった。

水をやり始めたタイミング＝非ゼロな高さに出会ったらインクリメントするのが自然だったのでそうしたかったが、 走査する過程で直前の花を枯らせてしまい直前がもともと高さゼロだったのか、 もしくは本来1以上の高さが連続していたが直前にゼロまで枯らせてしまったのか、 判断できなくなり困ってしまった。

なので、高さがゼロ（メモを残していた当時、ここで息絶えていて何を書こうとしていたのかわからなくなってしまった（2019/02/28））

懐古DPさんのC問題の解き方・実装

twitterでおみかけしたもの。とてもスマートなやりかた。 こういう方法にはなにか名前とかあったりするんだろうか？

直前の花の高さと比較して、自分の方が高かったらその差分を加算するだけ。 確かに数えたいブロックの数が正しく数えられていることになる。

ans := 0
for i := 0; i < n; i++ {
  if i == 0 {
    ans += H[i]
    continue
  }

  ans += Max(H[i]-H[i-1], 0)
}

けんちょんさんのC問題の解き方・実装

while文を使って、区間の始まりで加算するやり方。

(0,0,1,1,1,1,0,1,1,1) みたいな1の連続する区間の数え上げは典型チックらしいので、こちらで覚えたいところ。

while文の採用を検討したいケース

考えられるのは、今回のような 添字の進め方の制御を柔軟に行いたい場合 。

なんとなく無限ループを生みやすい気がしていたため敬遠しがちだが、 練習するときは常に「while文のほうがいいかも」と発送できるようにしておきたい。

2019/02/26 - Dの復習

ちゃんとpriority queue使って解く。

kobaさんのブログを参考に学習する。

自分なりに考えた実装方法

選んだinitiatorとfollowerについて、それぞれを管理するデータ構造を明確に分ける。 そして、 選んだfollowerをpriority queueで管理する。

種類数について全探索する際には、種類数を最低で見積もっていることに注意する。 それでも寿司の種類数を増やしていく中で、ちゃんと正しく計算されるようになる。

直感的に考えるのが難しいが、個人的には initiatorとなっている寿司の価値がとても高い という認識が重要。 （d.jpgを参照すること。）

（自分なりの）まとめ

結局、この問題で肝になるのは、以下の内容あたりだと思う（後半はちょっとヒューリスティックがすぎるが）。

• 最適な選び方とはどういうものかを考える、イメージする、推理する。
• 各種類の寿司について、美味しさが一番大きいもの、すなわちinitiatorを「明確に」区別すること。
• 全探索という軸。
• 最初はとりあえずバカ貪欲で作ってみる、そこからの改良を検討する。

なお、cobaさんのブログでは、明確に以下の2つを典型としてまとめている。

• 貪欲
• 最適解の形を考える

解説放送のDの解法

前半の解説はPDFのやり方をわかり易く説明した感じだった。 （initiatorを示すフラグを付与した寿司のペアを作るのがちょっと大変そうではあった。）

後半の解説はkobaさんの解法とおなじに見える（多分）。

解説放送内のとあるコメント

「各ネタの中で最良の寿司」を選んだ個数を種類数だと思って計算しても上手くいく、ということに気付くと結構シンプルに書ける

自分は正当性に自信が持ちきれないけど、やはり自分の仮説は合ってるっぽい。

種類数は単純に一番良い寿司の集合から何個選んだか、で計算してよい（過小評価になるが、どこかでは最適解と一致するので大丈夫）

こちらは、同人物のtwitterからの引用。