こんにちは、NOSSです。 今日は第2回説明会を行いました。

説明会

説明会には9名ほど来てくれました。
説明した内容はこちらの紹介記事にも書いてありますので参照してみてください。

体験会

前で私のコーディング画面を写しながら実際に皆さんに問題を解いてもらうという形で体験会を行いました。
途中まほろばさんがユークリッド互除法の解説をしてくれました。

今日行ったバーチャルコンテストへのリンクはこちら(YNU CPC 2019 VC 002)

今日はループで書く最大公約数の求め方を解説しました#ynucpc pic.twitter.com/8FVC9SVScu

— 横浜国立大学競技プログラミング部 (@ynu_cpc) 2019年4月19日

ABC001 A - 積雪深差

https://atcoder.jp/contests/abc001/tasks/abc001_1

問題概要

$H_1 - H_2$ を求めよ。

解法

そのまま $H_1 - H_2$ を出力すれば答えになります。

コード例

#include <iostream>
using namespace std;

int main(){
    int h1, h2;
    cin >> h1 >> h2;
    cout << h1 - h2 << endl;
    return 0;
}

ABC065 A - Expired?

https://atcoder.jp/contests/abc065/tasks/abc065_a

問題概要

賞味期限が $A$ 日前の食品を買い $B$ 日後に食べました。
期限を $X$ 日まで過ぎた食品を食べてもおなかを壊さず、それより過ぎるお腹を壊します。

賞味期限内に食べられればdelicious、賞味期限を過ぎたがお腹を壊さなければsafe、お腹を壊したらdangerousと出力してください。

解法

それぞれ場合分けをしてどの条件にあてはまるか調べます。

• $A \ge B$ のとき
  期限内に食べられたとわかります。
• $A < B \le A+X$ のとき
  賞味期限は過ぎましたがお腹は壊さない条件を満たしています。
• $A+X < B$ のとき
  お腹を壊します。

これでそれぞれの条件がわかりました。
プログラムで場合分けを行うときにはif文が使用できます。
また、文字列を出力するときには" “で囲みます。

コード例

#include <iostream>
using namespace std;

int main(){
    int x, a, b;
    cin >> x >> a >> b;
    if(a >= b){
        cout << "delicious" << endl;
    }
    else if(a+x >= b){
        cout << "safe" << endl;
    }
    else{
        cout << "dangerous" << endl;
    }
    return 0;
}

ABC108 A - Pair

https://atcoder.jp/contests/abc108/tasks/abc108_a

問題概要

$1$ 以上 $K$ 以下の正の整数から、偶数と奇数ひとつずつの組を選ぶ方法の個数を求めてください。
なお、選ぶ順番は考慮しません。

解法

偶数と奇数を $1$ つずつ選びます。
まず偶数を $1$ つ選ぶ通りは何通りになるか考えてみます。
これは $K$ 以下の偶数の個数に一致します。
偶数の個数は $K/2$ (余り切り捨て) で求まります。

同様にして奇数を $1$ つ選ぶ通りは $K$ 以下の奇数の個数になりますから、$K-K/2$ で求まります。

偶数の選び方と奇数の選び方は独立なのでこれらの積が答えになります。

コード例

#include <iostream>
using namespace std;

int main() {
    int k, even, odd;
    cin >> k;
    even = k/2;
    odd = k-even;

    cout << even*odd << endl;

    return 0;
}

ABC112 B - Time Limit Exceeded

https://atcoder.jp/contests/abc112/tasks/abc112_b

問題概要

$N$ 個の帰宅経路の候補があります。$i$ 番目の経路はコスト $c_i$ をかけて時間 $t_i$ で帰宅できます。

時間 $T$ 以内に帰宅できる経路のうち、コストが最小となる経路のコストを求めてください。

解法

候補を $1$ ずつ順に見ていって、

• かかる時間 $t_i$ が $T$ 以下かどうか
• コスト $c_i$ は小さいか

を調べていけば答えが求められます。
すべて調べ終わったときのコストの最小値が求める値です。

調べる操作は同じ動作の繰り返しなのでループ文であるforを使用すると実装することができます。

求める最小値を $ans$ と置きます。最初は十分大きい値(無限)が入っているとします。
時間 $T$ 以内の経路のうち、コスト $c_i$ のより小さいものがあれば $ans$ を更新します。

コード例

#include <iostream>
using namespace std;

