新人SEの学習記録

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

学習記録:ABC #067

[学習記録] ABC #067

またまた引き続き過去問の学習。
相変わらずD問題は解説を見ないとダメ。。

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

コンテストURL

abc067.contest.atcoder.jp

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

C問題

問題

N枚のカードの山があり,上からi番目のカードには整数aiが書かれている。
すぬけ君がこのカードの山の上から何枚かカードを取ったとき,取ったカードに書かれた数の総和をx,残りのカードに書かれた数の総和をyとし,|x-y|としてありうる値の最小値を求めよ。

解答

上手いことやろうとして結構WAを連発してしまった。
愚直に|x-y|を毎回計算するようにして,その最小値をそのまま出すようにしてACにできた。

for (int i = 0; i < N; i++) {
    a[i] = in.nextLong();
    sum += a[i];
}

// まずは1枚目のカードを引いた状態にする
// 現在の引いたカードの合計値はa[0]
long snuke = a[0];
// 現在の|x - y|はsum - 一番上のカードの値*2
long cur = Math.abs(sum - snuke * 2);
// 答えとなる|x - y|の最小値
long ans = cur;

// 両者とも1枚は引かないといけないので,iは1〜N-2でループさせる
for (int i = 1; i < N - 1; i++) {
    // 新たにa[i]を引く
    snuke += a[i];
    // 現在の|x - y|を計算
    cur = Math.abs(sum - snuke * 2);
    // 答えを更新
    ans = Math.min(ans, cur);
}

D問題

問題

1からNまでの番号のついたN個のマス目があり,マス目はN-1本の道でつながれている。
i番目の道はai番のマスとbi番のマスを繋げており,どの2つのマスも隣接するマスを辿って必ずたどり着くことができる。
はじめに1番のマスは黒く,N番のマスは白く塗られている。
先手のフェネックは黒いマスから隣接した何も塗られていないマスを1つ選んで黒く塗り,後手のすぬけくんは白く塗られたマスから隣接した何も塗られていないマスを1つ選んで白く塗る。
手番のプレイヤーがマスに色を塗れなかったとき敗者となる。フェネックとすぬけくんが最適に行動したときの勝者を出力せよ。

解答

木構造が毎回苦手。。
まずは1番のマスからN番のマスへの最短パスを塗っていくのが最適戦術だと思いつくことが必要。
続いて,その場合には,あるマスについて1番のマスからの距離がN番のマスからの距離が近い場合,そのマスは黒く塗れることがわかる。(解説を読むまでわからなかった。。)
その1番マスおよびN番マスからの距離だけを見て黒か白か判定して,黒の方が多ければフェネックの,白の方が多ければ(+同数なら)すぬけくんの勝ちとなる。

// 木構造を表すリスト。
// i番目のリストには,マスiから伸びている道が続くマス目の番号が入る
List<List<Integer>> treeList;
// 深さ優先探索で使うフラグ配列。マス目iが既に通ったか否かを表す
boolean[] done;
// マス1から他のマスへの距離およびマスNから他のマスへの距離
int[] dist1, distN;    

public void calc() {
    int N = in.nextInt();
    int[] a = new int[N-1], b = new int[N-1];

    // treeListの初期化
    treeList = new ArrayList<List<Integer>>();
    for (int i = 0; i < N; i++) {
        treeList.add(new ArrayList<Integer>());
    }

    for (int i = 0; i < N-1; i++) {
        a[i] = in.nextInt() - 1;
        b[i] = in.nextInt() - 1;
        treeList.get(a[i]).add(b[i]);
        treeList.get(b[i]).add(a[i]);
    }
    
    done = new boolean[N];
    dist1 = new int[N];
    distN = new int[N];
    
    // マス1からの深さ優先探索
    dfs(0, 0, dist1);
    // マスNからの深さ優先探索(フラグも初期化)
    Arrays.fill(done, false);
    dfs(N-1, 0, distN);
    
    // フェネックとsnukeが穫れるマス目の数
    int fennec = 0, snuke = 0;    
    for(int i = 0; i < N; i++) {
        // マス1からの方が近ければフェネックが取れる
        if (dist1[i] <= distN[i]) {
            fennec++;
        }
        else {
            snuke++;
        }
    }
    
    // snukeが取れるマス目がフェネックと同数以上ならsnukeの勝ち
    String ans = "Fennec";        
    if (snuke >= fennec) {
        ans = "Snuke";
    }
    
    out.println(ans);
    out.close();
}

