2021-04-14

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195） B - Many Oranges

ABC

問題

atcoder.jp

考察

重要な点としては

Aグラム以上Bグラム以下というみかんの重さに下限と上限があること。

みかんの重さが整数とは限らない。

重さの合計がぴったりW（キログラム単位）であること。

みかんの個数Nが分かっている場合、
$A \le \frac{1000W} N \le B$ が成り立てば、N個のみかんで重さの合計をぴったりWにできる。

公式解説で
$AN \le 1000W \le BN$ （この考察内だと $A \le \frac{1000W} N \le B$ を式変形したものと同じ）
を見たとき、なぜこれが成り立つと重さをぴったりWにできるんだ？と思ったが、

$\frac{1000W} N$ は1000Wをみかんの個数でN等分したときのみかん1個の重さ。
N個の中で1個の重さを増やすと他の1個以上のみかんの重さが減り、逆に1個の重さを減らすと他の1個以上のみかんの重さが増えます。
（なぜなら、重さの合計は変わらずWで、みかんの重さの配分を変えているだけだから。）

このN個のみかんの重さの配分をいくら変えても、 $\frac{1000W} N$ を中心に重さの最小値Xと最大値Yの差が広がり
$A \le (X \le \frac{1000W} N \le Y) \le B$ の範囲に当てはまらない場合が出てきてしまう。
なので、XとYの差が最も小さくなる $\frac{1000W} N$ がA以上、B以下であるかどうかを判定している。

制約の $1 \le W \le 1000$ から
みかんの個数は1～1000000までの範囲だと分かる。
あとはこの範囲の中でみかんの個数で全探索をしながら、 $A \le \frac{1000W} N \le B$ が成り立つかをチェックして
最大の個数、最小の個数を出力する。

ソースコード

atcoder.jp

2021-04-13

AtCoder Beginner Contest 198 C - Compass Walking

ABC

問題

atcoder.jp

考察

原点(0, 0)からユークリッド距離でRずつしか移動できない。

移動先の座標は整数でなくてもよい。

ぴったり(X, Y)にたどり着かなければならない。

これがこの問題を解くときに大事なポイントだと思われる。

原点(0, 0)と(X, Y)間のユークリッド距離がRで割り切れる場合は
単純にユークリッド距離をRで割れば何回で(X, Y)にたどり着くか分かる。

逆にユークリッド距離がRで割り切れない場合については
(X, Y)とのユークリッド距離がR未満になるまで、(X, Y)に向かって移動する。（移動後の座標を(x, y)とする）
その後、(x, y)からユークリッド距離でR移動した座標と(X, Y)からユークリッド距離でR移動した座標
この2つが一致する座標に移動する。
そうすると、現在の座標からユークリッド距離でR移動すれば(X, Y)にぴったりだどり着ける。
つまり余分に1回移動回数を増やすことで、対応できる。

以上から
sqrt(X^2 + Y^2) / R でちょうど割り切れる場合はsqrt(X^2 + Y^2) / R
割り切れない場合はceil(sqrt(X^2 + Y^2) / R)になる。
ただ、sqrt(X^2 + Y^2) < Rの場合については2になる。

ソースコード

atcoder.jp

2018-06-26

Educational Codeforces Round 45

Codeforces 復習

Editorial
A問題
B問題
C問題
D問題
E問題
F問題
G問題(未解決)

Editorial

codeforces.com

A問題

問題

codeforces.com

$N$ 個の解説ボックスと $M$ 個の団体チームが存在しており、各団体チームに均等に解説ボックスを割り当てたい
$N$ を $M$ で割り切れないときは、各団体チームに解説ボックスを割り当てることが出来ない

1つの解説ボックスを解体するのに $a$ burles支払う
1つの解説ボックスを建てるのに $b$ burles支払う

各団体チームに同じ数の解説ボックスを配布したい時、支払うburlesの最小値を求める

考察

