Javaで進める競プロ日記

1 モチベーション
2 目標
3 モチベーション維持方法
4 毎週末詰まったところを追記する
5 レートの変化

競技プログラミングをJavaではじめました。

この記事で各内容は以下です。

毎週の勉強メモ
モチベーションの変遷メモ
目標のメモ
毎月の進捗（レート変化・Atcoder ProblemsのAC数）

すべてこの記事で一元管理します。というのも、この記事が育つ→モチベ維持につながるため。記事数が増えてもあまり見返すことはなく、モチベも維持しずらいため。あまりにもでかくなったら分割するかも。

モチベーション

2022年の4月から転職活動する決意をしたため、AtCoderのレートを上げることで実力アップ＋転職活動で見せれるものを増やすこと【20210531追記】
会社でJavaを使ったツールをよく開発するので、早く正確に実装できるようになりたい。【20210531追記】

目標

2021年の11月までに、茶色になること【20210531追記】
2022年の4月までには、緑色になること【20210531追記】

モチベーション維持方法

レートが下がるとモチベーションが下がることがあるので、その際の維持する方法をメモ。

この記事を更新することで、過去を見返して成長をちょっと感じる。
AtcorderProblemsの問題のAC数が、先月より増加していれば少しは成長したと思える。
自作のAtCoderのライブラリを充実させる。

毎週末詰まったところを追記する

随時更新します。

区間の共通部分を求める【20210628追記】

区間 $[X, Y], [X, Y), (X, Y], (X, Y)$ とは？

閉区間 $[X, Y]$ は、 $X$ 以上 $Y$ 以下の全ての実数からなる区間

半開区間 $[X, Y)$ は、 $X$ 以上 $Y$ 未満の全ての実数からなる区間

半開区間 $(X, Y]$ は、 $X$ より大きく $Y$ 以下の全ての実数からなる区間

開区間 $(X, Y)$ は、 $X$ より大きく $Y$ 未満の全ての実数からなる区間

を表します。一言で言うと、角括弧 $[]$ を使っている側は端点を含み、丸括弧 $()$ を使っている側は端点を含みません。

ABCの207のCで出会う。共通部分の判定をするために、すべて閉区間に変換する前処理が必要となる。

すべて閉区間にするために、±0.5することによって判定が可能だが、±1.0してしまったのでACできなかった。

式を立てる【20210628追記】

ABCの207のBで出会う。この問題では目標達成可能判定を判定する必要があり、その判定式を立てずに実行してしまった。

