あいさつ

ABC 131に参加してました．Dまでで4完してその後E, Fも解いたので考え方を書いておきます．解答例はこちら．

A問題

4桁の文字列(数値)をとって，連続した同じものがあればBadを，無ければGoodを出力せよという問題です．文字列をs[4]として，

1
2
3
4
5
for (int i = 0; i < 3; ++i) {
    if (s[i] == s[i + 1]) {
        flag = true;
    }
}

flagがtrueならGood，そうでなければBadですね．

B問題

最初そのままいちいち差の絶対値を計算して出してACしちゃいましたが，絶対値が小さい味のものを食べないようにしたほうが簡潔ですね．食べない味の符号を反転したまま覚えておかないことにだけ注意しましょう．n, lを入力の値として，

1
2
3
4
5
6
7
8
9
10
11
int min = INF;
int not_eat = 0;
int sum = 0;
for (int i = l; i < l + n; ++i)	{
    sum += i;
    if (min > abs(i)) {
        min = abs(i);
        not_eat = i;
    }
}
cout << sum - not_eat << endl;

これで通ります．

C問題

A以上B以下の整数のうち，CでもDでも割り切れないものはいくつあるかという，中学受験の算数でありそうな問題ですね（高校受験か…？）．頭の中にベン図を思い浮かべればいいでしょう．E = lcm(C, D)とすれば，
(B - (B以下のCの倍数 + B以下のDの倍数 - B以下のEの倍数)) - (A - 1 - (A未満のCの倍数 + A未満のDの倍数 - A未満のEの倍数))で答えが求まりますね．
汚いですがこんな感じ…gcdやlcmがC++にあるのを知らなかったので自前でユークリッドの互除法を書きました…．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
unsigned long long a, aa, b;
unsigned long c, d, cc, dd;
cin >> aa >> b >> c >> d;
a = aa - 1;
unsigned long long gcd;
unsigned long long r;
cc = c, dd = d;
r = cc % dd;
while (r != 0) {
    cc = dd;
    dd = r;
    r = cc % dd;
}
gcd = c * d / dd;
	
unsigned long long bdivc, bdivd, bdivgcd, divb;
unsigned long long adivc, adivd, adivgcd, diva;
	
bdivc = b / c, bdivd = b / d, bdivgcd = b / gcd;
adivc = a / c, adivd = a / d, adivgcd = a / gcd;

divb = b - (bdivc + bdivd - bdivgcd);
diva = a - (adivc + adivd - adivgcd);

cout << (divb - diva) << endl;

D問題

0から時間がスタートします．N個のタスクがあり，締め切り時間B_iまでに，時間A_iかかるタスクたち(1 <= i <= N)をスケジューリングできますか？という問題です．自分はEDF（Earliest Deadline First）と呼ばれる締切時間優先のアルゴリズムで解きましたが，どうやらそれで正しかったようです（本当にこれでいいのかわからず，DMやRMみたいな他のアルゴリズムもあるので調べていて時間を食いました）．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
bool compare_by_b(pair<unsigned int, unsigned int> a, pair<unsigned int, unsigned int> b)
{
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first > b.first;
    }
}

