tookunn’s diary

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

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

yukicoder No514 宝探し3

考察

  • 座標(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))

Codeforces #397 Div1+Div2 D Artsem and Saunders

考察

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

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

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





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

SRM 708 Div2 Hard

考察

うーん。これ思いつく発想ってどうやるんだろ。

「X[i]を決めた時のiより左、右に分けた時の左側、右側それぞれの文字列が左右対称であることを思いつく」 ことかなぁ

ソースコード

public class PalindromicSubseq2 {
	static final int MOD = (int)1e9 + 7;

	public int solve(String s){
		char[] S = s.toCharArray();
		char[] R = new StringBuilder(s).reverse().toString().toCharArray();
		int N = S.length;
		long[][] dp = new long[N+1][N+1];

		for(int i = 0;i < N+1;i++){
			dp[i][0] = 1;
			dp[0][i] = 1;
		}

		for(int i = 1;i < N + 1;i++){
			for(int j = 1;j < N + 1;j++){
				dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + MOD) % MOD;
				dp[i][j] %= MOD;
				if(S[i-1] == R[j-1]){
					dp[i][j] += dp[i-1][j-1] % MOD;
					dp[i][j] %= MOD;
				}
			}
		}

		long ans = 0;
		for(int i = 1;i < N + 1;i++){
			ans ^= (dp[i-1][N-i] * i % MOD);
		}
		return (int)ans;
	}
}