猫でもわかるWebプログラミングと副業

本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。

AtCoder Regular Contest #041 に参加しました&復習

結果

  • 200(1) 44:52
  • 順位: 129位
  • Rating: 3級 -> 2級

AとBは解けました。Cも解法は分かったのですがACはできませんでした。

解説に関してはAtCoder公式の生放送 or スライドがわかりやすいと思います。

http://www.nicovideo.jp/watch/lv227003854

A - コインの反転

やるだけなので省略

B - アメーバ

僕は外側から順に数を決めていったが、正解が存在することが保証されているので、解説の通り上から貪欲にやっていけばよかった…。

提出したソースコード

import java.io.*;
import java.util.*;
import java.lang.ArrayIndexOutOfBoundsException;
import java.math.*;
 
class Main {
    static Scanner sc = new Scanner(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] table = new int[n][m];
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            for (int j = 0; j < m; j++) {
                table[i][j] = (int)(str.charAt(j) - '0');
            }
        }
        
        int[][] ans = new int[n][m];
        int mini = 1;
        int minj = 1;
        int maxi = n - 1;
        int maxj = m - 1;
        while(mini <= maxi && minj <= maxj) {
            for (int i = mini; i < maxi; i++) {
                ans[i][minj] += action(table, i, minj);
                ans[i][maxj-1] += action(table, i, maxj-1);
            }
            for (int j = minj+1; j < maxj-1; j++) {
                ans[mini][j] += action(table, mini, j);
                ans[maxi-1][j] += action(table, maxi-1, j);
            }
            mini++;
            minj++;
            maxi--;
            maxj--;
        }
        
        print(ans, n, m);
    }
    
    static void print(int[][] table, int n, int m) {
        for (int i = 0; i < n; i++) {
            StringBuffer buf = new StringBuffer();
            for (int j = 0; j < m; j++) {
                buf.append(table[i][j]);
            }
            System.out.println(buf.toString());
        }
    }
    
    static int action(int[][] table, int i, int j) {
        int ans = table[i-1][j];
        ans = Math.min(ans, table[i][j-1]);
        ans = Math.min(ans, table[i+1][j]);
        ans = Math.min(ans, table[i][j+1]);
        table[i-1][j] -= ans;
        table[i][j-1] -= ans;
        table[i+1][j] -= ans;
        table[i][j+1] -= ans;
        return ans;
    }
}

C - ウサギ跳び

これも解説がすごくわかりやすい。

右向きのうさぎと左向きのうさぎをセットにして考えることは気づいて、実装もできた。ただし、Nが106, Lが109 なので、答えの最大値が N*L と同程度のオーダーとなることを考えると、intじゃ収まらないのでlongにする必要がある。ここに気づかずに時間内にはACできなかった。

一体何回オーバーフローでWA出してるのかわからないのですが、久々だとどうしても忘れてしまうので、これはプロコン用ソースコードにコメントを残しておくべきだと思った。

ソースコード

import java.io.*;
import java.util.*;
import java.lang.ArrayIndexOutOfBoundsException;
import java.math.*;

class Main {
    static Scanner sc = new Scanner(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int l = sc.nextInt();
        
        ArrayDeque<Integer> rq = new ArrayDeque<Integer>();
        ArrayDeque<Integer> lq = new ArrayDeque<Integer>();
        long ans = 0;
        long sumi_cnt = 0;
        
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            char direction = sc.next().charAt(0);
            if(direction == 'L') {   // 左向きのうさぎの場合
                if(rq.isEmpty()) {    // 左端までジャンプできる場合
                    long cnt = x - 1 - sumi_cnt;
                    ans += cnt;
                    sumi_cnt++;
                } else {  // 右向きのうさぎが既に存在する場合
                    lq.addLast(x);
                }
            } else {  // 右向きのうさぎの場合
                if(lq.isEmpty()) {
                    rq.addLast(x);
                } else {  // セットが見つかったので計算
                    long cnt = calc(rq, lq);
                    ans += cnt;
                    rq.push(x);
                }
            }
        }
        // ループ終了後
        if(lq.isEmpty()) {    // 残ったやつ全員右端まで行かせる
            sumi_cnt = 0;
            while(rq.size() > 0) {
                int x = rq.pollLast();
                long cnt = l - x - sumi_cnt;
                ans += cnt;
                sumi_cnt++;
            }
        } else {
            ans += calc(rq, lq);
        }
        System.out.println(ans);
    }
    
    static long calc(ArrayDeque<Integer> rq, ArrayDeque<Integer> lq) {
        int rx = rq.pollLast();
        int rcount = 1;
        long ans = 0;
        while(rq.size() > 0) {
            int x = rq.pollLast();
            long cnt = rx - x - rcount;
            ans += cnt;
            rcount++;
        }
        int lx = lq.pollFirst();
        int lcount = 1;
        while(lq.size() > 0) {
            int x = lq.pollFirst();
            long cnt = x - lx - lcount;
            ans += cnt;
            lcount++;
        }
        long max_cnt = Math.max(rcount, lcount);
        long cnt = max_cnt * (lx - rx - 1);
        ans += cnt;
        return ans;
    }
}

おわりに

D問題の解説を見ましたが、凄い美しい問題でした。今回の解説生放送は学びが多かったので、見る価値アリだと思います。

おまけ

f:id:yoshiki_utakata:20150705020732p:plain