topcoder SRM 660 Div2 に参加しました！

結果と反省

最近は朝10時とかにやってることが多かったので、参加できていませんでしたが、久々の参加です！このブログでtopcoder参加記は初めて書くので今までのレート遷移から

ちょっと最近落ち込んでいます。とりあえず緑に戻そう！

と思ったのですが…ダメでした。

まずEasyの問題を理解するのに時間がかかりました。でもEasyは通ったのでその点に関してはよしとしましょう。問題はMedです。Medも解法はなんとなくわかりました。が、勘違いをしていました。終了30秒前にその勘違いに気づくという…。これはEasyの問題をサッと処理できなかった影響ですね。

今回は問題を把握するのに時間がかかってしまいました。次からAOJの問題を解く時は時間をはかろうかと思います。

最終結果は

• 1問正解
• 部屋12位
• Rating: 849 -> 855 (+6)

でした。

Easy: Cyclemin

問題

文字列Sの「循環」を、「一番最初の文字を取り除いて、一番最後につけたす」ことと定義する。例えば abcde を1回循環させると bcdea となる。

次に、文字列Sに対して、Sの循環文字列の集合というものを考える。これは、文字列Sを0回以上循環させてできる文字列の集合である。Sを abcde とすると、abcde, cdeab, eabcd などは、Sの循環文字列の集合に入る。

つづいて、文字列の大きさというものを定義する。同じ長さの文字列の場合、辞書順で前の方に来る文字列の方を「小さい」と定義する*1 。例えば、cable と cards では、b の方が r より辞書順で前になるので、cable の方が「小さい」ということになる。

あなたは String s と int k を入力として受け取る。s は英語小文字からなる文字列である。あなたは、s の中で k 文字まで好きな文字（英語小文字）に書き換えることができる。またさらに、sを好きなだけ循環させることができる。この操作で作ることができる文字列の中で、辞書順最小のものを答えよ。

入出力例

• 0) aba, 1

  • 1文字書き換えられるので、bをaに書き換えて aaa とするのが辞書順で最小

• 1) aba, 0

  • 書き換えはできないが、循環させて aab とするのが辞書順で最小

• 2) bbb, 2

  • 最初の2文字を書き換えて aab とするのが最小

• 3) sgsgaw, 1

  • wをaに書き換えた後、循環させて aasgsg とするのが最小

• 4) abacaba, 1

  • aaaabac

• 5) isgbiao, 2

  • aaaisgb

方針

まず文字の書き換えについては、辞書順最小を目指すので、 a 以外に書き換える意味はなさそうです。問題はどこを書き換えるかです。入出力例5を見てみると、書き換える位置の決定はそんな簡単に決まらないように思えます。文字列の長さが50で短いからといって、1文字1文字について、書き換えるかどうかを全探索していると、2⁵⁰ かかってしまい間に合いません。どうすればいいでしょうか。

ポイントは、「最初に文字列の循環をしてから、その中で最小になる文字列の書き換えを行う」ことです。入力例5で見てみましょう。

• isgbiao -循環0-> isgbiao -2文字書き換え-> aagbiao
• isgbiao -循環1-> sgbiaoi -2文字書き換え-> aabiaoi
• ...（中略）...
• isgbiao -循環4-> iaoisgb -2文字書き換え-> aaaisbg

以上を見てもらえればわかると思いますが、循環が固定されると、「先頭から順に見ていき、 a 以外の文字を a に書き換える」ことによって辞書順最小になります。じゃあすべての循環文字列に対してこの書き換え操作を行い、辞書順最小のものを取ってくればいいということになります。

循環が最高で50パターン、循環後の文字書き換えが最悪O(50)、文字列の大小比較にO(50)だとすれば、このアルゴリズムは O(50*(50+50)) で間に合います。50だったら3乗まで大丈夫と覚えておくのは便利かもしれません。

実装