解説ボックスの数を $M$ (団体チーム数)で割り切れるまで
解体する( $a$ burles支払う)か
建てる( $b$ burles支払う)かどちらか一方を行うことを考えると
$N \mod M = 解体する回数$
$N - (N \mod M) = 解説ボックスを建てる回数$
が分かる
結果的に支払うburlesの最小値は $min(N \mod M \times a, (N - N \mod M) \times b)$ になる

ソースコード

Submission #39089978 - Codeforces

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

public class A {

    long N,M;
    int A,B;

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

        long mod = N % M;

        long a = A * (M - mod);
        long b = B * mod;

        long ans = Math.min(a, b);
        out.println(ans);
    }
}

B問題

問題

codeforces.com

皿の上に $N(1 \le N \le 2 \times 10^5)$ 体のバクテリアが存在する
$i$ 番目のバクテリアの大きさは $a_i(1 \le a_i \le 10^6)$ である
$K(1 \le K \le 10^6)$ という定数が与えられる

$i$ 番目のバクテリアは以下の条件を満たすとき、 $j$ 番目のバクテリアを食べることが出来る

$a_i \gt a_j$
$a_i \le a_j + K$

食べられた $j$ 番目のバクテリアは皿の上から消える( $i$ 番目のバクテリアの大きさは変化しない)

最終的に皿の上に残存しているバクテリアの数の最小値を求める

考察

まず、大きさの昇順にソートする
$a_i$ は重複する場合があるので、同じ $a_i$ はまとめる
大きさの昇順に $a_i$ を見ていき、 $a_{i-1} + K \ge a_i$ を満たす場合
$a_{i-1}$ のバクテリアを除いていく

ソースコード

Submission #39101019 - Codeforces

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

public class B {

    int N,K;
    ArrayList<Integer> a;

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

        Collections.sort(a);
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for(int v : a) {
            if (map.containsKey(v)) {
                map.put(v, map.get(v) + 1);
            } else {
                map.put(v, 1);
            }
        }
        ArrayList<Integer> b = new ArrayList<>();
        for(int v : map.keySet()) {
            b.add(v);
        }

        int ans = N;
        for(int i = 0;i < b.size() - 1;i++) {
            int j = i + 1;
            if (b.get(i) < b.get(j) && b.get(i) + K >= b.get(j)) {
                ans -= map.get(b.get(i));
            }
        }

        out.println(ans);
    }
}

C問題

問題

codeforces.com

$N(1 \le N \le 3 \times 10^5)$ 個の"(",")"のみが含まれる文字列 $s_i(1 \le i \le N)$ が与えられる

2つの文字列 $s_i, s_j$ を選び、文字列結合した結果 $s_i + s_j$ が有効な括弧文字列であるペア $(i, j)$ の数を求める
$i \neq j$ でペア $(i, j)$ と $(j, i)$ が有効な括弧文字列である場合、どちらも別々でカウントする
$i = j$ でペア $(i,j)$ と $(j, i)$ が有効な括弧文字列である場合、1つとカウントする

考察

3つパターンで $N$ 個の括弧文字列を分ける

既に有効な括弧文字列である場合
文字列の左から順に見ていく。")"を見ている時、その文字列内で"("と")"で対応できていない")"の数が1つ以上の場合
文字列の右から順に見ていく。"("を見ている時、その文字列内で"("と")"で対応できていない"("の数が1つ以上の場合

後は

$パターン1の文字列の数 \times (パターン1の文字列の数-1)$
$パターン2で対応できていない")"の個数がA個の数 \times パターン3で対応できていない"("の個数がA個の数$
$パターン3で対応できていない")"の個数がB個の数 \times パターン3で対応できていない"("の個数がB個の数$

上記のパターンをすべて足した数が解

ソースコード

Submission #39109916 - Codeforces

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

public class C {

    int N;
    String[] brackets;

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