void dfs(int to, int len, int[] dist) {
    if (done[to]) {
        return;
    }
    done[to] = true;
    dist[to] += len;
    treeList.get(to).forEach(next -> dfs(next, len+1, dist));             
}

学習記録: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]--;
    }
} 

学習記録:ABC #069

[学習記録] ABC #069

いつも通り過去問を解いてみました。
なんとか解説を見ずに4問解けた!(所要時間1時間くらい)

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

コンテストURL

abc069.contest.atcoder.jp

A問題

問題

東西にn本,南北にm本の通りがある。
東西南北を通りに囲まれた最小の領域を街区と呼ぶ時,街区が何個あるか求めよ。

解答

(n-1)*(m-1)を求めるだけ。

int n = in.nextInt(), m = in.nextInt();
System.out.println((n-1) * (m-1));

B問題

問題

3文字以上の文字列sが与えられる。
"internationalization"を"i18n"と略すように,同様の規則で文字列sを略したものを求めよ。

解答

sの先頭文字とsの文字列長-2,sの末尾文字をくっつけたものを出力すればOK。

char[] s = in.next().toCharArray();
String ans = "" + s[0] + (s.length-2) + s[s.length-1];
System.out.println(ans);

C問題

問題

長さNの数列a(a1, ... aN)が与えられる。
aの要素を自由に並べ替え,全ての隣り合うai, ai+1の積が4の倍数に出来る時"Yes",出来ない場合"No"を出力せよ。

解答

4の倍数の個数と,2の倍数(4の倍数を除く)の個数が大事なところまではわかった。
そこから色々と条件分岐を考えて解答。
解説を見たらもっと簡略化できたもよう。

String ans = "No";

// 4の倍数の個数と2の倍数の個数が特定の条件を満たすときに"Yes"になる
if (N % 2 == 0) {
    if (divisibleBy4 + divisibleBy2 / 2 >= N / 2) {
        ans = "Yes";
    }
}
else {
    if (divisibleBy4 + (divisibleBy2 - 1) / 2 >= N / 2) {
        ans = "Yes";
    }
}

D問題

問題

H * Wのマス目がある。これをN個の色で塗り分ける。
ただし,色iで塗られたマス目は全て隣り合っている必要がある。
また,色iで塗れるマス目の個数は,配列a(a1, ... aN)で与えられる。
このとき,条件を満たす塗り方を一つ求めよ。

解答

色を順番にマス目に塗っていくことになるが,横一列や縦一列に塗ろうとすると,
折り返しのときに色が隣り合わずに途切れてしまう可能性がある。
それなら渦巻状に塗っていけば良いんじゃないか?という発想で解答できた。
解説を見たら渦巻状で無くても,右に塗っていって端まで来たら一段下がって左へ・・・という塗り方で良かったorz
途中で上がったり下がったりと余計な苦労をしてしまった。。

// H, W, N, aについては取得済

int[][] ans = new int[H][W];

// 1 = 下/右方向 -1 = 上/左方向 0 = 移動しない
int dirH = 1;
int dirW = 0;
// h, wの初期値
int height = -1;
int width = 0;

// 各色について順番に塗っていく
for (int color = 0; color < N; color++) {
    // 色の数a[color]だけ塗りつぶしていく
    for (int i = 0; i < a[color]; i++) {
        // 次のマスへ移動
        height += dirH;
        width += dirW;
        
        // H * Wのマス目を越えてしまっている,もしくは移動先が既に塗られている場合
        if (height < 0 || height >= H || width < 0 || width >= W || ans[height][width] != 0) {
            // 移動する前に戻る
            height -= dirH;
            width -= dirW;
            // 向きを変える(下 -> 右 -> 上 -> 左の順に向きを変えていく)
            if (dirH == 0) {
                dirH = -dirW;
                dirW = 0;
            }
            else {
                dirW = dirH;
                dirH = 0;                        
            }
            // 今回のループでは何も塗らなかったので回数も戻す
            i--;
        }
        // 普通に濡れる場合
        else {
            // マス目を塗りつぶす(色は1オリジンなので1足す)
            ans[height][width] = color + 1;
        }
    }
}

