tookunn’s diary

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

Codeforces #486 Div3

Editorial

codeforces.com

A問題

問題

codeforces.com

長さN(1\le N\le 100)の数列a(1 \le a_i \le 100)が与えられる
数列aから値が重複しないようにK(1 \le K \le N)個取り出せるか

取り出せる場合はK個のa_i(1 \le i \le K)iを出力する

考察

aに含まれる整数の種類がK個未満なら取り出すのは不可能
K個以上の場合はmap[a_i] = i

ソースコード

Submission #38839259 - Codeforces

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

public class A {

    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[] map = new int[100 + 1];

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

        ArrayList<Integer> ans = new ArrayList<>();
        for(int i = 0;i < 100 + 1;i++) {
            if (map[i] > 0) {
                ans.add(map[i]);
            }
        }

        if (ans.size() < K){
            out.println("NO");
            return;
        }

        out.println("YES");
        for(int i = 0;i < K;i++) {
            if (i != 0) {
                out.print(" ");
            }
            out.print(ans.get(i));
        }
        out.println();
    }
}

B問題

問題

codeforces.com

N(1 \le N \le 100)個の文字列S(1 \le len(S_i) \le 100)が与えられる
S_{i-1}が部分文字列としてS_iに含まれるようにN個の文字列を並べ替えが可能か
可能な場合、並べ替えたN個の文字列Sを出力する

考察

文字列の長さでN個の文字列Sをソートして
S_{i-1}が部分文字列としてS_iに含まれているかをi(1 \le i \le N-1)についてチェック

文字列の長さでソートするのはよく考えると分かる

  • len(S_{i-1}) = len(S_i)の場合S_{i-1}が部分文字列としてS_iに含まれるのはS_{i-1} = S_iの場合のみ
  • 並べ替えが可能な場合、S_i(1 \le i \le N-1)が部分文字列としてS_j(i \lt j \le N)に必ず含まれていなければいけない

ソースコード

Submission #38842064 - Codeforces

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

public class B {

    int N;
    String[] s;

    private void sort(String[] s) {

        for(int i = 0;i < N;i++) {
            for(int j = i+1;j < N;j++) {
                if (s[i].length() > s[j].length()) {
                    String tmp = s[i];
                    s[i] = s[j];
                    s[j] = tmp;
                }
            }
        }
    }

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

        sort(s);
        for(int i = 0;i < N-1;i++) {
            if (s[i+1].indexOf(s[i]) == -1) {
                out.println("NO");
                return;
            }
        }
        out.println("YES");
        for(int i = 0;i < N;i++) {
            out.println(s[i]);
        }
    }
}

C問題

問題

codeforces.com

 K(2 \le K \le 2 \times 10^5)個の長さ n_i(1 \le n_i \lt 2 \times 10^5)の各数列 a(-10^4 \le a_i \le 10^4)が与えられる
各数列の長さの総和 (\sum_{i = 0}^K n_i) 2 \times 10^5以下である

2つの数列a_ia_jを選び、以下の操作が出来る(i \neq j)

  • a_ia_jからそれぞれ1つずつa_{i,x},a_{j,y}を取り除く(1 \le x\le n_i), (1 \le y \le n_j)

操作後、数列 a_iの総和と数列 a_jの総和を等しくすることが可能か

可能な場合は i,xj,yを出力する

考察

操作後の2つの数列の総和を等しくしたいので、どの数列からどの値を取り除いて数列の総和はどうなるのかをあらかじめ求めておく。(以下のようなペアを作っておく)
 (要素を取り除いた後の総和, 何番目の数列, 何番目の要素) = (sum, i, x)

(sum, i,x)のペアをソートする
あとは各ペアに対してsumが同じでiが異なるもう一つペアが存在するか二分探索
存在する場合はその2つのペアが解

ソースコード

Submission #38854484 - Codeforces

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

public class C {

    int K;
    int[] N;
    int[][] S;
    ArrayList<D> list;

