College of Technology Programming Contestの解説(kagamiz担当分)

みなさん、CTPCにご参加いただき, ありがとうございました！
素晴らしいジャッジ環境を使わせていただいた@imos さん, 一緒にwriterをやってくれた@kyuridenamida さん, 問題文のチェック・問題のテストを行なっていただいた@tokoharu_sakuraさんには, 本当にお世話になりました.

また機会があれば, 次回の開催も行いたいとは思いますが, とりあえず今回の問題の解説を書きます.

(統計情報は, 後日CTPCのページに載せます.)
A. Average 問題文はこちら

[簡易解説]
問題文に書かれている通り, floor((4つの数の最大値＋４つの総和) / 5) ≧ 60であれば"Yes"を, そうでなければ"No"を出力すれば良いです.
両辺に5をかけて, (4つの数の最大値＋4つの数の総和) ≧ 300 などでも良いですね.

[解答例]

#include <stdio.h>

int main(void)
{
    int m;
    int sum, temp;
    int i;
    
    m = sum = 0;
    for (i = 0; i < 4; i++){
        scanf("%d", &temp);
        sum += temp;
        m = m > temp ? m : temp;
    }
    
    sum += m;
    
    if (sum >= 300){
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }
    
    return (0);
}

C. Communication Tool 問題文はこちら
[簡易解説]
問題文に読解する要素が多かったです. 申し訳ありません.
サンプルに, "その他の情報"がひとつも含まれていないので, 細かい所で別のミスを誘発しやすくなっていました.
解答の方針としては, 情報を読み込んでいき, それが1文字以上140文字未満であれば, リプライであるか, つぶやきであるかを判断する, というのが良いでしょう. getchar();を使って, 1文字ずつ読み込んでいっても構いません.

[解答例]

#include <stdio.h>
#include <string.h>

int main(void)
{
    int n;
    int i;
    int s, t;
    char str[512];
    
    scanf("%d", &n);
    getchar();
    
    s = t = 0;
    for (i = 0; i < n; i++){
        fgets(str, 512, stdin);
        str[strlen(str) - 1] = '\0';
        if (1 <= strlen(str) && strlen(str) < 141){
            if (str[0] == '@'){
                s++;
            }
            t++;
        }
    }
    
    if (t != 0){
        printf("Tweet:%d Reply:%d\n", ((t - s) * 100) / t, (s * 100) / t);
    }
    else {
        printf("Tweet:NA Reply:NA\n");
    }
    return (0);
}

E. Airport 問題文はこちら
[簡易解説]
n(3 ≦ n ≦ 17)個の空港間に, 問題で与えられた条件を満たす直行便の組み合わせがあるかを判定する問題でした.
解答の方針としては, まずは, この直行便の組み合わせを無向グラフとみて, 完全グラフであるかを事前に判定します. max(n) = 17なので、隣接行列(2次元配列)などで確かめていくといいと思います.
次に, 直行便の組み合わせを有向グラフと見て, ワーシャルフロイド法のアルゴリズムに似たような事(下記参照)を行います
(ただし, 2次元配列directedGraphは, 空港AからBに行くことが出来れば, directedGraph[A][B]が1, 出来なければ0になっているものとします.):

for (k = 0; k < n; k++){
    for (i = 0; i < n; i++){
        for (j = 0; j < n; j++){
            directedGraph[i][j] |= (directedGraph[i][k] & directedGraph[k][j]);
        }
    }
}

この作業によって, directedGraph[i][j]がすべて真になっていれば, すべての空港を通ったという事が証明できます. (簡単に証明できます.)

問題の制約をかなり緩くしましたが, これは, O(n^2*2^n)のアルゴリズムや, O(n*2^n)のアルゴリズムで少し迷って欲しかったからです. あまり難しいことをしないでも大丈夫です.
[解答例]

#include <stdio.h>
#include <string.h>

