新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

学習記録:ABC #068

[学習記録] ABC #068

引き続き過去問の学習。
D問題は解説を見ないとダメでした。。

プログラムはこちら。
atcoder/atcoder-prg/src/abc068 at master · ueriku/atcoder · GitHub

コンテストURL

abc068.contest.atcoder.jp

A問題とB問題は簡単だったので省略。

C問題

問題

N個の島があり,定期便がM種類運行されている。
i番目の定期便は,それぞれ島aiとbiを行き来することが出来る。(1<=ai<=bi<=N)
島1から島Nに行きたいが,直行する定期便はないとき,定期便を二つ使うことで島Nに行けるか調べよ。
行ける場合はPOSSIBLE,行けない場合はIMPOSSIBLEと出力せよ。

解答

色々考えたものの,愚直な方法だとN,Mが200000以下と大きいのでTLEやらMLEやらになってしまった。
定期便のリストをHashMapに入れて,島1から行ける島のリストを経由地とし,経由地から島Nに行けるかを調べることでACにできた。

// 定期便の組み合わせが入るMap。
// key: 定期便の出発元の島, value: keyの島から定期便が出ている出発先の島のList
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();

for (int i = 0; i < M; i++) {
    a[i] = in.nextInt() - 1;
    b[i] = in.nextInt() - 1;
    // mapにa[i], b[i]を追加
    List<Integer> list = map.getOrDefault(a[i], new ArrayList<Integer>());
    list.add(b[i]);
    map.put(a[i], list);
}

// 島0から定期便で行ける先のList
List<Integer> viaList = map.get(0);
String ans = "IMPOSSIBLE";

// 島0から行ける島を経由地とし,各経由地について
outside: for (Integer via : viaList) {
    // 経由地から行ける島のListを取得
    for (Integer dest: map.getOrDefault(via, new ArrayList<Integer>())) {
        // 経由地から島N(0オリジンなのでN-1)に行ければ答えはPOSSIBLE
        if (dest == N - 1) {
            ans = "POSSIBLE";
            break outside;
        }
    }
}

D問題

問題

長さNの非負整数列aiに対し,以下の操作を繰り返し行う。
「整数のうち最も大きい要素を求め,この要素の値をN減らし,それ以外の要素の値を1減らす」
数列の最大値がN-1以下になるまでこの操作を繰り返すとする。
ここで,整数Kが与えられるので,この操作を行う回数がちょうどK回となる数列aiを1つ求めよ。
ただし,2<=N<=50,0<=ai<=10^16+1000で無ければならない。

解答

わからなかったので解説を見てしまった。要するに,{0, 1, 2, ..., N-1}の数列に対して,
逆操作を左端から順番にK回行うことで,条件を満たす数列を導出することができるとのこと。
これは思いつかないなぁー

// 配列aを{0, 1, 2, 3 ... N-1}で初期化し,
// それを左から純に逆操作することで答えの配列を導出する
// 逆操作 = 選んだ要素にNを足し,他の要素から1を引く
int N = 50;
long[] a = new long[N];
// 逆操作をN回繰り返すと,結果的に全要素に1を加えたことになる
// 逆操作をK回行うとき,K/Nの数だけ全要素に1を加え,
// あまりのK%N回だけ逆操作を行えば良い
for (int i = 0; i < N; i++) {
    a[i] = i + K / N;
}

// あとはKをNで割った余りの回数だけ逆操作
for (int i = 0; i < K % N; i++) {
    // 全要素に対し,
    for (int j = 0; j < N; j++) {
        // 選んだ数にはNを足し,
        if (i == j)  a[j] += N;
        // それ以外の数から1を引く
        else  a[j]--;
    }
}