A+B*x = C*x*D
x = A/(CD-B）

つまり、xの最大値はAであることが分かる。このように式を立ててループの上限を見積もることが重要。

深さ優先探索【20210606追記】

ABC204のCで出会う。問題としてはグラフの問題の始点と終点のパターンの列挙であり、深さ優先探索で解くことができた。

しかし、１問TLEになってしまった。TLEの解消に、すでに始点と終点の数え上げが完了している場合は、その計算結果を再利用することで探索を打ち切るようにした。（自分の提出）の６２行目。

条件を満たす値を探す（２分木探索）【20210530追記】

ABC146のCで出会う。大雑把に言えば、条件を満たすものの内、最大のものを出力するというもの。

１から10^9という範囲で条件を満たすものを探す場合、愚直に先頭から確認していくとTLEとなる。また条件からある程度初期値を探索対象に近づけておくこともでも問題は解けそう。

探索→２分木探索はすぐに思いつき実装可能なものにしておく。

long max = (long)Math.pow(10, 9);
long ok = -1;
long ng = max+1;
while(ok+1!=ng) {
            long mid = (ok+ng)/2;
            long money = a*mid + b*(long)String.valueOf(mid).length();
            if(money <= x)ok = mid;
            else ng = mid;

}
System.out.println(ok);

okとngの範囲を探索範囲の１つ外側にしておくことがポイント。それによりwhile(ok+1!=ng)の部分でコーナーケースも条件を満たす。

最大値や最大値の２番目を求める【20210530追記】

ARC121のAで出会う。最大値や最大値の次などを求める際の備忘。自分的には２つある。

for文中で大小比較して、最大値・最大値の２番目を更新
sortしてインデックスが[0] or を取得（降順ソート後）

普段は何も考えず①をやっていたが、②の方が便利だということに気づく。計算量は①の方が良いがfor文の中が煩雑になりバグを作りこみやすい。また最大値から５番目などという話になると更にややこしくなる。

最大値・最小値の何番目→ソートと意識と考えるようにする。

ではJavaで配列をソートはArrays.sortが便利。

Integer[] array = new Integer[]{4, 3 ,2, 1};
Arrays.sort(array, Comparator.naturalOrder());
System.out.println(Arrays.toString(array));

二次元配列の場合は以下のように、Comparatorを生成すればよい。

Integer[][] array2 = new Integer[][]{
                {4, 1},
                {3, 2},
                {2, 3},
};
Arrays.sort(array2, Comparator.comparingInt(o -> o));
// or
//  Arrays.sort(array2, (o1, o2) -> o1 - o2);
for(int i=0; i<array2.length; ++i) {
      System.out.println(Arrays.toString(array2[i]));
}

Comparator#comparingXXXといったように型に合わせたstaticメソッドが用意されている。自分でカスタマイズしたい場合は、例のようにSAMを代入で行ける。

sumofsumは2回ループ回せば出せる【20210526追記】

ARC120のAで出会う。ARCの問題はA問題であっても単純な総当たりでは計算時間をオーバーする。基本的に2重ループのコード自分が書いたら、何か工夫が必要と思うべし。

sum of sum（合計の合計）くらいはサクッと書けるようになりたいと思ったのでメモ。

for(int i=1; i<n; ++i) ai[i] += ai[i-1];
for(int i=1; i<n; ++i) ai[i] += ai[i-1];

二回合計するとsum of sumが求まることは覚えておこう。

[a1, a2, a3]の場合、

１度目のループで[a1, a1+a2, a1+a2+a3]

２度目のループで[a1, a1+(a1+a2), (a1)+(a1+a2)+(a1+a2+a3)]

となる。　つまり、2番目の要素は2番目の要素までの合計値となる。

(i, j)の数えあげは一方を固定【20210522追記】

ABC202のCで出会う。(i, j)を単純をループで数えてしまうと変数が2つなので2重ループとなり、O(N^2)となってしまう。N=10^5のため、N^2=10^10となりTLEとなる。だいたいN=10^8くらいならセーフかもしれない。

仮にiを固定した場合、jを探索する処理をループを使わずにどうやればいいか考える。答えは事前にヒストグラムを作成しておけばよかった。このような考え方はテンプレとして頭に入れておきたい。

普通にC問題は全探索すればよい【20210515追記】

ABC201のCで出会う。要は特定の条件を満たすパスワードは何通りかという問題である。

ここでちょっと数学Aとかを勉強したことがある自分は、数学の知識を使って解こうと頑張ってしまった。（それはそれで大切なことだが）

プログラミングである以上、10000通りくらいなら全探索すればよい。for(int i=0;i<10000;++i)で回して条件に合うものを数え上げればOK。

C問題は複雑に解こうとした時点で何か自分が勘違いていると思った方がよい。

部分集合＝ビット全探索【20210509追記】

ABC200のDで出会う。この問題を解く一部で、数列の部分集合を全探索する必要があり、ビット全探索という方法が利用できる。

例えば、{1, 2, 3}の部分集合は000, 001, 010, 011, 100, 101, 110, 111というように1のビットが立っている数値を数列に用いる。

int [] array = new int[]{1, 2, 3};
        for(int i=0; i<(1<<3); ++i) {
            System.out.println("----");
            System.out.println(Integer.toBinaryString(i));
            List<Integer> target = new ArrayList<>();
            for(int j=0; j<3; ++j) {
                if((i>>j&1)==1) {
                    target.add(array[j]);
                }
            }
            System.out.println(target);
        }

1<<3の部分が、1を左に3ビットシフト→2の3乗→8を意味する。

if((i>>j&1)==1)の部分が、ビットが立っているかを調べる部分である。例えば、010の2桁目が立っているかを調べる場合、001に変換（010>>1）し、001とアンドをとる（001&001）することで1となるかという判定をしている。

mCnを求める【20210508追記】

ABC137のCで出会った。組み合わせを求める実装を記載する必要があり、6C2とかの中学高校でやるような計算である。JavaのStreamでmCnを書くと以下のようにかける。

public static void main(String... args) {
        System.out.println(mCn(6, 2));
    }

    private static long mCn(long m, long n) {
        Long num1 = Stream.iterate(m,i -> i-1).limit(m).reduce((v1, v2) -> v1*v2).get();
        Long num2 = Stream.iterate(n,i -> i-1).limit(n).reduce((v1, v2) -> v1*v2).get();
        Long num3 = Stream.iterate(m-n,i -> i-1).limit(m-n).reduce((v1, v2) -> v1*v2).get();
        return num1/(num2*num3);
    }

リバースする系【20210502追記】

ZONeエナジープログラミングコンテスト “HELLO SPACE”のDで出会った。

このRという文字がある場合、文字列をリバースする必要がある。やり方はいろいろあるがリバース状態かフラグで管理することで対応する。データの持たせた方は、以下の３パターン。

Dequeで、フラグによってaddFirst, addLast
StringBuilderで、フラグによってinsert, append
char[]を2倍のサイズで、左右へのカーソルを2つ用意し配列に格納

が考えられる。自分は慣れているStringBuilderを利用しTLEにもならなかった。StringBuilderのreverseメソッドを利用するとTLEになるので注意。

非単調減少かどうか【20210429追記】

非単調減少にできる数値配列か判定する問題にABC126のCで出会った。

for文で数値配列を先頭から確認し、それまでの最大値を求めておき、2段以上の差があれば非単調減少にすることはできない。

それまでの最大値と現在値を比較することで条件の判定を行うという思考が思いつかなかったので残しておく。

問題を置き換える【20210426追記】

第二回日本最強プログラマー学生選手権のC問題で出会った。

与えられたA<=x, y<=Bというx, yの組み合わせのうち、最大公約数の最大値を求める問題である。愚直にやってしまいx, yの最大公約数の最大値を求める全通りを求めてしまった。

そうではなく、A<=z<=Bというzが最大公約数となるx, yが存在するかという問題に置き換えることで解くことができた。if (b / c – (a – 1) / c >= 2) で求まる。

1文字の入れ替え（replaceではなく、setChatAt）【20210426追記】

ABC199のCで出会った。StringBuilderの中の一文字を変換するという処理が発生したこれで私はTLEで解けなかったが、ほかの人の実装を見てreplaceではなくsetChatAtを利用していることが分かった。

// i文字目に"a"をセットする
// replace版
sb.replace(i, i+1, "a");

// setCharAt版
sb.setCharAt(i, 'a');

setCharAtを利用するとTLEではなくクリアすることができた。

調べてみるとString.replaceは内部でPatternクラスを毎回コンパイルしている。Javaでは有名なPattern.compile重すぎ問題が原因であった。replaceは使わないようにしよう。

データの読み込み

Scannerを使うとコマンドラインからデータを与えられる。

// 一行で読み込んで分割する
Scanner scan = new Scanner(System.in); int i = scan.nextInt(); long l = scan.nextLong(); String[] s = scan.nextLine().split(" ");

// １つ１つとる（型ごとに用意されている）
scan.next();//String型
scan.nextInt();
scan.nextDouble();
scan.nextBigDecimal();
scan.nextFloat();

// 以下のようにfor文でとった入りする。
int[] ai = new int[M];
for(int i=0; i<M;++i)ai[i]=scan.nextInt();

データ型の最大サイズに気を付ける

アルゴリズムは合っていても、データ型を使い間違えると当然だが間違いとなる。結果がTLEやWAとなったりで原因に気付けなかった。intかlongかは注意。ABC193のCでこの手のミスをしてしまった。以下のnをintとしてしていてTLE・WAとなった。

Scanner scan = new Scanner(System.in);
    long n = scan.nextLong();
    Set<Integer> set = new HashSet<>();
    for(int i=2; i<=n; ++i) {
      if(set.contains(i))continue;
      int result = i;
      while(result<=n) {
        result = result*i;
        if(result<=n) {
          set.add(result);
        }
      }
    }
    System.out.println(n-set.size());

DP（動的計画法）を学ぶ

ABC129Cにて出会う。

ai[i]=ai[i+1]+ai[i+2]といった漸化式に落とし込める場合に有効。また頭を切り替える必要があり、階段の最上段を「１」とした場合、階段の0段目はどうかという、ゴールから求めるという発想が必要となる。（自分にはなかった）

少数部分を求める

double型の少数部分だけほしいと思った場合のやりかた。

// 整数部分を引く
double data = 1.0583;
double syousuu = data - (int)data;
System.out.println(syousuu);

二つの数値のうち、大きい方を返す、小さい方を返す。（便利）

double max = Math.max(5, 4);
System.out.println(max);//5
double min = Math.min(5,4);
System.out.println(min);//4

レートの変化

レートの変化について感想を書く。

2021年6月28日追記

前回から一か月たちレートは227→294（+67）上がった。ABCのC問題が安定してきたのもありレートが少しは上がった。

先月立てた以下の目標レートを達成することはできた。

レートを227→260（4週*+10で40くらい上げたい）

解いた問題は以下。C問題を解くの中心に進めた。

A：47→５２（+５問）
B：51→５７（+６問）
C：36→５４（+１８問）
DPまとめコンテストを４問

先月立てたAtcoderProblemsの目標は達成できた。

C問題を36→50にしよう。

翌月の目標

C問題のACを５４→７４にする（２０問解く）
D問題のACを０→１０にする（１０問解く）
レートを２９４→３５０にする（毎週＋15くらいのペース）

D問題を解くのを少しずつ進めていき、ABCDの４完をやってみたい。

2021年5月31日追記

前回から一か月経ったがレートは216→227（+11）しか上がらなかった。ARCにも挑戦してA問題を解けづレートが下がるのが冷えた原因。ただ自分の実力より少し上の問題を解いているからか、ABCのC問題が解けるようになってきた。

また、この１つの記事で記録をつけているので、過去の自分の覚えたことをいやでも見返すのため知識が定着した感がある。

AtCoderProblemsの状況は

A：43→47（+4問）
B：47→51（+4問）
C：24→36（+12問）

とあまり進捗はよくない。AB問題の虚無埋めはやめC問題を解くようにしている。C問題には少しずつ慣れてきており、ABCのC問題は本番で解けるようになってきている。

来月末更新する際の目標

C問題を36→50にしよう。
レートを227→260（4週*+10で40くらい上げたい）

2021年5月9日追記

200代に乗ることができた。ABC200で久々にABCの3完できたが、WAが多くパフォーマンスも377と良くなかった。C問題をWA/TLEなしで解けるようにしていきたい。

AtCoderProblemsの進捗はこんな感じ。AB問題から得られる情報が少なくなってきたので、C問題を進め始めた。

2021年4月：172

ABCのABが解けるようにはなってきた。Cは問題によるという状態。アルゴリズムの武器がないため全探索してTLEになって終了という結果になってしまう。