for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
        out.print(ans[i][j] + " ");                
    }
    out.println();
}

学習記録:ABC #074 D問題

[学習記録] ABC #074 D問題

できなかったD問題を解いてみました。
プログラムはこちら。
atcoder/Main.java at master · ueriku/atcoder · GitHub

コンテストURL

abc074.contest.atcoder.jp

問題

N個の都市があり,ある都市間は道路で双方向に結ばれている。
どの都市からどの都市へも,必要であれば他の都市を経由することで移動ができる。
N*Nの表Aが与えられ,Ai,jは都市iからjへの最短経路の長さを示すものとする。
このような道路の構造が存在するか判定し,存在する場合はそのような道路の構造のうち,存在する道路の長さの和が最小となるものを求めよ。
存在しない場合は-1を出力せよ。

解答

最短距離と聞いて真っ先にワーシャルフロイド法が思い浮かんだが,今回の問題では既に最短距離(と思われるもの)が与えられている。
まずはこのグラフAを更にワーシャルフロイド法に掛けて,本当に最短距離のグラフなのか確かめる。
続いて道路の長さの和を求める必要があるが,解説を見てもなかなか良くわからなかった。
結果的には,各A[i][j]を足し算していき(A[i][j]とA[j][i]は二重カウントしないようにする),
経由地kをとったときに,A[i][j] == A[i][k] + A[k][j]となるようなkが存在する場合,その道路の長さA[i][j]はカウントしないようにすることで,答えを求めることができた。

public void calc() {
    int N = in.nextInt();
    int[][] A = new int[N][N];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            A[i][j] = in.nextInt();
        }
    }

    // グラフAとなる道路の構造が存在しなければtrue
    boolean notExist = false;
    // 答えとなる道路の長さの和(存在しない場合-1)
    long ans = 0;

    // A[i][j]について調べる
    for (int i = 0; i < N; i++) {
        if (notExist) {
            break;
        }
        for (int j = i + 1; j < N; j++) {           
            if (notExist) {
                break;
            }                
            // 道路の長さの和に加える必要がある場合true
            boolean add = true;
            // 各A[i][j]について,経由地kをとった場合を見ていく
            for (int k = 0; k < N; k++) {
                // i == kまたはj == kの場合はカウントしない
                if (i != k && j != k) {
                    // kを経由した際,そちらの方がA[i][j]より短い距離で行けてしまう道が存在する場合,
                    // このグラフAを満たす道路の組み合わせは存在しない                        
                    if (A[i][j] > A[i][k] + A[k][j]) {
                        notExist = true;
                        break;
                    }
                    // kを経由した際の距離がA[i][j]と等しいkが存在する場合,
                    // その距離A[i][j]は答えに加算しない(他の道路の距離を足し合わせることでカウントされるため)
                    else if (A[i][j] == A[i][k] + A[k][j]) {
                        add = false;
                    }
                }
            }
            if (add) {
                ans += A[i][j];
            }
        }   
    }
    // 存在しない場合はansに-1を入れる
    if (notExist) {
        ans = -1;
    }
    out.println(ans);
    out.close();  
} 

参加記録:ABC #074

[参加記録] ABC #074

なるべく毎週参加します。

コンテストURL

abc074.contest.atcoder.jp

結果

忘れていてコンテスト開始から50分後に参加したこともありC問題をギリギリ解けず時間中に解けたのはA,Bのみ。
殘念すぎるorz
コードは以下に格納してます。
atcoder/atcoder-prg/src/abc074 at master · ueriku/atcoder · GitHub

A問題

問題

N*Nのマス目のうちAマスを白色に塗る時,塗られていないマスは何個あるか求めよ。

解答

本来の問題はもうちょっとわかりにくく書いてますが,要するにN*NからAを引いた値を求めるだけ。

