tookunn’s diary

主に競技プログラミング関係

Good Bye 2017 C New Year and Curling

問題

codeforces.com

半径rの円の中心のx座標がN個与えられる。
i = 0,1,2,3...N-1の順に円はy=10^100からy = 0に向かって進む。
他の円に接した時、y = 0に円が接した時に円は止まる。
最終的なN個の円のy座標を求める。

考察

i番目の円aをy=0に向かって進める際に、既に止まっているj番目(j < i)の円bを考える。

abs(x[i] - x[j])がr * 2(円aの半径+円bの半径)より大きい場合はその円同士は接することはない。
abs(x[i] - x[j])がr * 2以下の場合は接するので、円aと円bの距離は必ずr * 2になる。
後は三平方の定理からsqrt( (r * 2) * (r * 2) - abs(x[i] - x[j]) * abs(x[i] - x[j]) )が円aと円bのy座標の距離となる。

y[j] + (円aと円bのy座標の距離)の最大値が円aの最終的なy座標となる。

ソースコード

戒め
これは色々良くないコードで
y座標が大きいものから取って、円が止まるy座標を二分探索してる

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class C {

    int N,r;
    int[] x;
    ArrayList<Point> points;

    private class Point implements Comparable<Point>{
        double y,x;

        public Point(double y,double x) {
            this.y = y;
            this.x = x;
        }

        public int compareTo(Point point) {
            return Double.compare(point.y,this.y);
        }
    }

    private double dis(Point p,double y,double x) {
        return (p.y - y) * (p.y - y) + (p.x - x) * (p.x - x);
    }

    private boolean isHit(double y,double x) {
        for(Point p : points) {
            if (dis(p,y,x)  <= (r * 2) * (r * 2)) {
                return true;
            }
        }

        return false;
    }

    private double getY(PriorityQueue<Point> q,double x) {

        double lowY = r;

        while(q.size() > 0) {
            Point p = q.poll();
            if (isHit(p.y,x)) {
                lowY = Math.max(lowY,p.y);
            }
        }

        double low = lowY;
        double high = 10000000;

        for(int j = 0;j < 100;j++) {
            double mid = (high + low) / 2;

            if (isHit(mid,x)) {
                low = mid;
            } else {
                high = mid;
            }
        }

        return high;
    }

    private void solve() {
        N = nextInt();
        r = nextInt();

        x = new int[N];
        for(int i = 0;i < N;i++) {
            x[i] = nextInt();
        }

        PriorityQueue<Point> pq = new PriorityQueue<>();
        points = new ArrayList<>();

        for(int i = 0;i < N;i++) {
            PriorityQueue<Point> tmp = new PriorityQueue<>();
            tmp.addAll(pq);

            double minY = getY(tmp,x[i]);

            pq.add(new Point(minY,x[i]));
            points.add(new Point(minY,x[i]));
        }

        for(int i = 0;i < points.size();i++) {
            if (i != 0) {
                out.print(" ");
            }
            out.print(String.format("%.09f",points.get(i).y));
        }

        out.println();
    }

    public static void main(String[] args) {
        out.flush();
        new C().solve();
        out.close();
    }

    /* Input */
    private static final InputStream in = System.in;
    private static final PrintWriter out = new PrintWriter(System.out);
    private final byte[] buffer = new byte[2048];
    private int p = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (p < buflen)
            return true;
        p = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (buflen <= 0)
            return false;
        return true;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrint(buffer[p])) {
            p++;
        }
        return hasNextByte();
    }

    private boolean isPrint(int ch) {
        if (ch >= '!' && ch <= '~')
            return true;
        return false;
    }

    private int nextByte() {
        if (!hasNextByte())
            return -1;
        return buffer[p++];
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = -1;
        while (isPrint((b = nextByte()))) {
            sb.appendCodePoint(b);
        }
        return sb.toString();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

これは想定解で解き直したやつ(スッキリ)

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class C {

    int N,r;
    int[] x;
    double[] y;

    private void solve() {
        N = nextInt();
        r = nextInt();

        x = new int[N];
        y = new double[N];
        for(int i = 0;i < N;i++) {
            x[i] = nextInt();
        }

        for(int i = 0;i < N;i++) {
            double maxY = r;

            for(int j = 0;j < i;j++) {
                int distanceX = Math.abs(x[i] - x[j]);
                if (distanceX <= r * 2) {
                    maxY = Math.max(maxY,y[j] + Math.sqrt((r * 2) * (r * 2) - distanceX * distanceX));
                }
            }
            y[i] = maxY;
        }

        for(int i = 0;i < N;i++) {
            if (i != 0) {
                out.print(" ");
            }
            out.print(String.format("%.09f",y[i]));
        }

        out.println();
    }

    public static void main(String[] args) {
        out.flush();
        new C().solve();
        out.close();
    }
}

Educational Codeforces Round 35 (Rated for Div. 2) C Three Garlands

問題

codeforces.com

整数k_i(1<= i <= 3)が与えられる。
x_i,x_i + k_i,x_i + 2*k_i,x_i + 3*k_i...の値を選択できる。
整数x_1,x_2,x_3の値を定めた時、max(x_1,x_2,x_3)以上の整数すべてを選択できるかを判定する。

考察

・k_i = 1が1つ以上存在するのならYES
値の差が1なので整数すべてを覆える

・k_i = 2が2つ以上存在するのならYES
x_iが偶数、奇数を含むようにすればOK

・k_i = 3が3つ存在するのならYES
x_i mod 3 = 0
x_i mod 3 = 1
x_i mod 3 = 2
となるx_iを含むようにすればOK

・k_i = 2が1つ、k_i = 4が2つ存在するのならYES
x_i mod 2 = 0
x_i mod 4 = 1
x_i mod 4 = 3
となるx_iを含むようにすればOK

それ以外はNO

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class C {

    int k1,k2,k3;

    private void solve() {
        k1 = nextInt();
        k2 = nextInt();
        k3 = nextInt();

        int[] count = new int[1500 + 1];
        count[k1]++;
        count[k2]++;
        count[k3]++;

        if (count[1] >= 1 || count[2] >= 2 || count[3] >= 3 || (count[2] == 1 && count[4] == 2)) {
            out.println("YES");
        } else {
            out.println("NO");
        }

    }

    public static void main(String[] args) {
        out.flush();
        new C().solve();
        out.close();
    }

    /* Input */
    private static final InputStream in = System.in;
    private static final PrintWriter out = new PrintWriter(System.out);
    private final byte[] buffer = new byte[2048];
    private int p = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (p < buflen)
            return true;
        p = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (buflen <= 0)
            return false;
        return true;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrint(buffer[p])) {
            p++;
        }
        return hasNextByte();
    }

    private boolean isPrint(int ch) {
        if (ch >= '!' && ch <= '~')
            return true;
        return false;
    }

    private int nextByte() {
        if (!hasNextByte())
            return -1;
        return buffer[p++];
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = -1;
        while (isPrint((b = nextByte()))) {
            sb.appendCodePoint(b);
        }
        return sb.toString();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

AtCoder Beginner Contest 082/AtCoder Regular Contest 087 D - FT Robot

問題

D - FT Robot

解法

x座標、y座標に分けてDP
文字列Sを連続する'T','F'で分割して考えると、x座標だけ変化する、y座標だけ変化する区間が存在することが分かる。
よって、x座標、y座標の変化は独立して考えることが出来る。
あとはdp[i個目の連続する'F'の区間][x座標またはy座標の値]で「x,y座標に到達できるか」を求める。
d[i] = i個目の連続する'F'の区間の長さ(進む距離)
dp[i + 1][j + d[i]] |= dp[i][j]
dp[i + 1][j - d[i]] |= dp[i][j]

自分がハマったところは、
文字列S="FFF..."のような場合、最初はx座標は正の方向に向かって進むことを考慮するのを忘れていたこと。

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;


public class Main {

    char[] s;
    int x,y,N;
    boolean[][] xdp,ydp;
    ArrayList<Integer> vx,vy;

    private void solve() {
        s = next().toCharArray();
        N = s.length;
        x = nextInt();
        y = nextInt();

        vx = new ArrayList<>();
        vy = new ArrayList<>();

        int countF = 0;
        int countT = 0;
        for(int i = 0;i < N;i++) {
            if (s[i] == 'F') {
                countF++;
            } else {
                if (countT % 2 == 0) {
                    vx.add(countF);
                } else {
                    vy.add(countF);
                }
                countT++;
                countF = 0;
            }
        }
        if (countF > 0) {
            if (countT % 2 == 0) {
                vx.add(countF);
            } else {
                vy.add(countF);
            }
        }

        xdp = new boolean[vx.size() + 1][8000 * 2 + 1];
        ydp = new boolean[vy.size() + 1][8000 * 2 + 1];

        int add = 0;
        if (s[0] == 'T') {
            xdp[0][8000] = true;
        } else {
            xdp[1][8000 + vx.get(0)] = true;
            add++;
        }
        for(int i = 0 + add;i < vx.size();i++) {
            for(int j = 0;j < 8000 * 2 + 1;j++) {
                if (!xdp[i][j]) continue;
                if(j - vx.get(i) >= 0) {
                    xdp[i + 1][j - vx.get(i)] |= xdp[i][j];
                }

                if (j + vx.get(i) < 8000 * 2 + 1) {
                    xdp[i + 1][j + vx.get(i)] |= xdp[i][j];
                }
            }
        }

        ydp[0][8000] = true;
        for(int i = 0;i < vy.size();i++) {
            for(int j = 0;j < 8000 * 2 + 1;j++) {
                if (!ydp[i][j]) continue;
                if(j - vy.get(i) >= 0) {
                    ydp[i + 1][j - vy.get(i)] |= ydp[i][j];
                }

                if (j + vy.get(i) < 8000 * 2 + 1) {
                    ydp[i + 1][j + vy.get(i)] |= ydp[i][j];
                }
            }
        }

        if (xdp[vx.size()][x + 8000] && ydp[vy.size()][y + 8000]) {
            out.println("Yes");
            return;
        }
        out.println("No");
    }

    public static void main(String[] args) {
        out.flush();
        new Main().solve();
        out.close();
    }

    /* Input */
    private static final InputStream in = System.in;
    private static final PrintWriter out = new PrintWriter(System.out);
    private final byte[] buffer = new byte[2048];
    private int p = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (p < buflen)
            return true;
        p = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (buflen <= 0)
            return false;
        return true;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrint(buffer[p])) {
            p++;
        }
        return hasNextByte();
    }

    private boolean isPrint(int ch) {
        if (ch >= '!' && ch <= '~')
            return true;
        return false;
    }

    private int nextByte() {
        if (!hasNextByte())
            return -1;
        return buffer[p++];
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = -1;
        while (isPrint((b = nextByte()))) {
            sb.appendCodePoint(b);
        }
        return sb.toString();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

AtCoder Regular Contest 086 C - Not so Diverse

解法

整数がK種類以下になるまで、個数の少ない整数から書き換えていく(整数を消していくと考えても良い)。

まず、各整数ごとに個数をまとめて、次に個数で整数の種類数をまとめていく。
あとはK種類以下の整数になるまで、整数を書き換えていく(整数を消していく)。

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;


public class Main {

    int N,K;
    int[] A;

    private void solve() {
       N = nextInt();
       K = nextInt();
       A = new int[N];
       for(int i = 0;i < N;i++) {
           A[i] = nextInt();
       }

//       各整数ごとに個数をカウント
       int[] a = new int[200000 + 1];
       for(int i = 0;i < N;i++) {
           a[A[i]]++;
       }

//       各個数ごとにカウント
       int[] b = new int[N + 1];
       for(int i = 0;i < 200000 + 1;i++) {
           if (a[i] > 0){
               b[a[i]]++;
           }
       }

//       整数の種類数を求める
       int count = 0;
       for(int i = 0;i < 200000 + 1;i++) {
           if (a[i] > 0) {
               count++;
           }
       }

       int ans = 0;
       for(int i = 0;i < N + 1;i++) {
           int min = Math.min(count - K, b[i]);

           ans += min * i;
           count -= min;
       }

       out.println(ans);
    }

    public static void main(String[] args) {
        out.flush();
        new Main().solve();
        out.close();
    }

    /* Input */
    private static final InputStream in = System.in;
    private static final PrintWriter out = new PrintWriter(System.out);
    private final byte[] buffer = new byte[2048];
    private int p = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (p < buflen)
            return true;
        p = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (buflen <= 0)
            return false;
        return true;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrint(buffer[p])) {
            p++;
        }
        return hasNextByte();
    }

    private boolean isPrint(int ch) {
        if (ch >= '!' && ch <= '~')
            return true;
        return false;
    }

    private int nextByte() {
        if (!hasNextByte())
            return -1;
        return buffer[p++];
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = -1;
        while (isPrint((b = nextByte()))) {
            sb.appendCodePoint(b);
        }
        return sb.toString();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

COLOCON -Colopl programming contest 2018- C - すぬけそだて――ごはん――

解法

A~Bまでの整数が書かれた各カードを購入するか購入しないで全探索する。

制約等から時間計算量がO(2^35)と思ってしまうが
「...これまでに食べたどのカードに書かれた整数とも互いに素である整数の書かれたカードを食べたとき...」というこの問題の特徴を考えると
2で割り切れる整数は2枚以上購入できない、3で割り切れる整数は2枚以上購入できない、5で...(省略)
という感じで時間計算量O(2^35)も掛からない。

「2で割り切れる整数は2枚以上購入できない」ということで、全探索中に購入出来るカードは高々18枚しかない。
これを3で割り切れる,5で割り切れる,...という風に考えると十分全探索で間に合うと考えられる。

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;


public class Main {

    long A,B;
    long[] prev;

    private long gcd(long x,long y) {
        return y == 0 ? x : gcd(y,x % y);
    }

//    整数A~整数Bの各整数に対して 購入する/しない で探索
    private int dfs(long n,int it) {
        if (n == B + 1) {
            return 1;
        }

//        整数nを購入しない場合
        int ret = dfs(n + 1,it);

//        購入済みの各整数と整数nが互いに素であるかをチェック
        boolean ok = true;
        for(int i = 0;i < it;i++) {
            if (gcd(n,prev[i]) != 1) {
                ok = false;
            }
        }

//        整数nを購入する場合
        if (ok) {
            prev[it] = n;
            ret += dfs(n + 1,it + 1);
        }
        return ret;
    }

    private void solve() {
       A = nextLong();
       B = nextLong();

       prev = new long[(int)(B - A + 1)];
       int it = 0;
       out.println(dfs(A,it));
    }

    public static void main(String[] args) {
        out.flush();
        new Main().solve();
        out.close();
    }

    /* Input */
    private static final InputStream in = System.in;
    private static final PrintWriter out = new PrintWriter(System.out);
    private final byte[] buffer = new byte[2048];
    private int p = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (p < buflen)
            return true;
        p = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (buflen <= 0)
            return false;
        return true;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrint(buffer[p])) {
            p++;
        }
        return hasNextByte();
    }

    private boolean isPrint(int ch) {
        if (ch >= '!' && ch <= '~')
            return true;
        return false;
    }

    private int nextByte() {
        if (!hasNextByte())
            return -1;
        return buffer[p++];
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = -1;
        while (isPrint((b = nextByte()))) {
            sb.appendCodePoint(b);
        }
        return sb.toString();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

SRM719 Div2 Hard

考察

根ノードから任意のノードまでのパスのXORの計算を行う。

xor[V] = 根ノードから任意のノードVまでのXOR

そうすると任意のノードVから他の任意のノードUまでのパスのXORの計算結果は
xor[V] ^ xor[U]になる。これはXORの性質を考えると分かる。
A xor B = X
A xor C = Y
X xor Y = B xor C

詳しくはkmjpさんの解説記事で
kmjp.hatenablog.jp

ソースコード

下のコードでやっていることは

ノード0から任意のノードvまでのXORを求めとく。
制約からノード数<=1000なので、パスの始点ノードsと終点ノードtを全探索してxor[s]^xor[t]をSetに挿入。
0<=w[i]<=1023なのでXORの計算結果は高々1024通りしかない。
あとはSetから重複を許して値を二つ選んでXORの最大値を求める。

import java.util.HashSet;
import java.util.Set;
public class TwoDogsOnATree{

        public int maximalXorSum(int[] parent,int[] w){

            int N = parent.length + 1;
            int[] xor = new int[N];

            for(int i = 1;i < N;i++){
                int v = i;

                while(v > 0){
                    xor[i] ^= w[v-1];
                    v = parent[v-1];
                }
            }
            Set<Integer> xorSet = new HashSet<>();
            for(int i = 0;i < N;i++){
                for(int j = 0;j < N;j++){
                    xorSet.add(xor[i]^xor[j]);
                }
            }

            int ans = 0;
            for(int a : xorSet){
                for(int b : xorSet){
                    ans = Math.max(ans,a^b);
                }
            }
            return ans;
        }
    }

AtCoder Regular Contest 079 D Decrease (Contestant ver.)

考察

・公式解説
Editorial - AtCoder Regular Contest 079 | AtCoder

公式解説見ながらソースコード中に考えたこと書きました。

実験して解法につながる性質とか規則性見つけるの難しい。
こういう問題に出くわしたらどうするのが良いのだろう

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {

	long K;
	int N;

	public void solve() {
		K = nextLong();
		N = 50;

		long[] a = new long[N];

		//解説の通り、[0,1,2,3,4,5,6...,N-1]にする
		for(int i = 0;i < 50;i++){
			a[i] = i;
		}

		/*
		 * 1番目,2番目,3番目,4番目,5番目,...N番目,1番目,2番目,3番目,..みたいな感じ
		 * で1~N番目の要素を順番にそれぞれに対して操作を合計K回行う
		 */

		long x = K / N;//xはそれぞれの要素に必ず操作する回数
		long y = K % N;//先頭からy番目まで追加で操作を行う

		for(int i = 0;i < N;i++){

			a[i] += N * x;//x回N増やす
			a[i] -= (N-1)* x;//他の要素の数×一つの要素に対して必ず操作する回数
			a[i] -= y;//全ての要素の中で追加で操作する回数

			if(i < y){
				a[i] += N+1;//今見ている要素に対して追加で操作を行うとき
			}
		}

		out.println(N);
		for(int i = 0;i < N;i++){

			if(i != 0)out.print(" ");
			out.print(a[i]);
		}
		out.println();
	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}