    private class D implements Comparable<D> {
        long sum;
        int ij,xy;
        public D(long sum,int ij,int xy) {
            this.sum = sum;
            this.ij = ij;
            this.xy = xy;
        }

        public int compareTo(D other) {
            if (this.sum != other.sum) {
                return Long.compare(this.sum, other.sum);
            }

            if (this.ij != other.ij) {
                return Integer.compare(this.ij, other.ij);
            }
            return Integer.compare(this.xy, other.xy);
        }

        public String toString() {
            return "[sum=" + this.sum + " ij=" + this.ij + " xy=" + this.xy + "]";
        }
    }


    private void solve() {
        K = nextInt();
        N = new int[K];
        S = new int[K][];
        list = new ArrayList<>();

        for(int i = 0;i < K;i++) {
            N[i] = nextInt();
            S[i] = new int[N[i]];
            long sum = 0;
            for(int j = 0;j < N[i];j++) {
                S[i][j] = nextInt();
                sum += S[i][j];
            }

            for(int j = 0;j < N[i];j++) {
                long removedSum = sum - S[i][j];
                list.add(new D(removedSum, i + 1, j+1));
            }
        }

        Collections.sort(list);

        ArrayList<D> tmpList = new ArrayList<>();
        D pre = list.get(0);
        for(int i = 1;i < list.size();i++) {
            D next = list.get(i);

            if (!(pre.sum == next.sum && pre.ij == next.ij)) {
                tmpList.add(pre);
                pre = next;
            }
        }
        tmpList.add(pre);
        list = tmpList;

        for(int i = 0;i < list.size();i++) {
            D d1 = list.get(i);

            int low = i;
            int high = list.size();

            while(high - low > 1) {
                int mid = high + low >> 1;
                D d2 = list.get(mid);
                if (d1.compareTo(d2) <= 0) {
                    high = mid;
                } else {
                    low = mid;
                }
            }

            if (high != list.size()) {
                D d2 = list.get(high);
                if (d1.sum == d2.sum && d1.ij != d2.ij) {
                    out.println("YES");
                    out.println(d1.ij + " " + d1.xy);
                    out.println(d2.ij + " " + d2.xy);
                    return;
                }
            }
        }

        out.println("NO");
    }
}

D問題

問題

codeforces.com

数直線上にN(1 \le N \le 2 \times 10^5)個の点x_i(-10^9 \le x_i \le 10^9)が存在する
各点同士の距離が2の累乗である点集合を出来るだけ集合に含まれる点の数が多くなるように選びたい

点集合に含まれる点の数の最大値と点を出力する

考察

よく考えたら、4つ以上の点を集合に含めることが出来ないことが分かる

例として、3つの点X,Y,Zを考える(X \lt Y \lt Z)
点Xと点Yの距離を 2^a
点Yと点Zの距離を 2^b
とすると点Xと点Zの距離を 2^nの形にするには2^a = 2^bである必要がある

ここで4つ目の点Wを加えるとする (X \lt Y \lt Z \lt W)
点Zと点Wの距離を 2^c
上記の 2^a = 2^bを考えると 2^a = 2^b = 2^cから
点Xと点Wの距離は 2^a + 2^b + 2^cとなり、2の累乗の形に出来ないので、3つまで点を見れば良いことが分かる

「距離」と「点X」を決め打ちして「点Xの位置-距離」または「点Xの位置+距離」に点が存在するならば
その点を集合に追加していく

ソースコード

Submission #38969303 - Codeforces

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.NoSuchElementException;

public class D {

    int N;
    ArrayList<Integer> x;

