読者です 読者をやめる 読者になる 読者になる

日々精進

新しく学んだことを書き留めていきます

SRM495 Div2 Medium

IT TopCoder

問題
RとBからなる文字列が与えられるので、
1からNまでの自然数を使って以下の条件を満たす数列を作れ。
・Rの位置には素数を当てはめる
・Bの位置には非素数を当てはめる
・左から右へ単調増加する
ただし、ある位置が複数の数字を取り得る場合は、-1とすること。

方針
エストラナントカの篩を使って1〜Nまでの数の素数フラグ配列を作成する。
与えられる素数・非素数の並び順(sring colors)を1から順にマッチングしていった場合とNから順にマッチングしていった場合の数列を作成する。
上記2つの数列のi番目を比較していき、同じ数字だったらそれがi番目の数、同じでない場合は-1をi番目の数として配列を作成する。


最初は引数colorsの条件を満たす数列を全通り調べようとしていたのですが、計算量的に無理でした。
他の人の回答を見てようやく前からと後ろからマッチングした場合の2パターンのみ調べればいいと気付きました。
これに気付くようになるにはどうすればいいか。。
i番目が2つ以上の数を取りうる場合は-1とする、ではなく1つだけの場合は-1としない、と考えた方がいいかも?

ソースコード

using System;
using System.Collections.Generic;
using System.Text;

public class ColorfulCards
{
    public int[] theCards(int N, String colors)
    {
        int len = colors.Length;
        int[] isPrime = new int[N + 1];
        for (int i = 2; i <= N; i++)
            isPrime[i] = 1;
        for (int i = 2; i <= N; i++)
            if (isPrime[i].Equals(1))
                for (int j = i * 2; j <= N; j += i)
                    isPrime[j] = 0;

        int[] c = new int[len];
        for(int i = 0;i < len;i++)
            if(colors[i].Equals('R'))
                c[i] = 1;
            else
                c[i] = 0;

        int[] forward = new int[len];
        int[] backward = new int[len];
        for (int i = 1, j = 0; i <= N; i++)
            if (isPrime[i].Equals(c[j]))
            {
                forward[j] = i;
                j++;
                if (j.Equals(len)) break;
            }

        for (int i = N, j = len - 1; 0 < i; i--)
            if (isPrime[i].Equals(c[j]))
            {
                backward[j] = i;
                j--;
                if (j.Equals(-1)) break;
            }

        int[] ans = new int[len];
        for (int i = 0; i < len; i++)
            if (forward[i].Equals(backward[i]))
                ans[i] = forward[i];
            else
                ans[i] = -1;
        return ans;
    }
}