AtCoder Grand Contest 032 B

atcoder.jp

問題文

整数 N が与えられます。 頂点に 1 から N の番号がついた N 頂点の無向グラフであって、以下の 2 つの条件を満たすものを 1 つ構成してください。

• 単純かつ連結
• ある整数 S が存在して、任意の頂点についてその頂点に隣接する頂点の番号の値の和は S となる

この問題の制約下でそのようなグラフが少なくとも 1 つ存在することが証明できます。

制約

• 入力は全て整数である。
• 

出力

1行目に構成したグラフの辺の本数を出力せよ。 続く行のうち行目には、2つの整数とを出力せよ。これらは番目の辺の端点を表す。 構成されたグラフが条件を満たすならば正解となる。

解法

この問題は、任意の頂点Vについてつながっていない頂点(自身含む)の番号の和を一定にすること、と言い換えが出来る。 隣接行列を描いて考える。

• N=偶数の場合

• N=奇数の場合

偶数と同様に考える 対処法

上の図で色のついていないマスが求める辺になる。

C++で実装

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<pair<int, int>> ans;

void read()
{
    cin >> N;
}
void solve()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if ((i + j) != (N + 1 - (N & 1)))
            {
                ans.push_back(make_pair(i, j));
            }
        }
    }
}
void print()
{
    cout << ans.size() << endl;
    for (auto &&i : ans)
    {
        cout << i.first << " " << i.second << endl;
    }
}
int main()
{
    read();
    solve();
    print();
    return 0;
}

AtCoder Grand Contest 032 A

atcoder.jp

問題文

• すぬけ君は空の数列 a を持っています。
• すぬけ君は a に対して N 回操作を行います。
• i 回目の操作では 1≤j≤i を満たす整数 j を選び、a の先頭から j 番目に j を挿入することができます。
• 長さ N の数列 b が与えられます。
• N 回の操作後に a が b と一致することがあるかどうかを判定し、可能ならばそれを達成する操作手順の一例を示してください。

制約

• 入力はすべて整数である。
• 
• 

出力

N回の操作後に a と b が一致するような操作手順が存在しないならば "-1" を出力せよ。存在するならば操作手順をN行に出力せよ。i行目ではi回目の操作で選んだ整数を出力せよ。考えられる操作手順が複数存在する場合は、そのうちのどれを出力してもよい。

解法

作成可能な数列Cがあるとする。その数列Cから1つずつ数字を取り除き、最終的に空の数列にすることができればよい。取り除くことができるのは (one based indexing)となる要素だけである。今、このような要素がの3つあるとする ( ) 。以外を取り除いた場合、 となるような状態(を取り除くことが出来る状態)が起こりえないのは明らかである。つまり、を満たすもののうち最もの大きいものを取り除く操作を数列が空になるまで行い、その操作を逆順に出力することで、答えを得ることが出来る。これはである。

C++で実装

#include <iostream>
#include <vector>
using namespace std;
#define MAX_N 100

bool is_ans = true;
int N;
vector<int> b;
vector<int> ans;

void read()
{
    int tmp;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> tmp;
        b.push_back(tmp);
    }
    return;
};
void solve()
{
    while (true)
    {
        is_ans = false;
        for (int i = b.size() - 1; i >= 0; i--)
        {
            if (b[i] == i + 1)
            {
                ans.push_back(i + 1);
                b.erase(b.begin() + i);
                is_ans = true;
                break;
            }
        }
        if (b.empty() == true)
        {
            is_ans = true;
            return;
        }
        if (b.empty() == false && is_ans == false)
        {
            return;
        }
    }
};
void print_ans()
{
    if (is_ans == true)
    {
        for (auto i = ans.rbegin(); i != ans.rend(); i++)
        {
            cout << *i << endl;
        }
    }
    else
    {
        cout << -1 << endl;
    }
}
int main()
{
    read();
    solve();
    print_ans();
    return 0;
}