public void calc() {
    int N = in.nextInt();
    int A = in.nextInt();

    out.println(N * N - A);
    out.close();
}

B問題

問題

N個のボールがあり,i番目のボールはx軸の位置xiに存在する。
タイプAのロボットはx軸の位置0に,タイプBのロボットはx軸の位置Kに存在する。
ロボットを使ってボールを回収するとき,各ロボットの移動距離の総和として考えられる最小の値を求めよ。
なお,ロボットの挙動は,ボールの位置まで移動し,ボールを1個回収し,もとの位置まで戻るという挙動になる。

解答

本来の問題文はもうちょっとわかりにくく書かれていましたが,y軸は無視してOKで,
各ボールについてタイプAからとタイプBからのどちらからの方が近いか求め,その距離の2倍を足していく形になります。

for (int i = 0; i < N; i++) {
    ans += Math.min(x[i], Math.abs(K - x[i])) * 2;           
}

C問題

問題

以下の4つの操作を組み合わせて,砂糖水を作る。

  • ビーカーに水を100 * Aグラム入れる
  • ビーカーに水を100 * Bグラム入れる
  • ビーカーに砂糖をCグラム入れる
  • ビーカーに砂糖をDグラム入れる

各操作は何回行ってもいいし,一回も行わない操作があっても良い。
なるべく濃い砂糖水を作るとき,その砂糖水の質量と溶けている砂糖の質量を求めよ。
ただし,100グラムに溶ける砂糖の量はEグラムまでであり,砂糖を溶け残らせてはいけない。
また,作った砂糖水の質量がFグラムを越えてはいけない。

解答

なんかかっこいい方程式で溶けるんじゃないか?とあれこれ考えていたものの上手くいかず,
結局全通り探索すればいいやと気づいたもののギリギリで撃沈。
一個だけWAになるなーと思っていたら,作れる砂糖水の濃度の最大値が0%だったとき,答えとなる砂糖水の質量が0グラムになってしまってはダメでした。
問題文にもただの水は濃度0%の砂糖水と考えると書いており,砂糖水の質量は少なくとも100*Aグラムじゃないといけないのでした。

// 答えとなる水の量と砂糖の量,砂糖水の濃度。
// 砂糖の量は0グラムになる可能性があるが,水は0グラムだと不正解になる
// Fは100*Aよりは大きいという制限があるので,初期値として100*Aを入れておく
int water = 100 * A;
int sugar = 0;
double noudo = 0.0;
// Eから導出される,答えとなる濃度の最大値。
// これを越えてしまうと不正解。
double maxn = 100.0 * E / (100.0 + E);

// 各操作を何回行うかをi1, i2, i3, i4として全ての場合を求める
for (int i1 = 0; i1 <= F / A * 100; i1++) {
    for (int i2 = 0; i2 <= F / B * 100; i2++) {
        // この組み合わせの時点で総量がFグラムを越えていたらスキップする
        if (i1 * A * 100 + i2 * B * 100 > F) {
            break;
        }
        
        for (int i3 = 0; i3 <= F / C; i3++) {
            // この組み合わせの時点で総量がFグラムを越えていたらスキップする
            if (i1 * A * 100 + i2 * B * 100 + i3 * C > F) {
                break;
            }                    
            
            for (int i4 = 0; i4 <= F / D; i4++) {
                // i1~i4の組み合わせでの水と砂糖の量を計算する                        
                int w = 100 * A * i1 + 100 * B * i2;
                int s = C * i3 + D * i4;
                // Fを越えていたらスキップ
                if (w + s > F) {
                    break;
                }
                // 濃度を求める
                double n = 100.0 * s / (w + s);
                // 濃度がEから求められる最大値を越えておらず,
                // 今までの計算の中での最大値より大きければその答えを保持する
                if (n <= maxn && noudo < n) {
                    noudo = n;
                    water = w;
                    sugar = s;
                }
            }                       
        }
    }           
}

D問題

まったく見れてないので後日解きます。

学習記録:ABC #070

[学習記録] ABC #070

引き続きAtCoder Beginner Contestの過去問を解いてます。

