2017-12-20

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

ABC ARC

問題

解法

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());
    }
}

2017-12-11

AtCoder Regular Contest 086 C - Not so Diverse

ARC ABC

問題

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());
    }
}

2017-12-10

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

COLOCON

問題

colopl2018-qual.contest.atcoder.jp

解法

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());
    }
}

2017-08-15

SRM719 Div2 Hard

SRM

問題

TopCoder Statistics - Problem Statement

考察

根ノードから任意のノードまでのパスの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;
        }
    }

2017-08-01

AtCoder Regular Contest 079 D Decrease (Contestant ver.)

ARC

問題

arc079.contest.atcoder.jp

考察

・公式解説
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());
	}
}

2017-05-06

yukicoder No514 宝探し３

yukicoder

問題

http://yukicoder.me/problems/no/514

考察

座標 $(0,0)$ と座標 $(AX,AY)$ のマンハッタン距離は $AX+AY$ である。（ $AX+AY=A$ とする）

そこで、座標 $(AX+AY,0)$ と座標 $(AX,AY)$ のマンハッタン距離 $AX+AY-AX+AY=B$ を考える。（y座標を求めるためにx座標を0に固定する）

すると、 $B=AY+AY=2*AY$ となり、 $AY=B/2$ と出来る。これで $AY$ は求まった。

あとは $A-AY=AX$ となり、座標 $(AX,AY)$ が求まった。( $A=AX+AY$ なので)

ソースコード

import sys
def query(p):
	print(p[0],p[1])
	sys.stdout.flush()
	ret = int(input())
	if ret == 0:
		sys.exit(0)
	return ret
a=query((0,0))
b=query(((a,0)))
query((a-b//2,b//2))

2017-02-16

Codeforces #397 Div1+Div2 D Artsem and Saunders

Codeforces

問題

codeforces.com

考察

多分これは,与えられた2つの式

$g(h(x)) = x \{x \in m\}$

$h(g(x)) = f(x) \{x \in n\}$

から、式を変形して考察を進めれば良いのかな？

@tookunn_1213 この単射ではないっていうのはh(a) = h(b)の場合,h(a) = h(b) = Aとして、g(h(a)) = a,g(h(b)) = bで,g(A) = a,bはaかbどちらかに一意に定まっていないということか
— tookunn (@tookunn_1213) 2017年2月16日

@tookunn_1213 h(g(x))とh(g(y))は同一の値になることが分かって、g(h(g(x))) = g(h(g(y)))でなきゃいけないからg(x) = g(y)であるということかな（説明が下手）
— tookunn (@tookunn_1213) 2017年2月16日

@tookunn_1213 メモhttps://t.co/phi9xhu1uZ
— tookunn (@tookunn_1213) 2017年2月16日

参考：
pekempey.hatenablog.com

ソースコード

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

public class D {

	int N;
	int[] g;
	ArrayList<Integer> h;
	HashMap<Integer,Integer> map;


	public void solve() {
		N = nextInt();
		g = new int[N];
		h = new ArrayList<Integer>();
		map = new HashMap<Integer,Integer>();

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

			int f = nextInt()-1;
			/*
			 * fの値ごとにまとめて適当に値を割り当てる
			 * 今回はmap.size()を割り当てる
			 * hには重複なしのfの値を挿入
			 */
			if(!map.containsKey(f)){
				map.put(f, map.size());
				h.add(f);
			}
			
			//fの値をkeyにして適当に割り当てた値をg[i]に
			g[i] = map.get(f);
		}

		for(int i = 0;i < map.size();i++){
			//g(h(x)) = x
			if(g[h.get(i)] != i){
				out.println(-1);
				return;
			}

		}

		out.println(map.size());
		for(int i = 0;i < N;i++){
			if(i != 0)out.print(" ");
			out.print(g[i]+1);
		}
		out.println();
		for(int i = 0;i < map.size();i++){
			if(i != 0)out.print(" ");
			out.print(h.get(i)+1);
		}
		out.println();
	}

	public static void main(String[] args) {
		out.flush();
		new D().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());
	}
}

tookunn’s diary

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

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

問題

解法

ソースコード

AtCoder Regular Contest 086 C - Not so Diverse

問題

解法

ソースコード

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

問題

解法

ソースコード

SRM719 Div2 Hard

問題

考察

ソースコード

AtCoder Regular Contest 079 D Decrease (Contestant ver.)

問題

考察

ソースコード

yukicoder No514 宝探し３

問題

考察

ソースコード

Codeforces #397 Div1+Div2 D Artsem and Saunders

問題

考察

ソースコード