        TreeMap<Integer, Integer> leftMinus = new TreeMap<>();
        TreeMap<Integer, Integer> rightPlus = new TreeMap<>();
        int zero = 0;
        for(int i = 0;i < N;i++) {
            char[] b = brackets[i].toCharArray();
            int L = b.length;

            int depth = 0;
            int leftCnt = 0;
            for(int j = 0;j < L;j++) {
                if (b[j] == ')') {
                    depth--;
                } else {
                    depth++;
                }

                if (depth < 0) {
                    leftCnt++;
                }
            }

            depth = 0;
            int rightCnt = 0;
            for(int j = L-1;j >=0;j--) {
                if (b[j] == '(') {
                    depth--;
                } else {
                    depth++;
                }

                if (depth < 0) {
                    rightCnt++;
                }
            }

            if (leftCnt > 0 && rightCnt > 0) {
                continue;
            }

            if (leftCnt == 0 && rightCnt == 0) {
                zero++;
                continue;
            }

            if (leftCnt > 0) {
                if (leftMinus.containsKey(depth)) {
                    leftMinus.put(depth, leftMinus.get(depth) + 1);
                } else {
                    leftMinus.put(depth, 1);
                }
            }

            if (rightCnt > 0) {
                if (rightPlus.containsKey(depth)) {
                    rightPlus.put(depth, rightPlus.get(depth) + 1);
                } else {
                    rightPlus.put(depth, 1);
                }
            }
        }

        long ans = ((long)zero) * (zero);

        for(int m : leftMinus.keySet()) {
            if (rightPlus.containsKey(-m)) {
                ans += ((long) leftMinus.get(m)) * rightPlus.get(-m);
            }
        }

        out.println(ans);
    }
}

D問題

問題

codeforces.com

頂点数が $N(1 \le N \le 1000)$ の0と1を含む正方行列で表される無向グラフ $G$ を考える
$(row, column) = (i,j)$ が1の場合は頂点 $i$ と頂点 $j$ は辺で繋がっていることを表す

無向グラフ $G$ の連結成分の数が $a(1 \le a \le N)$ 、無向グラフ $G$ の補グラフ上の連結成分の数が $b(1 \le b \le N)$ である
無向グラフ $G$ を表すことが出来るかを考える
※補グラフの説明：
補グラフ - Wikipedia

考察

$n=3,4,5$ とかのパターンで色々実験してみると
$a > 1$ の場合は $b = 1$ になることに気付く( $b > 1$ の場合は $a = 1$ )
これは補グラフの特徴として
無向グラフ $G$ 上で辺が繋がっていない頂点同士はグラフ $G$ の補グラフ $H$ 上では辺で繋がることに基づく
例えば、 $N = 4$ の $G$ 上で2つの連結成分 $x, y$ が存在し
連結成分 $x$ では頂点 $0, 1$
連結成分 $y$ では頂点 $2, 3$ を含むとする
$G$ の補グラフ $H$ では
頂点 $0$ は $2,3$ と辺で繋がり、頂点 $1$ も $2,3$ と繋がり、最終的に $H$ では1つの連結成分となる

これで $a > 1$ で $b > 1$ の場合は条件を満たす無向グラフ $G$ を表すことが出来ないことが分かった
あとは $b = 1$ の場合を考えると
連結成分の数が $a$ になるまで頂点同士を辺で繋げていけば良い
$a = 1$ の場合も $b = 1$ の時と同じ考えで解ける

特殊ケースがある
N = 2,A = 1,B = 1
N = 3,A = 1,B = 1

ソースコード

Submission #39414034 - Codeforces

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

public class D {

    int N,A,B;

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

        int min = Math.min(A ,B);
        if (min > 1) {
            out.println("NO");
            return;
        }

        if ((N == 2 && A == 1 && B == 1) || (N == 3 && A == 1 && B == 1)) {
            out.println("NO");
            return;
        }

        int[][] G = new int[N][N];

        if (A == 1) {
            for(int i = 0;i < N;i++) {
                for(int j = 0;j < N;j++) {
                    if (i == j) {
                        G[i][j] = 0;
                    } else {
                        G[i][j] = 1;
                    }
                }
            }
            for(int i = 0;i < N - B;i++) {
                G[i][i+1] = 0;
                G[i+1][i] = 0;
            }
        } else {
            for(int i = 0;i < N - A;i++) {
                G[i][i+1] = 1;
                G[i+1][i] = 1;
            }
        }