コンテストURL

abc070.contest.atcoder.jp

結果

D問題だけ解説を見ないと解けず。。
コードは以下に格納してます。
atcoder/atcoder-prg/src/abc070 at master · ueriku/atcoder · GitHub

A問題

問題

3桁の整数Nが与えられる。
Nが回文数(逆に並べても元の数と同じ数になる)の場合"Yes", そうでない場合"No"を出力せよ。

解答

100の桁(N / 100の整数値)と1の桁(100で割った余りを10で割った余り)が等しければYes。

public void calc() {
    int N = in.nextInt();

    String ans = (N / 100 == (N % 100) % 10)? "Yes" : "No";
        
    out.println(ans);
    out.close();
}

B問題

問題

AliceはA秒後からB秒後までスイッチを押し,BobはC秒後からD秒後までスイッチを押す。
ふたりともスイッチを押していた秒数を求めよ。

解答

色々条件分岐で出した。解説を見るともっと簡単に求められる模様。
重複してなければ0秒,重複していればmin(B, D) - max(A, C)で良いとのこと。

int calcTime(int A, int B, int C, int D) {
    // C <-> DがA <-> Bの範囲と重複しない場合
    if (B <= C || D <= A) {
        return 0;
    }

    // CがAより小さい場合
    if (C < A) {
        // DがB以下なら,A<->Dが重複範囲となる
        if (D <= B) {
            return D - A;
        }
        // DがBより大きければ,A<->Bが重複範囲となる
        else {
            return B - A;
        }
    }
    // 残るケースはCがAとBの間にある場合のみ
    else {
        // DがB以下なら,C<->Dが重複範囲となる
        if (D <= B) {
            return D - C;
        }
        // DがBより大きければ,C<->Bが重複範囲となる
        else {
            return B - C;
        }   
    }
}

C問題

問題

N個の整数T1...TNの最小公倍数を求めよ。

解答

T1とT2の最小公倍数を求め,その値とT3の最小公倍数を…と求めていけば良い。
ユークリッドの互除法で最大公約数を求め,それを使って最小公倍数を求める。
割り算の順序を間違えると桁が溢れてしまったりするので注意。

// 最小公倍数を求める
private long lcm(long a, long b) {
    // gcdでの割り算を先にすることで桁あふれを防ぐ
    return a / gcd(a, b) * b;
}

// 最大公約数を求める
private long gcd(long a, long b) {
    if (a > b) {
        return gcd(b, a);
    }
    while (a != 0) {
        long tmp = a;
        a = b % a;
        b = tmp;
    }
    return b;
}

public void calc() {
    int N = in.nextInt();
    long[] T = new long[N];

    for (int i = 0; i < N; i++) {
        T[i] = in.nextLong();
    }

    long ans = 1;
    
    for (int i = 0; i < N; i++) {
        ans = lcm(ans, T[i]);
    }
    
    out.println(ans);
    out.close();
}

D問題

問題

N頂点の木が与えられる。辺はN-1本あり,頂点aiとbiを距離ciで繋ぐ。
質問がQ個与えられ,それぞれについて頂点xiと頂点yiが示される。
また,加えて頂点Kが与えられる。
このとき,各質問について,頂点xiから頂点Kを経由し,頂点yiまで移動する場合の最短距離を求めよ。

解答

ワーシャルフロイド法を使ったところ,longのN*N二次元配列のせいでMLEになってしまった。
そもそも任意の2頂点を繋ぐ辺は1本しか無いので,全通り探索するのはちょっと無駄が多い。
解説と以下のブログ記事を読んで,深さ優先探索で書いてみた。
AtCoder Beginner Contest 070 /解説 - 絶賛工事中

木構造Javaで表すのをどうすれば良いか迷っていたが,上の記事ではTreeMapのArrayListで表現していた。
Listのi番目に入っているMapには,町iから伸びている道の情報が入っている。
MapのKeyが道の続いている町で,Valueは距離を示している。
このMapを,町Kから深さ優先探索していき,町Kから他の町への最短距離を計測する。
最終的に求めるのは,町Kからxiへの最短距離と,yiへの最短距離になる。

