3

本日、google code jam round 1B に参加してきました。コードジャムで、「Osmos」という問題がありました: https://code.google.com/codejam/contest/2434486/dashboard

問題の説明

問題は、プレイヤーが物であるゲームがあり、それよりも小さいものしか食べられず、食べたもののサイズだけ大きくなるということです. たとえば、サイズ 10 のプレーヤーがサイズ 8 のものを食べると、サイズ 18 になります。

ここで、プレーヤーの開始時のサイズと、ゲーム内の他のすべてのサイズを考慮して、ゲームを打ち負かすために必要な最小限の操作数を指定する必要があります。つまり、最終的にすべてを食べることができるということです。

操作は、何かを追加したり、何かを削除したりすることができます。

私が使用したコード

write_caseすべてのテスト ケースの出力を正しい形式で書き込む関数です。私は他のコード ジャム ラウンドでそれを使用しましたが、それが正しく、inp入力ファイルのファイル オブジェクトであることはわかっています。

cases = int(inp.readline())
for case in xrange(cases):
    # armin is the variable containing the size of the player,
    armin, n = int(inp.readline.split()[0])
    # others is a list of sizes of other things
    others = [int(x) for x in inp.readline().split()]

    # changes obviously holds the number of required changes
    changes = 0
    for other in sorted(others):  #we loop over all the other things in order.
        if other < armin:  #if the other thing is smaller, eat it, no change needed.
            armin += other
        else: # we'll need to make some changes
            # adding is the biggest size thing the player can eat,
            adding = armin - 1
            if other < armin + adding:  #if adding such a thing is good enough
                                        # to eat the other thing
                armin += adding + other # add it and eat them
                changes += 1 #we've made a change.
            else: # we can't add a big enough thing
                # we have to elete it from the game (skip it from the loop)
                # which is a change 
                changes += 1

    write_case(case + 1, changes ) #output the changes.

その背後にある私の論理

小さいものから大きいものまで他のものをループすることで、プレイヤーは最初に通常食べられるものをすべて食べます。食べられないものに遭遇すると、それよりも小さいものはすべて食べてしまったので、成長するために新しいものを追加する必要があります. 何か新しいものを追加する場合は、追加するもののサイズによって操作の数が変わらないため、できるだけ大きくすることをお勧めします。私が追加できる最大の食べられるものは、プレーヤーのサイズ -1 です。それが次のものを食べるのに十分な場合は、それを追加し、追加したものを食べ、以前に食べられなかったものを食べる.

追加が不十分な場合は、追加せず、現在のものを削除 (無視) します)。この時点で、他のすべてのものをスキップするためにループから抜け出すことができます (リストは並べ替えるには大きすぎるため)。 、しかし、それは結果を変えません。

このコードは、サンプル入力の値を正しく計算しますが、コンテスト入力に対しては正しくありません。理由はありますか？

4

3 に答える 3

1

したがって、あなたの問題は、追加が十分でない場合に何が起こるかのように見えます...その後、別のモートを導入して、十分に大きくなるまで自分のモートに餌を与え続けることができるからです. 別のモートをフィードしない場合は、残りのモートをすべて削除するとだけ言ったほうがよいでしょう。

興味があれば、この問題のかなり良い説明をここに公開しました。

于 2013-05-05T22:47:42.713 に答える