        out.println("YES");
        for(int i = 0;i < N;i++) {
            for(int j = 0;j < N;j++) {
                out.print(G[i][j]);
            }
            out.println();
        }
    }
}

E問題

問題

codeforces.com

Adilbekの家はx軸上で表される通りに存在している
通りはとても暗いので、照らすためにいくつかの照明を設置したい
通りには照明を設置するための $N(1 \le N \le 10^6)$ 箇所があり、それぞれ $0 から N-1$ に対応している
しかし、 $M(1 \le M \le N)$ 箇所にはランプが設置出来ない
それぞれパワーの違いによって異なるタイプの照明がある
位置 $x$ に設置し、パワーが $l$ である照明は区間 $[ x, x + l ]$ を照らす
照明はパワーが $1 から K(1 \le K \le N \le 10^6)$ までの異なるタイプがそれぞれ無限個売っている
客は1つのタイプしか購入できない
パワーが $l$ の照明を購入するには $a_l(1 \le a_l \le 10^6)$ のコストが掛かる
通りの全体 $[0 : N]$ を照らすための照明を購入する最小コストを求める

考察

各パワー $l(1 \le l \le K)$ について
$N$ 箇所すべて照らせるように $[x , x+l],[x + l + 1 , x + l \times 2 + 1],,,$ を照らすように貪欲に試していく。
試していく途中で $x + l + 1$ がランプが設置出来ない位置の場合は
区間 $[x+1 , x + l]$ 内(既に設置した1つ前のランプの位置と設置出来ない位置の間)でランプが設置出来る最大の位置に次のランプを設置するようにする

$N$ と $K$ の制約から間に合わないと思ってしまったが、意外と間に合う
これは各パワー $l$ を試していく中で $l$ が増加していき、ランプが照らす範囲が大きくなり、ランプを置く候補が絞られていくイメージから

ソースコード

Submission #39438365 - Codeforces

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

public class E {

    int N,M,K;
    int[] s,a;

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

        s = new int[M];
        for(int i = 0;i < M;i++) {
            s[i] = nextInt();
        }
        a = new int[K + 1];
        for(int i = 1;i <= K;i++) {
            a[i] = nextInt();
        }

        boolean[] blocked = new boolean[N + 1];
        for(int i = 0;i < M;i++) {
            blocked[s[i]] = true;
        }

        int[] notBlockIndex = new int[N + 1];
        notBlockIndex[N] = N;
        int index = 0;
        for(int i = 0;i < N;i++) {
            if (!blocked[i]) {
                index = i;
            }
            notBlockIndex[i] = index;
        }

        long ans = Long.MAX_VALUE;
        for(int i = 1;i <= K;i++) {
            int now = 0;
            long count = 0;

            if (blocked[now]) {
                continue;
            }

            while(now < N) {
                int next = Math.min(N, now + i);
                int nextnext = notBlockIndex[next];

                if (now == nextnext) {
                    break;
                }
                now = nextnext;
                count++;
            }

            if (!blocked[now] && now >= N) {
                ans = Math.min(ans, count * a[i]);
            }
        }

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

F問題

問題

codeforces.com

$N(1 \le N \le 2 \times 10^5)$ 個の分岐点と $M(0 \le M \le 2 \times 10^5)$ 本のパイプで構成されている水分配システムがある
$i(1 \le i \le M)$ 番目のパイプは分岐点 $x_i$ と $y_i$ 間に接続されている
$f_i >= 0$ の場合は $x_i$ から $y_i$ に向かって $f_i$ の水が流れる
$f_i < 0$ の場合は $y_i$ から $x_i$ に向かって $|f_i|$ の水が流れる
この $f_1,f_2,f_3, ..., f_M$ を求めたい
$i(1 \le i \le N)$ 番目の分岐点に水の流入量と水の放出量の差 $s_i(-10^4 \le s_i \le 10^4)$ が定められている
$s_i >= 0$ の場合は $i$ 番目の分岐点への水の流入量が水の放出量より $s_i$ 多いことを表す
$s_i < 0$ の場合は $i$ 番目の分岐点からの水の放出量が水の流入量より $|s_i|$ 多いことを表す
$f_1,f_2,f_3, ..., f_M$ が上記の要件を満たすように出来るか
出来る場合は $f_1,f_2,f_3, ..., f_M$ を出力し、不可能な場合-1を出力する

考察

要件を満たす $f_i$ を求められるかは各分岐点の放出量の総和と各分岐点の流出量の総和が等しく出来るかで分かる

適当な分岐点 $i$ を決め、パイプ $k$ で接続している分岐点 $j$ に水を放出または、 $j$ から $i$ へ水を流入すること考える
パイプが分岐点 $i$ から $j$ に接続されている場合、 $f_k = s_i \times (-1)$
パイプが分岐点 $j$ から $i$ に接続されている場合、 $f_k = s_i$
そして $s_j$ から $s_i$ 分の流量を加える

これを分岐点 $j$ と接続されている次の分岐点間のパイプについて同様に考え、繰り返していき
すべてのパイプについて流量をDFS等で貪欲に決めていく

ソースコード

Submission #39543693 - Codeforces

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

public class F {