public class Cyclemin {
    public String bestmod(String s, int k){
        int len = s.length();
        String ans = null;
        for (int i = 0; i < len; i++) {
            // ローテーション操作
            char c = s.charAt(0);
            s = s.substring(1) + c;
            // 書き換え操作
            String replaced_s = replace(s, k);
            // 辞書順確認
            if(ans == null){
                ans = replaced_s;
            }else if(ans.compareTo(replaced_s) > 0){
                ans = replaced_s;
            }
        }
        return ans;
    }
    
    String replace(String s, int k){
        if(k == 0) return s;
        char[] c = s.toCharArray();
        for(int i = 0; i < c.length; i++){
            if(c[i] != 'a'){
                c[i] = 'a';
                k--;
                if(k == 0) break;
            }
        }
        return String.valueOf(c);
    }
}

Mid: Private Party

問題文 *2

射命丸文は友達をパーティーに誘おうとしています。 彼女はn人の友達がいるので、仮に 0 から n-1 までの番号をつけるとします。 それぞれの友達は、1人以下の嫌いな友達がいます。 a[i] = j のとき、i番目の友達はj番目の友達が嫌いです。 ただし、 a[i] = i のとき、i番目の友達には嫌いな友達がいません。

射命丸は、彼女の友達を順番にパーティーに招待していこうと思います。 しかし、i番目の友達を招待した時に、i番目の人が嫌いなj番目の友達が、すでにパーティーに参加することが決まっていると、i番目はパーティーにへの招待を事態してしまいます。 （つまり、i番目の友達がパーティーに参加する時は、まだj番目の人を招待していないパターンか、j番目の人に断られてj番目の人がパーティに来ないパターンの2つがあることになります）

射命丸は、招待する順番を工夫し、なるべく多くの人をパーティーに参加させたいと考えています。配列 a が与えられるので、最も多くて何人参加してくれるかを答えなさい。

解法

この問題は問題文を読んでもらえれば問題の意味は分かってもらえると思うので、サンプル自体の解説はしません。

• 例えば、AがBを嫌っていることを A->B と書くとします。この時Bを先に招待するとAは来てくれないのですが、Aを先に招待すれば何も問題ありません。
• 同様に A->B->C->D のような場合も、矢印をたどるように招待すれば全員来てくれます。
• 問題になるのは、A<->B のようにお互いが嫌いなパターン。この時はかならずどちらかしか呼べません。
• これを拡張して、A->B->C->D->A のようにループができているパターン。この場合は、どのような順に招待しても、AからDのうち誰か1人はパーティに来なくなってしまいます。

つまりまとめるとこうです。

• 上のような嫌いな人有向グラフを作成し
• ループが1つ発見されるごとに1人来なくなる

実装

深さ優先探索を使ってループを発見します。ループの発見はグラフの問題でしばし使うので書けるようにしておきましょう。

package topcoder.SRM660Div2;

public class PrivateD2party {
    public int getsz(int[] a){
        int n = a.length;
        
        
        Person[] persons = new Person[n];
        for (int i = 0; i < n; i++) {
            persons[i] = new Person(i);
        }
        
        for (int i = 0; i < n; i++) {
            if(a[i] == i) continue;
            persons[i].hate = persons[a[i]];
        }
        
        int ans = n;
        for (int i = 0; i < n; i++) {
            if(persons[i].loopindex == 0){
                if(dfs(persons[i], 1, i+1) != 0){
                    ans --;
                }
            }
        }
        return ans;
    }
    
    public int dfs(Person person, int i, int loopindex){
        if(person.hate == null) return 0;
        if(person.loopindex != 0){
            if(person.loopindex == loopindex){
                // ループ発見
                return i - person.cnt;
            }else{
                // 探索済み
                return 0;
            }
        }
        person.loopindex = loopindex;
        person.cnt = i;
        return dfs(person.hate, i+1, loopindex);
    }
    
    class Person{
        public Person hate = null;
        public int cnt = 0;
        public int loopindex = 0;
        public int index;
        
        Person(int i){
            index = i;
        }
    }
}

おわりに

今回の2問はシンプルな問題の割にはよく考察が必要な良い問題でした。 3問目はまだ解いてませんが解けたら書くかもしれません。

*1:「辞書順で小さい」と言ったりする

*2:実際の問題文とは異なることがあります