AtCoder Regular Contest #006

結果

3完でした。もうちょっとよく考えたらD解けたかもしれないなぁ

A - 宝くじ

うわぁめんどくさい実装問題だなぁとか思ってクソ汚いコードを提出した。

int e[10];
int l[10];

int main()
{
    int count = 0, b, tmp;

    for(int i = 0; i < 6; i++)
    {
        scanf("%d", &tmp);

        e[tmp]++;
    }

    scanf("%d", &b);

    for(int i = 0; i < 6; i++)
    {
        scanf("%d", &tmp);

        l[tmp]++;
    }

    for(int i = 0; i < 10; i++)
        if(e[i] && l[i])
            count++;
    
    if(count == 6)
        puts("1");
    else if(count == 5)
        for(int i = 0; i < 10; i++)
            if(e[i] == 0 && l[i] == 1)
            {
                if(i == b)
                    puts("2");
                else
                    puts("3");
                return 0;
            }
    else if(count == 4)
        puts("4");
    else if(count == 3)
        puts("5");
    else
        puts("0");
    
}

B - あみだくじ

入力厄介だったのでgetlineで一気に読み込んで, 適当にシミュレーションして頭の悪い答えの求め方をしました.制限が緩かったので通っただけです.あと, これだとメモリ範囲外をインデクシングしそうですが, 通ったのでまぁいいと思います(ヨクナイ)

int main()
{
    int y, x;
    string s;
    vector<string> v;

    scanf("%d%d", &x, &y);
    cin.ignore();
    for(int i = 0; i <= y; i++)
    {
        getline(cin, s);
        v.push_back(s);
    }

    int now;

    for(int i = 0; i < v[y].size(); i++)
        if(v[y][i] == 'o')
            now = i;

    for(int i = y - 1; i >= 0; i--)
        if(v[i][now - 1] == '-')
            now -= 2;
        else if(v[i][now + 1] == '-')
            now += 2;

    int ans = 0;

    for(int i = 0; i <= now; i++)
        if(v[0][i] == '|')
            ans++;

    cout << ans << endl;
}

C - 積み重ね

１番これが簡単だったと思います. 焦ってメモ化していないコードで提出してTLEになりましたが...

const int INF = 1 << 30;
int n;
int w[52];
int memo[52];

int dfs(vector<int> a, int i)
{
    if(n == i)
        return a.size();
    if(memo[i] > 0)
        return memo[i];

    int res = INF;

    for(int j = 0; j < a.size(); j++)
    {
        if(w[i] <= a[j])
        {
            int tmp = a[j];
            a[j] = w[i];
            res = min(res, dfs(a, i + 1));
            a[j] = tmp;
        }
    }

    a.push_back(w[i]);

    res = min(res, dfs(a, i + 1));

    return memo[i] = res;
}

int main()
{
    scanf("%d", &n);
    vector<int> a;

    for(int i = 0; i < n; i++)
    {
        cin >> w[i];
    }

    a.push_back(w[0]);

    int res = dfs(a, 1);

    cout << res << endl;
}

D - アルファベット探し

正答者が多かったので, 簡単な問題だと気づくべきだった.

方針

訪れたところが'o'な場所を塗りつぶす.
塗りつぶした数を数える.
大きさはサンプルのAを数えれば分かると思いますが, 1倍→4倍→9倍→16倍...のように数が増加しているので上手いこと判定すればいいと思います.

typedef pair<int, int> P;

char c[1024][1024];
bool visited[1024][1024];
int ans[3];

const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dot[] = {12, 16, 11};

int main()
{
    int h, w;

    scanf("%d%d", &h, &w);

    for(int i = 0; i < h; i++)
    {
        cin >> c[i];
    }

    memset(visited, 0, sizeof(visited));

    for(int i = 0; i < h; i++)
    {
        for(int j = 0; j < w; j++)
        {
            if(visited[i][j]) continue;

            if(c[i][j] == 'o')
            {
                int count = 0;

                queue<P> que;

                for(que.push(make_pair(i, j)); !que.empty(); que.pop())
                {
                    P p = que.front();

                    if(visited[p.first][p.second])
                        continue;

                    visited[p.first][p.second] = true;
                    count++;

                    for(int k = 0; k < 8; k++)
                    {
                        int nx = p.second + dx[k], ny = p.first + dy[k];

                        if(nx < 0 || ny < 0 || nx >= w || ny >= h) continue;
                        if(visited[ny][nx]) continue;

                        if(c[ny][nx] == 'o')
                        {
                            que.push(make_pair(ny, nx));
                        }
                    }
                }

                for(int k = 0; k < 3; k++)
                {
                    double tmp = sqrt((double)count / dot[k]);

                    if(tmp - (int)tmp == 0)
                    {
                        ans[k]++;
                    }
                }
            }
        }
    }

    cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;
}