【アルゴリズム問題】yukicoder no.9 モンスターのレベル上げ (level ☆☆☆)
閉じる
閉じる

新しい記事を投稿しました。シェアして読者に伝えましょう

×

【アルゴリズム問題】yukicoder no.9 モンスターのレベル上げ (level ☆☆☆)

2014-08-01 00:04

    (そんなに面白く無い問題です)

    HeliaはRPGゲームをしている。そのRPGゲームは味方のモンスターのレベル上げていきゲームを進めるゲームである。
    Heliaは手持ちにN匹のモンスターのパーティーがいてレベル上げしたいと思っている。

    レベル上げは、敵のモンスターと1対1で戦い、敵のレベルの半分小数切り捨てを獲得できる。(自分の戦ったモンスターのレベルに加算する)
    例えば、自分のモンスターが1で相手のモンスターのレベルが5の時、
    戦ったあと、自分のモンスターのレベルは3になる。
    戦いに関しては、アイテムを駆使してでも勝つため、レベル差に関係なく勝てるとする。

    ここで、敵のモンスターが円状に時計回りに並んでいて、最初に戦うモンスターを決めると時計回りの順番に全員と一度だけ戦うことができる狩場がある。
    (最初に戦えるモンスターは自由に選べる)

    Heliaは、自分の手持ちのモンスターの中から、1戦毎、その時に一番レベルが低い、複数いる場合は、一番戦いをしてないモンスターを戦わせるとする。
    この狩場のモンスターを全て倒すとして、手持ちのパーティー中で戦闘回数が一番多い回数がもっとも低くなるよう狩場で最初に戦うモンスターを選んだとき、その中で一番戦闘回数が多い数を求めてください。

    入力
    N
    A1 A2 ... AN
    (空白区切り)
    B1 B2 ... BN
    (空白区切り)

    制約
    想定計算時間 2秒以内 (Java想定)
    1<=N<=1500 パーティーのモンスター数です。
    1<=Ai<=10000 味方のパーティーのモンスターのそれぞれのレベルです。
    1<=Bi<=10000 敵の狩場のモンスターのそれぞれのレベルです。

    狩場のモンスター数と味方のモンスター数は同じとする。
    この順番は時計回りに並んでるとする。


    出力
    数値を文字列で出力する。


    sample1
    3
    6 1 5
    9 2 7

    ans1
    2

    例えば狩場の最初のモンスターを左から3番目を選ぶとすると、
    7,9,2と戦う
    以下()内は戦闘回数

    6(0),1(0),5(0) -> 6(0),4(1),5(0) -> 6(0),8(2),5(0) ->6(0),8(2),6(1)
    となり、少なくとも、戦いが一番多いモンスターは2回は戦うことになる。


    sample2
    5
    6 1 5 9 2
    7 7 9 4 4

    ans2
    2

    狩場の最初のモンスターを左から4番目を選ぶとすると、
    4,4,7,7,9と順番に戦う

    6(0),1(0),5(0),9(0),2(0) -> 6(0),3(1),5(0),9(0),2(0) -> 6(0),3(1),5(0),9(0),4(1)->
    6(0),6(2),5(0),9(0),4(1) -> 6(0),6(2),5(0),9(0),7(2) -> 6(0),6(2),9(1),9(0),7(2)

    となり、一番戦う回数が多いのが2となる。
    (どのモンスターと最初に戦っても少なくとも、一番試合数が多いのは少なくとも2回となる)

    q

    https://gist.githubusercontent.com/yuki2006/522a0cd78b54d6dfe8f2/raw/863670bd5c159ec63cba38cba280506104a0bbbf/gistfile1.txt


    ちょっと不評だったのでネタばらし
    愚直に書くとO(N^3)を O(N^2 log N)にする問題です。


    自分の想定解
    http://ideone.com/OmIOKb

    1st 2コメさん
    http://ideone.com/z0c9EN

    2nd nanashiさん
    http://ideone.com/t7FUvS

    3rd. myonさん
    http://ideone.com/8YHcaQ
    広告
    コメントを書く
    コメントをするには、
    ログインして下さい。