    private void solve() {
        N = nextInt();
        x = new ArrayList<>();
        for(int i = 0;i < N;i++) {
            x.add(nextInt());
        }

        Collections.sort(x);

        int[] ans = new int[3];
        int size = 0;
        for(int v : x) {
            for(int bit = 0;bit < 31;bit++) {

                int small = v - (1 << bit);
                int big = v + (1 << bit);

                int ind1 = Collections.binarySearch(x, small);
                int ind2 = Collections.binarySearch(x, big);

                if (ind1 >= 0 && ind2 >= 0 && size < 3) {
                    ans[0] = small;
                    ans[1] = v;
                    ans[2] = big;
                    size = 3;
                }

                if (ind1 >= 0 && ind2 < 0 && size < 2) {
                    ans[0] = small;
                    ans[1] = v;
                    ans[2] = -1;
                    size = 2;
                }

                if (ind1 < 0 && ind2 >= 0 && size < 2) {
                    ans[0] = v;
                    ans[1] = big;
                    ans[2] = -1;
                    size = 2;
                }
            }
        }

        if (size == 0) {
            out.println(1);
            out.println(x.get(0));
            return;
        }

        out.println(size);
        for(int i = 0;i < size;i++) {
            if (i != 0) {
                out.print(" ");
            }
            out.print(ans[i]);
        }
        out.println();

    }
}

E問題

問題

codeforces.com

整数 N(1 \le N \le 10^9)が与えられる
Ni桁目とi+1桁目を交換する操作(交換操作)が出来る(交換操作後に先頭から0が1文字以上続く整数にするような交換操作は出来ない)
整数Nが25で割り切れる数になるように交換操作を繰り返した場合の交換操作回数の最小値を求めたい

25で割り切れる数に出来ない場合は-1を出力する

考察

25で割り切れる数の下2桁に注目すると
00,25,50,75の繰り返しになること気付くので、下2桁をその4パターンに絞る

まず、下2桁が 25になる場合について考える
交換操作回数を最小にしたいので、下1桁目から一番近い5を持つ桁(下1桁目も含む)から 5を交換操作をしながら下1桁目に配置する
下2桁目も同様に 2を持つ一番近い桁(下1桁目は除く)から交換操作をしながら下2桁目に配置する
その後、先頭1桁目が0の場合は0ではない値を持つ桁から、先頭に値を交換操作を行いながら配置する

下2桁が25になるような最小の交換操作回数は
下1桁目を5にするための交換操作回数 + 下2桁目を2にするための交換操作回数 + 先頭1桁目を0以外にするための交換操作回数

 00, 50, 75も同じように実際に交換操作を行いながら、交換操作回数の最小値を求める

ソースコード

Submission #39022664 - Codeforces

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

public class E {

    char[] N;

    private void swapFromLToR(int l,int r,char[] ch) {
        for(int k = l;k < r;k++) {
            char tmp = ch[k];
            ch[k] = ch[k+1];
            ch[k+1] = tmp;
        }
    }

    private void swapFromRToL(int l,int r,char[] ch) {
        for(int k = r;k > l;k--) {
            char tmp = ch[k];
            ch[k] = ch[k-1];
            ch[k-1] = tmp;
        }
    }

    private long toLong(char[] ch) {
        long ret = 0L;
        for(char c : ch) {
            ret *= 10;
            ret += c - '0';
        }
        return ret;
    }

    private int calc(char[] ch,char a,char b) {

        int ret = 0;

        int r = -1;
        for(int i = ch.length-1;i >= 0;i--) {
            if (ch[i] == b) {
                r = i;
                break;
            }
        }
        if (r == -1) {
            return Integer.MAX_VALUE;
        }
        swapFromLToR(r,ch.length-1 ,ch);
        ret += ch.length-1 - r;

        int l = -1;
        for(int i = ch.length-2;i >= 0;i--) {
            if (ch[i] == a) {
                l = i;
                break;
            }
        }
        if (l == -1) {
            return Integer.MAX_VALUE;
        }
        swapFromLToR(l, ch.length-2,ch);
        ret += ch.length-2 - l;

        if (ch[0] == '0') {
            int z = -1;
            for(int i = 1;i < ch.length;i++) {
                if (ch[i] != '0') {
                    z = i;
                    break;
                }
            }

            if (z == -1) {
                return Integer.MAX_VALUE;
            }

            swapFromRToL(z, 0, ch);
            ret += z;
        }

        long n = toLong(ch);
        if (n % 25 == 0) {
            return ret;
        }
        return Integer.MAX_VALUE;
    }