int main(void)
{
    char airport_id[18][21];
    char airport_adj[18][18], warshallFloyd[18][18];
    char temp[2][21];
    int n, m, from, to, flag;
    int i, j, k;
    
    scanf("%d", &n);
        
    memset(airport_adj, 0, sizeof(airport_adj));
    memset(airport_id, '\0', sizeof(airport_id));
    
    for (i = 0; i < n; i++){
        scanf("%s", airport_id[i]);
        getchar();
    }
    scanf("%d", &m);
    
    flag = 1;
    memset(warshallFloyd, 0, sizeof(warshallFloyd));
    
    for (i = 0; i < m; i++){
        scanf("%s", temp[0]);
        getchar();
        scanf("%s", temp[1]);
        getchar();
        for (j = 0; j < n; j++){
            if (strcmp(temp[0], airport_id[j]) == 0){
                from = j;
                break;
            }
        }
        
        for (j = 0; j < n; j++){
            if (strcmp(temp[1], airport_id[j]) == 0){
                to = j;
                break;
            }
        }
        warshallFloyd[from][to] = 1;
        if (airport_adj[from][to] == 0 && airport_adj[to][from] == 0){
            airport_adj[from][to] = airport_adj[to][from] = 1;
        }
        else {
            flag = 0;
        }
    }
    for (i = 0; i < n; i++){
        for (j = 0; j < n; j++){
            if (i == j){
                continue;
            }
            else if (airport_adj[i][j] != 1){
                flag = 0;
            }
        }
    }
        
    for (k = 0; k < n; k++){
        for (i = 0; i < n; i++){
            for (j = 0; j < n; j++){
                warshallFloyd[i][j] |= (warshallFloyd[i][k] & warshallFloyd[k][j]);
            }
        }
    }
    
    for (i = 0; i < n; i++){
        for (j = 0; j < n; j++){
            if (warshallFloyd[i][j] == 0){
                flag = 0;
            }
        }
    }
    
    if (flag){
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }
    
    return (0);
}

G. Lucky Number 問題文はこちら
[簡易解説]
7の冪たちを組み合わせて出来る数列のn番目の項を求める問題でした.
ここで, 7の冪たちを7進法で表してみましょう.すると, 当然ですが,

1, 10, 100, 1000, 10000, ... (すべて7進数)

となります.
問題文中にある"新しい数列"も, 7進法で書いてみましょう.

1, 10, 11, 100, 101, 110, ... (すべて7進数)
となります. 2進法の並びですね.
なので, 答えとしては, 2進数に直して7をどんどんかけていく感じになります. 途中で出てくる数が大きいので, modを適宜取るようにしましょう.

[解答例]

#include <stdio.h>

int main(void)
{
    int radix, ans;
    int n;
    
    scanf("%d", &n);
    
    ans = 0;
    radix = 1;
    
    while (n != 0){
        ans += (n & 1) * radix;
        ans %= 1000000;
        radix *= 7;
        radix %= 1000000;
        n >>= 1;
    }
    
    printf("%d\n", ans);
    
    return (0);
}

H. Magical Jump 問題文はこちら
[簡易解説]
マジカルジャンプをできるだけ行い, 最短経路で学校へ行く問題です.
想定解法としては, 動的計画法を2度用います.
1回目のDPでは, マジカルジャンプが出来る回数の最大値を求めます. (ここはDPではなくダイクストラ法などのアルゴリズムでも構いません.)
2回目のDPでは, 3次元配列を使ってDPをします.
dp[k][i][j] をマジカルジャンプをk回行なって(i, j)にいる方法とすると,
dp[k][i][j] = dp[k][i - 1][j] + dp[k][i][j - 1] + dp[k - 1][i - 1][j - 1];
となります.

猫がいる座標についても、うまく処理しながらDPをしましょう.
この解法だと, 計算量は, マジカルジャンプの最大回数をkとすると, O(kmn)となりますが, O(mn)にすることもできます.

[解答例]

#include <stdio.h>
#include <string.h>

#define MOD (1000000)

int max(int a, int b)
{
    if (a > b){
        return (a);
    }
    return (b);
}