// 木構造を表すリスト。
// i番目のリストに入っているMapは,町iから伸びる辺を著す。 
// MapのKeyは辺が続く町で,Valueは距離を示す。
ArrayList<TreeMap<Integer, Long>> treeList = new ArrayList<TreeMap<Integer,Long>>();
// dist[i]: 町iから町Kへの最短距離
long[] dist;

public void calc() {
    int N = in.nextInt();
    int[] a = new int[N-1];
    int[] b = new int[N-1];
    long[] c = new long[N-1];

    for (int i = 0; i < N-1; i++) {
        a[i] = in.nextInt() - 1;
        b[i] = in.nextInt() - 1;
        c[i] = in.nextLong();
    }
    
    int Q = in.nextInt();
    int K = in.nextInt() - 1;
    int[] x = new int[Q];
    int[] y = new int[Q];

    for (int i = 0; i < Q; i++) {
        x[i] = in.nextInt() - 1;
        y[i] = in.nextInt() - 1;
    }

    // treeListの初期化
    for (int i = 0; i < N; i++) {
        treeList.add(new TreeMap<Integer, Long>());
    }
    
    // 道の情報をtreeList(の中のMap)に入れていく
    for (int i = 0; i < N-1; i++) {
        treeList.get(a[i]).put(b[i], c[i]);
        treeList.get(b[i]).put(a[i], c[i]);
    }
    
    dist = new long[N];
    // 各点からKへの距離を求める
    dfs(-1, K, 0);
    
    for (int i = 0; i < Q; i++) {
        out.println(dist[x[i]] + dist[y[i]]);
    }
         
    out.close();
}

// 町Kから順に深さ優先探索を実施して,Kから各町への最短距離を求める
// 引数によって,前の町はfrom,現在の町はtoであり,ここまで距離len掛かっていることを表す。
// 町Kから現在地toまでの距離dist[to]を距離lenで初期化し,
// 次の町への道をtreeListから取得して再帰を行う。
// 再帰を行う際に町fromへ戻ってしまうと無限ループに陥るので,その前に来た道を除外している。
void dfs(int from, int to, long len) {
    // toへの距離をlenで初期化
    dist[to] = len;
    // K番目の町から伸びた道の情報が入ったMapを取得
    TreeMap<Integer, Long> map = treeList.get(to);
    // 来た道を消す(探索から除外する)
    map.remove(from);
    // 次の町toに着いたものとし,そこから再度dfsする。
    // その際,今来た町toをfromとし,fromから続く道をMapから取り出して,次の町とそこまでの距離を計算する
    map.forEach((k, v) -> dfs(to, k, len+v));
}

学習記録:ABC #071

[学習記録] ABC #071

引き続きAtCoder Beginner Contestの過去問を解いてます。

コンテストURL

abc071.contest.atcoder.jp

結果

今回もA〜Dまで解説を見ずに解けた!
ABCをやるより頑張ってARCに挑んだ方が良いか…?

A問題

問題

数直線上の位置a, b, xが与えられる。
xからaとbのどちらが近いか求め,"A"か"B"で出力せよ。

解答

絶対値を使って三項演算子で"A"か"B"を入れた。

    public void calc() {
        int x = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();

        String ans = (Math.abs(a - x) < Math.abs(b - x))? "A" : "B"; 
        
        out.println(ans);
        out.close();
    }

B問題

問題

英小文字からなる文字列Sが与えられる。
Sに現れない英小文字について,アルファベット順で小さいものを求めよ。ただし,Sに全ての英小文字が現れる場合は"None"を出力せよ。

解答

各小文字についてフラグを管理する方法もあると思うが(そっちの方がわかりやすかった気がする),
配列をソートしてごちゃごちゃやってしまった。

    public void calc() {
        String S = in.next();
        char[] carray = S.toCharArray();
        Arrays.sort(carray);
        String alphabet = "abcdefghijklmnopqrstuvwxyz";
        int index = 0;
        String ans = "None";
        
        for (char c : alphabet.toCharArray()) {
            if (index >= carray.length || carray[index] != c) {
                ans = c + "";
                break;
            }
            while (index < carray.length && carray[index] == c) {
                index++;
            }
        }

        out.println(ans);
        out.close();
    }

