Code Formula 2014 予選A

Code Formula

夏休み究極の無気力マンと化し起きてる時間より寝てる時間のほうが多い気がする中

ようやくDが解けたので全部載せる

コンテスト↓

Welcome to Code Formula 2014 予選A - Code Formula 2014 予選A | AtCoder

  1. 問題概要

    • Aの三乗根をがあれば'YES'なければ'NO'出力

    解法

    • やるだけ
    ソースコード

  2. 問題概要

    • ボーリングのたおれたピンをいい感じに出力しろ

    解法

    • やるだけ
    ソースコード

  3. 問題概要

      • 各予選の最高順位が高い人から順番に選ばれる。
      • 最高順位が同じ場合は、最高順位を取った予選が開かれた時期が早い方から先に選ばれる。
      • k 人が選ばれるまで、この操作を続ける。
    • 以上のルールをもとに、各予選を終えた時点で本戦出場が確定する人を出力して

    解法

    • がんばってやるだけ（難読解）
    • 愚直にやってもO(N^2 * K)
    ソースコード

  4. 問題概要

    • 作りたい文字列Sと、知ってる文字群Kが与えられます
    • 文字を間違えると＋２、正しい文字を使えば＋１
    • ある文字を使ったらその文字は二度と間違えない
    • 最善を尽くして文字列Sを作る時の期待値を求めて
    • 文字の種類は[1~9][a~z]

    解法

    • dp[残りの作りたい文字の数][今分からない文字の数] で　期待値dp
    • 解説でdp解法はやりにくいとかいう訳わからない事言われたがdpのほうが絶対簡単
    • 期待値 dpの基本は、ある状態の時の値 * その状態に遷移するパターン数　の総和を最終的に総遷移数で割ると出来るっぽい
    ソースコード

感想

期待値dpどうやらあってたみたいだけど微妙にバグった

そもそも、コンテスト中に期待値の問題をまともに解けたことが無いのでこういう典型っぽい問題でならしておきたい

55位で微妙な順位だけど予選通ったんかなこれ