新人SEの学習記録

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

参加記録: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問題

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