C問題

問題

N個の棒について,長さAiが与えられる。
これらの棒から異なる4本を選び,長方形を作る時,最大の面積になる長方形の面積を求めよ。

解答

Mapに棒の長さとその長さの棒の本数を入れてソート。
棒を長い順に見ていって,2本以上あればそれを使う,という感じで作った。
もっとも長い棒が4本ある場合,縦も横も同じ長さの棒を使えることを最初失念していてエラーになった。
また,Aiが10^9以下と大きいので,面積を求めるときはBigDecimalなりを使わないとダメ。

    public void calc() {
        int N = in.nextInt();
        int[] A = new int[N];

        for (int i = 0; i < N; i++) {
            A[i] = in.nextInt();
        }
        
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < N; i++) {
            map.put(A[i], map.getOrDefault(A[i], 0) + 1);
        }
        
        Object[] mapkey = map.keySet().toArray();
        Arrays.sort(mapkey);

        int w = 0;
        int h = 0;
        
        for (int i = mapkey.length - 1; i >= 0; i--) {
            int key = (int)mapkey[i];
            int num = map.get(key);
            if (num >= 4 && w == 0) {
                w = key;
                h = key;
                break;
            }
            else if (num >= 2 && w == 0) {
                w = key;
            }
            else if (num >= 2 && w != 0) {
                h = key;
                break;
            }
        }        
        
        BigDecimal width = new BigDecimal(String.valueOf(w));
        BigDecimal height = new BigDecimal(String.valueOf(h));
        BigDecimal ans = width.multiply(height).stripTrailingZeros();
        
        out.println(ans.toPlainString());
        out.close();
    }

D問題

問題

2×Nのマス目があり,このマス目にN個のドミノを敷き詰める。
ドミノは1×2の大きさで,マス目に縦または横に配置できる。
ドミノの敷き詰め方は文字列S1, S2で与えられ,それぞれ異なる英字で以下のように示される。

xaa
xbb

このとき,左端にはドミノが縦に,その次にはドミノが横になって上下に配置されていることを示す。
これらのドミノを3色で塗り,接しているドミノは異なる色で塗り分けるようにするとき,塗り方が何通りあるかをmod 1000000007で求めよ。

解答

複雑で投げ出しそうになったが,左端からドミノを見ていくと,縦にドミノを1つ置くか,横にドミノを上下2つで並べるかの2通りしかない。
左から順に見ていき,塗り分けられるパターンが何通りあるかを掛けていけば良い。
一番左端が縦ドミノの場合は3通り,横ドミノの場合は6通りの塗り分け方が存在する。
その次からは,左隣りのドミノが縦か横かと,自分自身が縦か横かの4パターンで塗り分け方が何通りあるか異なる。

  • 縦 -> 縦:2通り
  • 縦 -> 横:2通り
  • 横 -> 縦:1通り
  • 横 -> 横:3通り

