topcoder スターライトステージ SRM669 Div2

今回の問題はアイドルマスター！

今回の問題はアイドルマスターになぞらえた問題文になっていました。

Easy

問題文

今日はアイドルのライブの日です。 ここにM曲の歌があります。歌には0..M-1の番号がついており、歌 i はアイドル s[i] にしか歌えません。この歌を歌うと、観客の幸福度が h[i] だけ上がります。最も幸福度の高くなるように歌を選んでください。ただし、ライブの時間は限られているので、各アイドルにつき1曲しか歌えません。最も幸福度が高くなるように歌を選んだときのその幸福度を答えてください。

（デレステがリリースされた直後であることもあり、ここでちょっとアイマスっぽいなぁと思っていたのですが）

Examples 4)
{100,100,100,100,100,100,100,100,100,100,100,100,100}
{"haruka","chihaya","yayoi","iori","yukiho","makoto","ami","mami","azusa","miki","hibiki","takane","ritsuko"}
Returns: 1300

自分の解法

各アイドルについて最も幸福度が高い曲を貪欲に選んでいけば良い。228.13点（時間かかりすぎ）

Medium

問題文

アイドルの亜美と真美はゲームが好きです。今日は新しいゲームを買いました。このゲームでは、最初にスライムたちが出てきます。プレイヤーは、2匹のスライムを選び、そのスライムを合成させることができます。スライムが1匹になるまでゲームは続きます。 スライムには「大きさ」があります。大きさxとyのスライムを合成させると、新しくx+yの大きさのスライムになります。この時、x*y点が得点として入ります。 スライムの初期状態が与えられるので、亜美と真美が得られる最大の得点を求めてください。

自分の解法

明らかに貪欲な感じがしたので、与えられたスライムの大きさを 1,2,3,4,... とソートし、1と2を合成して、それと3を合成して...としてサンプルを通したら通ったのでとりあえずsubmitしました。486.35点を得て、これは部屋で最も高い得点でした。

public class CombiningSlimes {
    public int maxMascots(int[] a) {
        Arrays.sort(a);
        int len = a.length;
        
        int sum = a[0];
        int score = 0;
        for (int i = 1; i < len; i++) {
            int size = a[i];
            score += sum * size;
            sum += size;
        }
        return score;
    }
}

これは再提出が前提の提出です。提出直後、考察を始めました、考えてみると、この答え、どう考えてもおかしい点があります。

例えば、スライムの大きさが 50 50 60 70 だったとしましょう。このコードを追ってみるとこうなります。

1. 50 50 60 70 から50と50を合成します
2. 100 60 70 から100と60を合成します
3. 160 70 を最後に合成します

あら、2番で100と60を合成しているのはおかしい！貪欲に行くなら60と70を合成しないといけません。しかししかし、実はこれ、どのような順番でスライムを合成しても得点は同じになります。なのでソートする必要もなく、得点を求めるアルゴリズムさえ組めたらいいわけです。

ではこの問題の意図は？という感じですが、「問題をしっかりと理解せずにChallangeフェーズで突っ込むと死ぬ」といった目的の問題なのではないかなぁと僕は思いました。僕の部屋でもこの問題にChallangeして死んでいる人がいました。 どうやらDiv1でもチャレンジで荒れていたらしく、今回のSRMは、topcoderのチャレンジフェイズをまで考慮した問題、というのがコンセプトだったのかもしれません。

僕はコンテスト中にここまで考察していたので、チャレンジで死なずに住みました。

なおアイマスは問題にほとんど関係ない模様。

Hard

問題文

整数Nが与えられる。

完全グラフというものがある。これは、どの2つの頂点を選択したとしても、その間に枝があるグラフのことである。

ここで、「美しいグラフ」を以下の用に定義する

• N個の頂点がある完全グラフである
• すべての枝には重みがついており、その重みは1または2である。

Nに対して、 2^N*(N-1)/2 個の美しいグラフが存在する

美しいグラフの部分木のうち、最小全域木(MST)となるものを考える。最小全域木は以下を満たす

• 部分木がN個の頂点もつ
• 部分木が連結である（どの2つの頂点を選んでも、その間を行き来できるルートが存在している）
• 上2つの条件の中で、部分木の枝のコストの和が最も小さいもの

一つの美しいグラフは複数の最小全域木を持つことがある。（それぞれの最小全域木の枝の集合は異なるが、合計の重みは同じである） 最小全域木のすべての頂点について、それぞれの頂点から伸びている枝が2以下の場合、これを「線」と呼ぶことにする。 響は「最小全域木」と「線」が好きである。Nが与えられるので、頂点数Nの美しいグラフから抽出される最小全域木のうち線のものの数を、100000007で割ったものを求めよ。

自分の解法

わかりませんでした。響が出てきた理由からしてわかりませんでした。 でも解きたいし要復讐。この問題にたどり着いたとき残り50分くらいありましたが、30分くらい考えて諦め、上の問題の見直しに当てました。この選択は正しかったと思います。部屋では誰でも解けてませんでしたし、全体でも3人しか解けていませんでした。

結果

• 714.48点
  • 250点問題: 228.13
  • 500点問題: 486.35
• 部屋5位
• 全体57位
• Rating: 1035 -> 1102

過去最高レートとなりました。しかし、このままの実力だと、Div1とDiv2を往復するだけになりそうなので、そろそろ本気で勉強しないとヤバイです...

おまけ

int min = Math.max(min, h[j]); !!! pic.twitter.com/8syfM0u5ha

— うたかた/ヨシキ (@yoshiki_utakata) 2015年9月28日

String ss が実は使われていないのもポイントです。 こういうコードを指摘しても10点くらいほしい（コードの提出者が0点にならなくてもいいので）

おまけ2

@sigma425 というわけでアイマス回でした.レートがあがった人はおめでとうございます.下がった人はごめん.
まともな解説は後で書きます
ちなみにdiv2easyのサンプルにyosupoっぽいのがいます

— sigma (@sigma425) 2015年9月28日