結果

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が10⁶, Lが10⁹ なので、答えの最大値が 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;
    }
}