これらの値を,左端のドミノから掛け算していけばOK。
なお,答えはmod 1000000007で求める必要があるので,掛け算の度にmodを求めておく。
その際,Javaのintだと一時的にintの最大値を越えてしまう可能性があるのでlongにしておくこと。

    public void calc() {
        int N = in.nextInt();
        char[] S1 = in.next().toCharArray();
        char[] S2 = in.next().toCharArray();
        final int MOD = 1000000007;

        long ans = 0;
        // 左横のドミノが縦向きならtrueをとる
        boolean portrait = false;
        
        // S1について1文字ずつ見ていく
        for (int i = 0; i < S1.length; i++) {
            char c = S1[i];

            // ドミノが縦向きなら
            if (c == S2[i]) {
                if (i == 0) {
                    // 左端のドミノが縦向きなら最初の塗り方は3通り
                    ans = 3;
                }
                else {
                    if (portrait) {
                        // 縦 -> 縦なら*2通りする
                        ans = ((ans % MOD) * 2) % MOD;
                    }
                    else {
                        // 横 -> 縦なら1通りしかないので何もしない
                    }
                }
                // 前のドミノを縦向きにする
                portrait = true;
            }
            // ドミノが横向きなら
            else {
                if (i == 0) {
                    // 左端のドミノが横向きなら最初の塗り方は6通り
                    ans = 6;
                }               
                else {
                    if (portrait) {
                        // 縦 -> 横なら*2通りする
                        ans = ((ans % MOD) * 2) % MOD;
                    }
                    else {
                        // 横 -> 横なら*3通りする
                        ans = ((ans % MOD) * 3) % MOD;                        
                    }
                }
                // 前のドミノを横向きに設定して1つ多く進む
                portrait = false;
                i++;
            }
        }

学習記録:ABC #072

[学習記録] ABC #072

今日から時間のある日はAtCoderのBeginner Contestの過去問題をやってみることにしました。
まずはABC #072から。

コンテストURL

abc072.contest.atcoder.jp

結果

A〜Dまで解説を見ずに解けた!

A問題

問題

砂時計に入っている砂の重さX[g]と,時間t[秒]が与えられる。
1秒間に1g砂が落ちるとして,t秒後に何gの砂が砂時計の上側に残っているか求めよ。

解答

Xよりtが大きければ0を返すように,三項演算子を使ってみた。

    public void calc() {
        int X = in.nextInt();
        int t = in.nextInt();
        
        int ans = (X - t > 0)? X - t: 0;
        
        out.println(ans);
        out.close();
    }

B問題

問題

文字列sが与えられる。
前から数えて奇数文字目だけ抜き出して作った文字列を求めよ。

解答

char型の配列にして,indexが(0オリジンなので)偶数の文字だけ出力した。

    public void calc() {
        String s = in.next();
        char[] carray = s.toCharArray();
        
        for (int i = 0; i < carray.length; i = i + 2) {
            out.print(carray[i]);
        }
        out.println();
        out.close();
    }

C問題

問題

長さNと整数列a1...aNが与えられる。
各aiについて1を足す or 1を引く or 何もしないの3つの操作からどれか一つを選んで行う。
上手く操作を行い,ある整数Xの個数を最大化したとき,この個数を求めよ。

解答

結局,各aiに1を足した時と1を引いた時と何もしなかったときで,他のaiには影響がないので,
全てのaiに+1, -1, +-0したときの個数を計算して一番大きい値を出せば良い。

    public void calc() {
        int N = in.nextInt();
        int a[] = new int[N];

        for (int i = 0; i < N; i++) {
            a[i] = in.nextInt();
        }

        // 整数XをKeyにし,その個数をValueとするMap
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < N; i++) {
            // 各aiについて何もしない, +1, -1したときの個数を入れていく
            map.put(a[i], map.getOrDefault(a[i], 0) + 1);
            map.put(a[i] + 1, map.getOrDefault(a[i] + 1, 0) + 1);
            map.put(a[i] - 1, map.getOrDefault(a[i] - 1, 0) + 1);
        }

        int ans = 0;
        
        for (Map.Entry<Integer, Integer> e: map.entrySet()) {
            // 一番大きいValue = 個数を求める
            ans = Math.max(e.getValue(), ans);
        }
        
        out.println(ans);
        out.close();
    }

D問題

問題

N個の整数からなる順列p1, ... pNが与えられる。
隣り合う二つの数を選んでスワップし,全てのpiに対して,i != piとなるようにしたい。
必要なスワップ操作の最小回数を求めよ。

解答

左端から見ていって,pi == iとなる数があったら,その右隣と入れ替えればOK。
最初は一番右端がpi == iとなっているときに入れ替えるのを忘れていた。

    public void calc() {
        int N = in.nextInt();
        int[] p = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            p[i] = in.nextInt();
        }

        int ans = 0;
        
        // 右隣と入れ替える(配列の長さを越えないように注意)
        for (int i = 1; i < N; i++) {
            if (p[i] == i) {
                int tmp = p[i];
                p[i] = p[i+1];
                p[i+1] = tmp;
                ans++;
            }
        }
        
        // 一番右端の数字を入れ替える場合
        if (p[N] == N) {
            ans++;
        }
        
        out.println(ans);
        out.close();
    }