int main(){
    int N, T, c[120], t[105];
    cin >> N >> T;
    for(int i=0; i<N; i++){
        cin >> c[i] >> t[i];
    }

    int ans = 99999;  // コストの最小値。十分大きい値(inf)で初期化しておく

    for(int i=0; i<N; i++){
        if(t[i] <= T){  // かかる時間がT以下である条件
            if(c[i] < ans){  // 今まで見た最小値よりも小さい条件
                ans = c[i];
            }
        }
    }
    if(ans < 99999){
        cout << ans << endl;
    }
    else{  // 1つも時間T以下の経路がなかった
        cout << "TLE" << endl;
    }
    return 0;
}

ABC088 B - Card Game for Two

https://atcoder.jp/contests/abc088/tasks/abc088_b

問題概要

$N$ 枚のカードがあります。$i$ 枚目のカードには、$a_i$ という数が書かれています。

Alice と Bob は交互に $1$ 枚ずつカードを取っていきます。 Alice が先にカードを取ります。
$2$ 人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。

$2$ 人とも自分の得点を最大化するように最適な戦略を取った時、Alice は Bob より何点多く取るか求めてください。

解説

戦略としては残っているカードのうち、最も数の大きいカードをとっていくのがよさそうです。
なのでカードは大きい順に取られていくことになります。

どちらがどのカードを取るか考えると、
1番大きいカードをAlice、2番目に大きい値をbob、3番目に大きいカードをAlice、4番目に大きいカードをbob…
と続いていくのでこれは偶奇に注目して場合分けするとよさそうです。

よってカードの値 $a_i$ を大きさ順でソートしておき、偶奇でそれぞれに振り分けていけば答えが求まります。

コード例

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

int main(){
    int n, a[100];

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

    sort(a,a+n);  // 昇順でソート

    int alice = 0, bob = 0;
    for(int i=0; i<n; i++){
        if(i%2 == 0){
            alice += a[n-i-1];
        }
        else{
            bob += a[n-i-1];
        }
    }
    cout << alice - bob << endl;
    return 0;
}

ABC070 C - Multiple Clocks

https://atcoder.jp/contests/abc070/tasks/abc070_c

問題概要

$N$ 台の時計があり、$i$ 番目の時計の針はちょうど $T_i$ 秒で $1$ 周します。
最初、全ての時計の針は真っ直ぐ上に向いており、止まっています。
イルカは、全ての時計の針を同時に動かし始めました。
再び、全ての時計の針が真っ直ぐ上に向くのは何秒後でしょうか?

制約

• $1 \le N \le 100$
• $1 \le T_i \le 10^{18}$

解説

$N$ 個の時計の周期 $T_i$ の最小公倍数が答えになります。
よって最小公倍数の求め方が分かれば求められそうです。

$1$ つの方法として約数、あるいは倍数の列挙をしてけば求められるかもしれません。
しかし、$T_i$ が最大 $10^{18}$ と膨大な数になる可能性があるのでとても全てを調べきれません。

そこで効率なアルゴリズムとして「ユークリッドの互除法」を使います。
ユークリッドの互除法を用いると非常に高速に最大公約数が求まります。
詳しい解説はこちら(ユークリッドの互除法の証明と不定方程式 | 高校数学の美しい物語)などを参考にしてください。

最大公約数が求まると最小公倍数も求まります。
$2$ つの自然数 $a,b$ に対して最大公約数を $g$、 最小公倍数を $l$ と置きます。
また $a = a' g, b = b' g$ と表されるとします。(ただし $a', b'$ は互いに素)
このとき

$l = a’b’g = ab / g$

成り立つので $g,a,b$ から $l$ を導けます。

答えが非常に大きくなる可能性があるので int ではなく long long int を使用します。

コード例

#include <iostream>
using namespace std;

int main() {
    long long int n, t[100], ans;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> t[i];
    }
    ans = t[0];
    for(int i=0; i<n; i++){
        // ユークリッド互除法
        long long int a = ans, b = t[i], r, g;
        r = a % b;
        while(r != 0){
            a = b;
            b = r;
            r = a % b;
        }
        g = b;
        ans = ans/g*t[i];  // オーバーフロー回避のため先にgで割る
    }
    cout << ans << endl;
    return 0;
}

コメント

はじめはプログラム言語の書き方に慣れることが重要だと思います。
問題を解きながらがんばって練習しましょう！

次回の活動は4/27(金)の予定です。
活動場所についてはTwitterで連絡します。