    private void solve() {
        N = next().toCharArray();

        int ans = calc(Arrays.copyOf(N,N.length),'2','5');
        ans = Math.min(ans,calc(Arrays.copyOf(N,N.length),'5', '0'));
        ans = Math.min(ans,calc(Arrays.copyOf(N,N.length),'7', '5'));
        ans = Math.min(ans,calc(Arrays.copyOf(N,N.length),'0', '0'));

        if (ans == Integer.MAX_VALUE) {
            out.println(-1);
        } else {
            out.println(ans);
        }
    }
}

F問題

問題

codeforces.com

数直線上でPolycarpはx=0からx=a(1 \le a \le \lceil \frac{n}{2} \rceil)に移動したい(左から右への移動のみ可能)
n(1 \le n \le 2000)個の雨が降っている区間[l_i,r_i](0 \le l_i \lt r_i \le a)が与えられ、(この区間同士は重ならない)
さらにm(1 \le m \le 2000)個の傘の位置x_i(0 \le x_i \le a)、重さ p_i(, 1 \le p_i \le 10^5)が与えられる
Polycarpは初めにx = 0から出発する時は傘を持っていない

Polycarpはx = 0からx = aに移動する間、傘を拾ったり、捨てることができ、傘はいくつでも拾うことが出来る
Polycarpは雨で濡れたくないので、雨が降っている区間を移動している間は少なくとも1つ以上の傘を持っている必要がある

雨が降っていない区間では傘を持っている必要は無く、雨が降っている区間内で傘を交換出来る
1単位移動するごとに持っている傘の重さの総和の分だけ疲労が増加する
 x = 0から x = aに移動する際、出来るだけ疲労が少ないようにしたいので、
疲労の最小値を求める

 x= 0から x = aに移動が出来ない場合、-1を出力する

考察

dp[i + 1][j] := x=iに移動する際に傘jを持って移動する最小の疲労の総和
傘を持っていない状態をj=MとしてDPをする

基本的にはx=0,1,2,3,4...のように1単位ずつ移動することを考えると、複数の傘を同時に持つのは最適ではないことが分かり
どの傘をx=iの時に持っていればよいかをさらに考えるとDPでまとめられるかという発想になりそう

実装に関しては最初メモ化再帰で実装していたがなぜかWAが取れず、結局forDPに直して通した

ソースコード

Submission #39193925 - Codeforces

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

public class F {
    private static final long INF = (long)1e17+7;
    int A,N,M;
    int[] U;
    long[] P;
    boolean[] R;
    long[][] dp;

    private void solve() {
        A = nextInt();
        N = nextInt();
        M = nextInt();

        R = new boolean[A + 1];
        for(int i = 0;i < N;i++) {
            int l = nextInt();
            int r = nextInt();

            for(int j = l;j < r;j++) {
                R[j] = true;
            }
        }

        U = new int[A + 1];
        Arrays.fill(U, -1);
        P = new long[M];
        Arrays.fill(P, INF);
        for(int i = 0;i < M;i++) {
            int x = nextInt();
            P[i] = nextInt();
            if (U[x] == -1 || P[U[x]] >= P[i]) {
                U[x] = i;
            }
        }

        dp = new long[A + 1][M + 1];
        for(int i = 0;i < A + 1;i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][M] = 0;
        for(int i = 0;i < A;i++) {
            for(int j = 0;j < M + 1;j++) {
                if (dp[i][j] == INF) {
                    continue;
                }
                if (!R[i]) {
                    dp[i + 1][M] = Math.min(dp[i + 1][M],dp[i][j]);
                }

                if (j < M) {
                    dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + P[j]);
                }

                if (U[i] != -1) {
                    dp[i + 1][U[i]] = Math.min(dp[i + 1][U[i]], dp[i][j] + P[U[i]]);
                }
            }
        }

        long ans = INF;
        for(int i = 0;i < M + 1;i++) {
            ans = Math.min(ans, dp[A][i]);
        }