int main(void)
{
    int x, y;
    int tx, ty;
    int i, j, k;
    int n;
    int mj[21][21];
    int dp1[21][21], dp2[21][21][21];
    
    scanf("%d%d", &x, &y);
    scanf("%d", &n);
    
    memset(mj, 0, sizeof(mj));
    for (i = 0; i < n; i++){
        scanf("%d%d", &tx, &ty);
        mj[ty][tx] = -2;
        for (j = -1; j <= 1; j++){
            for (k = -1; k <= 1; k++){
                if (0 <= ty + j && ty + j <= y && 0 <= tx + k && tx + k <= x && mj[ty + j][tx + k] == 0 && (j != 0 || k != 0)){
                    mj[ty + j][tx + k] = -1;
                }
            }
        }
    }
    
    for (i = 0; i <= y; i++){
        for (j = 0; j <= x; j++){
            dp1[i][j] = -1 * 100000;
        }
    }
    
    for (i = 0; i <= y; i++){
        if (mj[i][0] != -2){
            dp1[i][0] = 0;
        }
        else {
            break;
        }
    }
    
    for (i = 0; i <= x; i++){
        if (mj[0][i] != -2){
            dp1[0][i] = 0;
        }
        else {
            break;
        }
    }
    
    for (i = 1; i <= y; i++){
        for (j = 1; j <= x; j++){
            if (mj[i][j] != -2){
                dp1[i][j] = max(dp1[i][j - 1], dp1[i - 1][j]);
            }
            if (mj[i - 1][j - 1] == 0 && mj[i][j] != -2){
                dp1[i][j] = max(dp1[i][j], dp1[i - 1][j - 1] + 1);
            }
        }
    }
    
    memset(dp2, 0, sizeof(dp2));
    
    for (i = 0; i <= y; i++){
        if (mj[i][0] != -2){
            dp2[i][0][0] = 1;
        }
        else {
            break;
        }
    }
    
    for (i = 0; i <= x; i++){
        if (mj[0][i] != -2){
            dp2[0][i][0] = 1;
        }
        else {
            break;
        }
    }
    
    for (i = 1; i <= y; i++){
        for (j = 1; j <= x; j++){
            for (k = 0; k <= dp1[i][j]; k++){
                if (mj[i][j] != -2){
                    dp2[i][j][k] = dp2[i - 1][j][k] + dp2[i][j - 1][k];
                    dp2[i][j][k] %= MOD;
                    
                    if (mj[i - 1][j - 1] == 0 && k != 0){
                        dp2[i][j][k] += dp2[i - 1][j - 1][k - 1];
                        dp2[i][j][k] %= MOD;
                    }
                }
            }
        }
    }
    
    printf("%d\n", dp2[y][x][dp1[y][x]]);
    
    return (0);
}

K. Prime Factorial 問題文はこちら
[簡易解説]
実際に素数をかけ合わせていき, 大きさ10^6の配列の添字に問題の条件を満たす場合1, 満たさない場合0などをいれて, O(1)で判定をしましょう.
素数判定には, エラトステネスのふるい(O(nloglogn))を使うと良いです.

[解答例]

#include <stdio.h>

char prime[10000001];
char pf[1000001];

void CountPrime(void)
{
    long long t;
    int i, j;
    
    for (i = 3; i < 10000001; i += 2){
        prime[i] = 1;
    }
    t = 2;
    prime[(int)t] = pf[(int)t] = 1;
    
    for (i = 3; i * i <= 10000000; i += 2){
        if (prime[i]){
            for (j = i * i; j <= 10000000; j += 2 * i){
                prime[j] = 0;
            }
        }
    }
    
    for (i = 3; i <= 10000000; i++){
        if (prime[i]){
            t = t * i % 1000000;
            pf[(int)t] = 1;
        }
    }
}

int main(void)
{
    int n;
    int t;
    int i;
    
    CountPrime();
    
    scanf("%d", &t);
    
    for (i = 0; i < t; i++){
        scanf("%d", &n);
        printf("%s\n", pf[n] ? "Yes" : "No");
    }
    
    return (0);
}