    int N,M;
    int[] x,y;
    long[] s,flow,sum;
    boolean[] visited;
    ArrayList<Edge>[] graph;

    private class Edge {
        int ind, to, dir;
        public Edge(int ind, int to, int dir) {
            this.ind = ind;
            this.to = to;
            this.dir = dir;
        }
    }

    private void dfs(int n) {
        visited[n] = true;

        for(Edge e : graph[n]) {
            if (visited[e.to]) {
                continue;
            }
            dfs(e.to);
            flow[e.ind] = s[e.to] * e.dir;
            s[n] += s[e.to];
        }
    }


    @SuppressWarnings("unchecked")
    private void solve() {
        N = nextInt();
        s = new long[N];
        sum = new long[N];
        for(int i = 0;i < N;i++) {
            s[i] = nextInt();
        }
        M = nextInt();
        x = new int[M];
        y = new int[M];
        for(int i = 0;i < M;i++) {
            x[i] = nextInt()-1;
            y[i] = nextInt()-1;
        }

        long sum = 0;
        for(int i = 0;i < N;i++) {
            sum += s[i];
        }
        if (sum != 0) {
            out.println("Impossible");
            return;
        }

        graph = new ArrayList[N];
        for(int i = 0;i < N;i++) {
            graph[i] = new ArrayList<>();
        }

        for(int i = 0;i < M;i++) {
            graph[x[i]].add(new Edge(i, y[i], 1));
            graph[y[i]].add(new Edge(i, x[i], -1));
        }

        flow = new long[M];
        visited = new boolean[N];
        dfs(0);

        out.println("Possible");
        for(int i = 0;i < M;i++) {
            out.println(flow[i]);
        }
        out.println();
    }
}

G問題(未解決)

問題

codeforces.com

$N$ 個の頂点を含む木が与えられる
頂点 $i$ には数値 $a_i$ が書かれている
関数 $g(x,y)$ は頂点 $x$ と頂点 $y$ 間のパスに含まれる頂点( $x,y$ を含める)に書かれている数値の最大公約数を求める
$1から2 \times 10^5$ の各整数に対して $g(x,y)$ の計算結果がその整数に対応している $(x,y)$ のペア数を数えたい

考察

ソースコード

2018-06-05

Codeforces #486 Div3

Codeforces

Editorial
A問題
B問題
C問題
D問題
E問題
F問題

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_i$ と $a_j$ を選び、以下の操作が出来る $(i \neq j)$

$a_i$ と $a_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,x$ と $j,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)$ が与えられる
$N$ の $i$ 桁目と $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);
        }
    }
}

2018-06-01

yukicoder long contest 1 stick xor

yukicoder Marathon

問題

No.5002 stick xor - yukicoder

考察

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

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

2017-12-30

Good Bye 2017 C New Year and Curling

Codeforces

問題

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

2017-12-29

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

Codeforces Educational Round

問題

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