        if (ans == INF) {
            out.println(-1);
        } else {
            out.println(ans);
        }
    }
}

yukicoder long contest 1 stick xor

考察

愚直にやって終わった感じでした。
愚直にやる以外は全然思いつかなかった。

1ターン毎に現在の盤面から最も多く漆黒→純白に反転できる操作を盤面に適用していく。
操作対象となるセル(x,y)のx,yはランダムに決定した。
・xは1~N-L,yはランダム(範囲1~N-L)
・yは1~N-L,xはランダム(範囲1~N-L)
あとは単純に漆黒→純白に反転できる数が最も多い操作を選んで盤面に適用して、次のターンで繰り返し...

ソースコード

最終サブミット
https://yukicoder.me/submissions/260603

# coding: utf-8
import random
from heapq import heappush,heappop

#操作opを盤面gridに適用する
def operation_grid(op, grid):
    rev_grid = grid
    #縦方向の操作
    if op[1] == op[3]:
        length = op[2] - op[0] + 1
        for i in range(length):
            rev_grid[op[0]-1+i][op[1]-1] = (grid[op[0]-1+i][op[1]-1]+1)&1
    #横方向の操作
    if op[0] == op[2]:
        length = op[3] - op[1] + 1
        for i in range(length):
            rev_grid[op[0]-1][op[1]-1+i] = (grid[op[0]-1][op[1]-1+i]+1)&1
    return rev_grid
#(x,y)=(base_x,base_y)
#(x,y)のセルから横方向に幅length高さ1の範囲の漆黒のセル数をカウント
def count_black_horizon(grid, base_x, base_y, length):
    return grid[base_y][base_x:base_x + length].count(1)
#(x,y)=(base_x,base_y)
#(x,y)のセルから縦方向に幅1高さlengthの範囲の漆黒のセル数をカウント
def count_black_vertical(grid, base_x, base_y, length):
    return [grid[i][base_x] for i in range(base_y,base_y + length)].count(1)

N,K = map(int,input().split())
L = list(map(int,input().split()))
A = [list(map(int,list(input()))) for i in range(N)]

#出力する操作
operation = []
#適当な値
P = 3
for k in range(K):
    #(-漆黒から純白への反転数, [出力する操作])
    hq = []
    #N-L[k]=盤面からはみ出ない最上、最左
    for x in range(N-L[k]):
        for i in range(P):
            #yはランダム値(0~N-L[k])
            y = random.randint(0, N-L[k])

            #(x,y)のセルから漆黒から純白に反転する数を求める
            horizon_cnt = count_black_horizon(A, x, y, L[k])
            vertical_cnt = count_black_vertical(A, x, y, L[k])
            if horizon_cnt < vertical_cnt:
                heappush(hq, (-vertical_cnt, [y+1, x+1, y+L[k], x+1]))
            else:
                heappush(hq, (-horizon_cnt, [y+1, x+1, y+1, x+L[k]]))
    for y in range(N-L[k]):
        for i in range(P):
            #xはランダム値(0~N-L[k])
            x = random.randint(0, N-L[k])

            #(x,y)のセルから漆黒から純白に反転する数を求める
            horizon_cnt = count_black_horizon(A, x, y, L[k])
            vertical_cnt = count_black_vertical(A, x, y, L[k])
            if horizon_cnt < vertical_cnt:
                heappush(hq, (-vertical_cnt, [y+1, x+1, y+L[k], x+1]))
            else:
                heappush(hq, (-horizon_cnt, [y+1, x+1, y+1, x+L[k]]))
    #漆黒から純白へ最も多く反転できる操作を取り出す
    cnt, op = heappop(hq)
    #操作を盤面に適用
    A = operation_grid(op, A)
    operation.append(op)

print('\n'.join([' '.join(list(map(str,op))) for op in operation]))

反省

愚直のその先を全然考察出来なかった。
ラソンっぽい思考難しい

学びの参考にしたい

hoikoro.hatenablog.com

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