int main(void)
{
    int n;
    cin >> n;
    vector<pair<unsigned int, unsigned int>> task;
    for (int i = 0; i < n; ++i) {
        unsigned int bufa, bufb;
        pair<unsigned int, unsigned int> p;
        cin >> bufa >> bufb;
        p = make_pair(bufa, bufb);
        task.push_back(p);
    }
    sort(task.begin(), task.end(), compare_by_b);
    unsigned int sumtime = 0;
    bool flag = true;
    for (int i = 0; i < task.size(); ++i) {
        sumtime += task[i].first;
        if (sumtime > task[i].second) {
            flag = false;
            break;
        }
    }
    if (flag) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

secondを使ってtaskをソートしますが，デフォルトのsortはfirstを使ってソートするので，独自のソートルールを定義しています（こういう書き方ができるんだ…）．

E問題

数字NとKが与えられた時，N頂点の単純かつ連結なグラフで，最短経路が2であるK個の頂点の組が存在するか（するならグラフのエッジ本数と構成を出力し，しないなら-1を出力せよ）という問題です．スターが最大っぽいな…というのはなんとなくわかっていたのですがそれが(N-1)(N-2)/2であることに気づけずタイムアップしました．手がかりとしては

  • スターグラフのときが最大である．
  • 完全グラフのとき0である（全部つながってるので）．

あたりかなと思っています．こういう問題はとにかく試す（一本の鎖のようにつながったグラフ，完全グラフ，スターグラフあたり）のがいいかなと思いました．
証明の手順としては，N頂点は最低でもN-1本の辺で結ばれる．したがって，K > N(N-1)/2 - (N-1) = (N-1)(N-2)/2 では解は存在し得ない．スターの時，ある点以外のN-1個の頂点間の最短距離を2にできて，その数は(N-1)(N-2)/2である，といった感じです．
このようなスターが構成できれば，残りのN-1個の頂点に辺を1本ずつ張っていくことで，最短経路2の頂点の組を一つずつ減らすことができ，結局0以上(N-1)(N-2)/2以下の組数で可能であることがわかります．
ここまで理解できれば実装はさほど困難ではなく，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n, k;
cin >> n >> k;
int max = (n - 1) * (n - 2) / 2;
if (k > max) {
    cout << -1 << endl;
} else {
  cout << (n - 1) + (max - k) << endl;
  for (int i = 0; i < n - 1; ++i) {
      cout << 1 << " " << i + 2 << endl;
  }
  int it = max - k;
  int begin = 2, end = begin + 1;
  while (it > 0) {
      cout << begin << " " << end << endl;
      end++;
      if (end > n) {
          begin++;
          end = begin + 1;
      }
      it--;
  }
}

4行目のif文では明らかに大きなものを判定．答えは(n - 1)(スター) + (max - k)(残りの部分に張る辺の数)になるのでこれを7行目で出力．あとは辺の張り方を出力します．8-10行目でスターの部分，11-21行目でスターの端点同士の辺の出力をしています．

F問題

N個の点があり，格子点に沿って四角形を形成できる三点の組を見つけ，残りの一点を見つけて追加していく操作を再帰的に何回繰り返せるかという問題です．
愚直に考えるのは到底無理なので，以下のようなグラフの問題に言い換えます．

  • 格子点のX座標を頂点X_i，Y座標を頂点Y_iとし，(x_i, y_i)に点が存在する時頂点X_iとY_iに辺を張る．
  • できたグラフに対して，それぞれの頂点から(自身を含め)いくつの(X, Y)の頂点に到達できるかを調べて，その組を(ex_i, ey_i)とする．ただし，一度訪問した点はカウントから除外する．
  • (Σex_i * ey_i) - nが答えとなる．

２つ目がミソかなあと思います．もし自身を含め(ex_i, ey_i)個の頂点にアクセスする辺が存在するなら，四角形を作るとは，全部でex_i * ey_i個の辺を張ることに相当します．
したがって，DFS等でいくつの頂点にアクセスできるかを数え，訪問した頂点は除外するという処理を書く必要があります．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
const int V = 100005;
vector<int> to[V * 2];
bool visited[V * 2];

vector<int> cnt;
void dfs(int v)
{
    //cout << "dfs(" << v << ")" << endl;
    if (visited[v]) {
        //cout << v << " is visited(in dfs)." << endl;
        return;
    }
    visited[v] = true;
    cnt[v / V]++;
    for (int u : to[v]) {
        dfs(u);
    }
}

int main(void)
{
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        y += V;
        to[x].push_back(y);
        to[y].push_back(x);
    }

    long long ans = 0;
    for (int i = 0; i < V * 2; ++i) {
        if (visited[i]) {
            //cout << i << " is visited at first." << endl;
            //cout << i << ":" << cnt[0] << " " << cnt[1] << endl;
            continue;
        }
        cnt = vector<int>(2);
        dfs(i);
        ans += (long long)cnt[0] * cnt[1];
        //cout << i << ":" << cnt[0] << " " << cnt[1] << endl;
    }
    ans -= n;
    cout << ans << endl;

    return 0;
}