2の累乗と10進数での桁数
タイトル通り、2の累乗と10進数表記での桁数の対応を確認する。ただそれだけです。
10進数表記の各桁での最小の2の累乗を以下に列挙します。（10進数で20桁まで） 例外として、31,32,63,64乗についても記載しています。32bitや64bitと符号付32bit整数、符号付64bit整数あたりは気になることが多いと思いますので。
| 2n | 10進数での桁数 | 10進数での値 |
|---|---|---|
| 0 | 1 | 1 |
| 4 | 2 | 16 |
| 7 | 3 | 128 |
| 10 | 4 | 1,024 |
| 14 | 5 | 16,384 |
| 17 | 6 | 131,072 |
| 20 | 7 | 1,048,576 |
| 24 | 8 | 16,777,216 |
| 27 | 9 | 134,217,728 |
| 30 | 10 | 1,073,741,824 |
| 31 | 10 | 2,147,483,648 |
| 32 | 10 | 4,294,967,296 |
| 34 | 11 | 17,179,869,184 |
| 37 | 12 | 137,438,953,472 |
| 40 | 13 | 1,099,511,627,776 |
| 44 | 14 | 17,592,186,044,416 |
| 47 | 15 | 140,737,488,355,328 |
| 50 | 16 | 1,125,899,906,842,624 |
| 54 | 17 | 18,014,398,509,481,984 |
| 57 | 18 | 144,115,188,075,855,872 |
| 60 | 19 | 1,152,921,504,606,846,976 |
| 63 | 19 | 9,223,372,036,854,775,808 |
| 64 | 20 | 18,446,744,073,709,551,616 |
こうしてみると、10進数で桁が上がるときの2の指数の1の位は0,4,7の繰り返しなんだな、という謎の気づきがありました。2の3乗が8なので8掛けたら大体一桁上がるけど足りないこともある、ということを考えるとそれはそうだなという感じですが。
【Java】AtCoderのジャッジシステムアップデート（言語アップデート）の影響を確認する
AtCoderのジャッジシステムアップデートが近づいています。
アップデートされたジャッジシステムをテストするためのコンテストも本日21時から開催予定です。
ジャッジシステムのアップデートによって使用できる言語のバージョンもアップデートされます。
ここでは、その言語アップデートのなかでもJavaについて影響ありそうなことをまとめておきます。
使用可能なJavaのバージョン
- 今まで ：OpenJDK1.7.0、OpenJDK1.8.0
- アップデート後：OpenJDK11.0.6、OpenJDK1.8.0
7が使用できなくなり、11が新たに使用可能になります。
以降では、8→11間のアップデート内容の中から、競プロをする上で関係ありそうなものをピックアップします。
競プロに影響ありそうな変更
影響ありそうな変更をまとめた感想を先に述べておきますが、
まぁあんまり影響ないと思います。（まとめ記事を書く意味ないやんという感じですが、影響ないことを確認できた、ということで。）
一応APIの変更をメインに取り上げていますが、実装の変更で恩恵とかがありそうなものもいくつか取り上げています。
※各変更点についてサンプルコードとかも記載しようと思っていますが、間に合っていないので後から追記する予定です。
※標準ライブラリのソースコードなどはOpenJDKに内蔵されているソースコードから引用しています
Collection.toArray(IntFunction)
https://bugs.openjdk.java.net/browse/JDK-8060192
リリースバージョン：11
Collectionインターフェースに以下の新たなtoArrayメソッドが追加されました。
default <T> T toArray(IntFunction<T> generator)
既存のtoArrayメソッドはそのままです。
Object toArray();
<T> T toArray(T a);
■メリット
Collectionを配列に変換する際にほんのちょっとだけいい感じになります。
List<Integer> list = List.of(1, 2, 3);
Integer oldToArray = list.toArray(new Integer[list.size()]);
Integer newToArray = list.toArray(Integer::new);
保持したい要素数が不明な時にひとまずListなどのコレクションで保持しておいて、あとから配列に変換して配列で処理する、みたいにしたいとき使えるかもしれません。
（ただ自作ライブラリとかはたいていint[]とかで作ってあって結局最初から配列でどうにかすることが多いのは私だけでしょうか...）
不変List/Set/Mapのstaticファクトリメソッド
http://openjdk.java.net/jeps/269
リリースバージョン：9
immutableなコレクションインスタンスをスッキリと作成できるようになりました。
以下はJEPに記載されているサンプルです。
【これまでの方法】
Set<String> set1 = new HashSet<>();
set1.add("a");
set1.add("b");
set1.add("c");
set1 = Collections.unmodifiableSet(set);Set<String> set2 = Collections.unmodifiableSet(new HashSet<>(Arrays.asList("a", "b", "c")));
Set<String> set3 = Collections.unmodifiableSet(new HashSet<String>() {{
add("a");
add("b");
add("c");
}});
Set<String> set4 = Collections.unmodifiableSet(Stream.of("a", "b", "c").collect(toSet()));
【新しい方法】
Set<String> set = Set.of("a", "b", "c");
競プロだとコードの寿命が短いかつ一人でのコーディングであることがほとんどなため、インスタンスがimmutableであることの恩恵はあまり感じられない気がします。
ただ、問題によっては数えるほどの要素しか持たないリストやセットを作りたいときもあると思うのでそんな時に手軽に作れるかと思います。（そんなとき、あるかな。。）
streamAPI（takeWhile、dropWhile）
https://bugs.openjdk.java.net/browse/JDK-8071597
リリースバージョン：9
Streamインターフェースに以下の二つのデフォルトメソッドが追加されました。
default Stream<T> takeWhile(Predicate<? super T> predicate)default Stream<T> dropWhile(Predicate<? super T> predicate)
takeWhileの方は、引数に渡したpredicateが最初にfalseになる要素の一つ前までを含むstreamを返し、一方dropWhileは最初にfalseになった要素以降のstreamを返します。
基本的にはソートされた状態でつかうことになると思いますが、それ以外でも使用できる場面はありそうです。
List<Integer> sortedList = List.of(1, 2, 3, 4, 5, 6, 7, 8, 9);
List<Integer> unsortedList = List.of(3, 1, 4, 1, 5, 9, 2);
// before
System.out.println("before - take - sorted");
for (int i = 0; i < sortedList.size(); i++) {
if (sortedList.get(i) < 5) {
System.out.println(sortedList.get(i));
} else {
break;
}
}
System.out.println("before - take - unsorted");
for (int i = 0; i < unsortedList.size(); i++) {
if (unsortedList.get(i) < 5) {
System.out.println(unsortedList.get(i));
} else {
break;
}
}
boolean drop = true;
System.out.println("before - drop - sorted");
for (int i = 0; i < sortedList.size(); i++) {
if (!(sortedList.get(i) < 5)) {
drop = false;
}
if (!drop) {
System.out.println(sortedList.get(i));
}
}
drop = true;
System.out.println("before - drop - unsorted");
for (int i = 0; i < unsortedList.size(); i++) {
if (!(unsortedList.get(i) < 5)) {
drop = false;
}
if (!drop) {
System.out.println(unsortedList.get(i));
}
}// after
System.out.println("after - take - sorted");
sortedList.stream().takeWhile(x -> x < 5).forEach(System.out::println);System.out.println("after - take - unsorted");
unsortedList.stream().takeWhile(x -> x < 5).forEach(System.out::println);System.out.println("after - drop - sorted");
sortedList.stream().dropWhile(x -> x < 5).forEach(System.out::println);System.out.println("after - drop - unsorted");
unsortedList.stream().dropWhile(x -> x < 5).forEach(System.out::println);
Stringの結合処理
http://openjdk.java.net/jeps/280
リリースバージョン：9
これは特にコードの書き方には影響しないのですが、今までStringを+演算子で結合する場合はコンパイル時にStringBuilderでの結合に置き換えられていたのが、今後は実行時に結合処理を呼び出すようになります。
また、デフォルトで呼び出される結合のアルゴリズムとしては、最初に文字列の長さを厳密に調べたうえでその長さの配列を用意し、そこに文字列を詰めていく、という方法になるようです。
これによって+演算子での文字列結合処理は速くなるようですが、繰り返し結合する場合はもちろんStringBuilderで結合することになるので、ほとんど恩恵はなさそうです。
ここら辺の話はちょっと難しかったので以下のページを参考にさせていただきました。
https://vdocuments.mx/jep280-java-9-.html
https://www.techscore.com/blog/2017/12/09/benchmark/
Stringのコンパクト化
http://openjdk.java.net/jeps/254
リリースバージョン：9
これもまた、Stringの内部処理の話です。
これまで文字列をUTF-16の文字配列として保持していたのを、Latin-1で表現できるものはLatin-1で持つようになったということです。これはStringだけでなくStringBuilderなどでも同様です。
競プロでは扱う文字列は英数字であることが多いと思うので、メモリ使用量の削減などが期待できると思います。
一方でLatin-1に収まらない日本語などを使う場合は、一度Latin-1で作成していた配列を破棄してUTF-16で作り直すようで、パフォーマンス低下が起こる可能性もありそうです。
ローカル変数の型推論
http://openjdk.java.net/jeps/286
リリースバージョン：10
普段のコーディングではあまり需要を感じない型推論ですが*1、競プロのようにコード自体も数十行で済み、かつ寿命もACするまでの数分しかないなかで、1秒でもコーディング時間を短くしたい、という状況では使う余地はあると思います。ただ、使える場面は限られるので、宣言をvarで行うかどうか悩むくらいならこれまで通り型を宣言するほうが楽な気もします。IDEとかの補完機能で型を宣言するのもそんなにコスト高くないと思いますし。
【型推論を使える場面】
- イニシャライザを持つローカル変数
- 拡張forループのインデックス
- 従来のforループで宣言されたローカル変数
var map = new HashMap<>();
for (var i = 0; i < 5; i++) {
map.put(i, i * i);
}for (var e : map.entrySet()) {
System.out.println(String.format("key: %d, value: %d", e.getKey(), e.getValue()));
}
ちなみに、上記のサンプルで最初の変数宣言時の右辺でダイヤモンド演算子を省略すると、拡張for文内でgetKey()やgetValue()が使えません。理由はよくわかってないです。。ここら辺のジェネリクスの話とかをよく分かってないから調べなきゃ。
Character.toString()
https://bugs.openjdk.java.net/browse/JDK-8198837
リリースバージョン：11
（文字のコードポイントを指定してStringを生成するメソッドが追加されたのですが、競プロで使う場面なさそうだったので取り消しました。）
String.repeat()
https://bugs.openjdk.java.net/browse/JDK-8198296
リリースバージョン：11
以下のメソッドがStringクラスに追加されました。
public String repeat(int count)
引数に指定した回数その文字列を連結した文字列を返すメソッドです。特定の文字列を一定回数繰り返す処理は競プロで時々求められると思いますが、その時にfor文などをいちいち用いる必要なくシンプルに書けそうです。
List<String> list = List.of("a", "b", "c");
// before
StringBuffer before = new StringBuffer();
for (int i = 0; i < list.size(); i++) {
for (int j = 0; j <= i; j++) {
before.append(list.get(i));
}
}
System.out.println(before.toString());//after
StringBuffer after = new StringBuffer();
for (int i = 0; i < list.size(); i++) {
after.append(list.get(i).repeat(i+1));
}
System.out.println(after.toString());
拡張for文のバイトコード生成改善
https://bugs.openjdk.java.net/browse/JDK-8175883
https://www.oracle.com/technetwork/java/javase/10-relnote-issues-4108729.html#JDK-8175883
記載したものの、どういうことなのかまだきちんと把握できていません。自分が想定している変更内容をJava11で試すと相変わらずOOMEになってしまいます。
このアップデートによって拡張for文がGCをブロックしていた問題が解決された、というのがJBSなどを読んだ私の認識なのですが、実際に動かしてみるとどうもうまくいきません。JBSにも記載されているコードを手元で実行するとOOMEになってしまいます。
private static final int HALF_OF_MEMORY = (int) (Runtime.getRuntime().maxMemory() * 0.5);
public static void main(String args) {
byte data = new byte[HALF_OF_MEMORY];for (byte b : data); // <-- if you comment this line - the application finished successfully
data = null; // this expects to discard reference -> allow to release the memorybyte data2 = new byte[HALF_OF_MEMORY]; // the memory can't be allocated second time, if the "for" loop statement above is used
System.out.println("Success");
}
実験として、①for文 ②拡張for文 ③while文で同じような処理をしてみると、①for文のみOOMEが発生しませんでした。
//①for文
private static final int HALF_OF_MEMORY = (int) (Runtime.getRuntime().maxMemory() * 0.5);
public static void main(String args) {
byte data = new byte[HALF_OF_MEMORY];for (int i = 0; i < 1; i++) {
byte a = data;
System.out.println(a);
break;
}
data = null;
byte data2 = new byte[HALF_OF_MEMORY];System.out.println("Success");
}//=>Success
//②拡張for文
private static final int HALF_OF_MEMORY = (int) (Runtime.getRuntime().maxMemory() * 0.5);
public static void main(String args) {
byte data = new byte[HALF_OF_MEMORY];for (byte b : data) {
byte a = data;
System.out.println(a);
break;
}
data = null;
byte data2 = new byte[HALF_OF_MEMORY];System.out.println("Success");
}//=> Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
//③while文
private static final int HALF_OF_MEMORY = (int) (Runtime.getRuntime().maxMemory() * 0.5);
public static void main(String args) {
byte data = new byte[HALF_OF_MEMORY];while (true) {
byte a = data;
System.out.println(a);
break;
}
data = null;
byte[] data2 = new byte[HALF_OF_MEMORY];System.out.println("Success");
}//=> Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
ここにピックアップしたものの、AtCoderしかやったことないので他のコンテストの事情は分かりませんが、空間計算量が厳しいことはないので、この問題が解決されていようがいまいがさほど影響はないとは思います。強いて言えば、マラソンとかでいろんな状態に対して処理を繰り返すときとかに参照しなくなったはずのインスタンスが残り続けると問題になることも出てくるのかなぁ、とかはありえそうな気もします。
とりあえず、このアップデート内容について知っている方（もしくは上記の検証方法に誤りがあればそれに気づいた方）いらっしゃったら教えてください！
参考
▼各バージョンでの主な変更点まとめ
http://openjdk.java.net/projects/jdk9/
https://openjdk.java.net/projects/jdk/10/
https://openjdk.java.net/projects/jdk/11/
▼その他
https://qiita.com/nowokay/items/1ce24079f4daafc73b4a
https://nowokay.hatenablog.com/entry/20180704/1530712754
https://gist.github.com/ykubota/b37a62de579dc92d02c9483974160c67
https://gist.github.com/ykubota/3afcfdac5b252bd31ae8c14b54b5d32f
最後に
アップデート後に初めてコンテスト参加する際は、きちんと言語を選択してからsubmitするよう気を付けてください！
また、アップデート前のコンテストの問題を開いた後に、アップデート後のコンテストの問題を開くと言語選択がリセットされているので気を付けてください。
*1:もちろん個人的な意見です。コード書く時に型の宣言をサボれるメリットに比べて、それ以降そのコードを読む際の不便のデメリットの方が大きいと感じています。
水色コーダーになるための100問をしばく（1/3）
最近、実生活のほうでかなり実力不足を痛感して悔しい思いをしまして、「この思いをどのように晴らしてくれようか」と煮えくり返っていたところ、以下の様な素晴らしい記事が目につきました。
この中に『初中級者が解くべき過去問精選100問』という章があり、AtCoderで水色コーダーになるのに適切な教育的良問が100問挙げられています。また、100問全部解けたら青色コーダーくらいの実力が付く、との言及もあります。
1年弱水色コーダーで定着してしまっている私ですが、どうにか青になりたいと思っていましたし、一方で基本的な部分が抜け落ちているような気もしていました。
ということで、悔しさをエネルギーにこの100問をしばき倒すことで、精神の解放と青色になるための基礎力を手に入れてやろうと決意しました。
で、いざやってみると100問解くというのは想像以上に大変でした。。。
金曜の夜からやっていますが、ようやく三分の一が終わったところです。（実際は解けずにスキップしているものもあるのでほんとは三分の一も終わっていない。）
当初はこの3連休で全部終わらせるつもりでしたが、主に体力的に厳しそうなので、三連休後も少しずつでもしばいていこうと思っています。
問題を解いた後に1行ずつくらい感想を書き留めているので、それを記録代わりに記載しておきます。（これも当初は100問分一気にブログにするつもりでしたが、3回くらいに分けることにしました。挫折に次ぐ挫折。）
各問題の感想
全探索：全列挙
1 ITP1_7_B - How Many Ways?
さすがに基本的過ぎて飛ばすか悩んだけど、選ばず全部やる！ってことでやってみたらなれない形式のINPUT/OUTPUTでちょっとつまずいた。
幸先の悪いスタート。
2 AtCoder Beginner Contest 106 B - 105
AC済み。
200点にしてはちょっと難しそうな見た目だけど結局全列挙なので。
3 AtCoder Beginner Contest 122 B - ATCoder
AC済み。
苦手な文字列。最後にtmpが暫定解より大きい時に代入するのを忘れて１WA。
4 パ研杯2019 C - カラオケ
全探索、全列挙の問題として見ていなかったらDPとか余計なこと考えていたかもしれない。
落ち着いて制約を見てN*M^2の3重ループで行けることをすぐに見抜く。
全探索：工夫して通り数を減らす全列挙
5 AtCoder Beginner Contest 095 C - Half and Half
AC済み。
以前ACした時とかなりコードが一致していた。成長していない。。？
6 三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN
AC済み。
以前ACした時に比べてStringクラスのindexOf(str, fromIndex)メソッドを利用するなどしてスッキリかけた。成長している。
★7 JOI 2007 本選 3 - 最古の遺跡
TLEするのでスキップ
8 Square869120Contest #6 B - AtCoder Markets
何とかAC。難しい。勉強になる。
N個の数a1,a2,…aNについて|x-a1|+|x-a1|+...+|x-aN|が最小となるxは「a1,a2,...,aNの中央値」
★9 JOI 2008 予選 4 - 星座探し
見た目的に無理なのでスキップ
全探索：ビット全探索
10 ALDS_5_A - 総当たり
bit全探索だといわれているのに最初なぜかDPやろうとしてた。
11 AtCoder Beginner Contest 128 C - Switches
AC済み。
以前より少しだけスッキリかけていた。
12 AtCoder Beginner Contest 002 D - 派閥
最大クリーク問題というNP困難な問題らしい。
13 JOI 2008 予選 5 - おせんべい
実行制限時間10secってどのくらいの計算量まで許容されるかわかんねーと思いながらひとまず提出したら417msで全然余裕だった。
bit全探索だけでなく、論理和と排他的論理和も普通に使えるようになってて、競プロはじめてbit演算耐性がついたなと実感。
14 Square869120Contest #4 B - Buildings are Colorful!
オーバーフローで１WA。入力で10^9とかあったら迷わずlongを使いなさい。
全探索：順列全探索
★15 AtCoder Beginner Contest 145 C - Average Length
未参加ABCで今後バチャをやる可能性があるのでスキップ
16 AtCoder Beginner Contest 150 C - Count Order
AC済み。
結構最近やったやつなのにどうするか迷った。順列全探索苦手っぽい。
17 ALDS_13_A - 8 クイーン問題
見た瞬間無理と思ったけど愚直にDFSで全探索して通した。これも順列全探索と扱うのか？
二分探索
18 ALDS_4_B - 二分探索
シンプルすぎて逆にOKとNGの判定をどうすべきか悩んだ。
★19 JOI 2009 本選 2 - ピザ
MLEが取れずスキップ。
20 AtCoder Beginner Contest 077 C - Snuke Festival
AC済み(2回)
二分探索に持っていくことができれば、あとはただの二分探索。
リンクミスがあったっぽくARC037C億マス計算を↑の先にAC。（この問題はAC済み。最近これと似たような二分探索の中で二分探索するような問題がABC出会った気がする）
21 AtCoder Beginner Contest 023 D - 射撃王
AC済み。
問題文が「最大値の最小化」という二分探索典型パターンを醸し出そうとしていて変な問題文になっている気がする。
intとlongで行き来するのが苦手。というかそもそもやらないようにすべきな気がするがどうした良いものか。
22 AtCoder Regular Contest 050 B - ムーアの法則
解説AC。
できなくて色々ググった結果、三分探索を習得した。
★23 JOI 2008 本選 5 - ダーツ
分からなすぎるのでスキップ
深さ優先探索
24 ALDS_11_B - 深さ優先探索
純度100%のDFS
25 AOJ 1160 - 島はいくつある？
何かもう少しいい感じにできそうな気がするけど、とりあえず愚直に。
26 AtCoder Beginner Contest 138 D - Ki
AC済み
imos法をDFSでやる感じ。
27 JOI 2009 予選 4 - 薄氷渡り
DFSやるだけ。
幅優先探索
28 ALDS_11_C - 幅優先探索
普段ほとんど幅優先探索やることないので慣れてなくて手間取る。
29 AtCoder Beginner Contest 007 C - 幅優先探索
普段ほとんど幅優先探索やることないので慣れてなくて手間取る。
問題名で解法をお知らせしていて、かなりビギナー向けだと感じた。
30 JOI 2011 予選 5 - チーズ
幅優先探索を複数回。
31 JOI 2012 予選 5 - イルミネーション
BFSで外側から行けるところを判定した後、外から行けるところと行けないところの接点の数を数える。
四角が並んだ普通のグリッドでなく正六角形なため、各ブロックの隣接を列挙するのが少し悩む。
32 AOJ 1166 - 迷図と命ず
ブロック間に壁があるので、行けるいけないの判定に少し工夫が必要。各ブロックから行ける方向をbitで管理した。
33 AtCoder Beginner Contest 088 D - Grid Repainting
BFS自体はシンプルで、最短経路を見つければよいことに気づければ勝ち。
BFSに全然慣れていなかったけど、これで結構慣れた気がする。（というかどれも実装がかなり似ていて、ノイローゼになりそうだった。。）
残り、67問。最後までやり通せるかなこれ。
final修飾子の仕様確認
今まで何となく定数を宣言するときにstatic finalとして付けるくらいで、finalが実際にどのようなものなのかをしっかり理解できていなかったので、仕様を確認してみます。
仕様の確認は主にJava SE 11の言語仕様を参照しています。
finalの種類
finalはクラス、メソッド、変数の3つを修飾することができ、ざっくりと以下のような効果になります。
・finalクラス：他のクラスから継承されなくなる。
・finalメソッド：オーバーライドされなくなる。
・final変数：一度しか値を代入されなくなる。
finalクラスが継承できないことの確認
以下のようなfinalクラスとそれを継承しようとしているクラスを作ります。
final class SampleFinal {
public void message() {
System.out.println("This is final class.");
}
}
class SampleFinalExtends extends SampleFinal{
@Override
public void message() {
System.out.println("This extends final class.");
}
}
そして以下のようにfinalクラスを継承したクラスをnewしてみます。
class Main {
public static void main(String args) {
SampleFinalExtends sfe = new SampleFinalExtends();
sfe.message();
}
}
すると以下のようなエラーになります。
Exception in thread "main" java.lang.Error: Unresolved compilation problems:
The type SampleFinalExtends cannot subclass the final class SampleFinal
The method message() of type SampleFinalExtends must override or implement a supertype method
一方でfinalクラスでない場合はうまくいきます。
class SampleNotFinal {
public void message() {
System.out.println("This is not final class.");
}
}
class SampleNotFinalExtends extends SampleNotFinal {
@Override
public void message() {
System.out.println("This extends not final class.");
}
}
class Main {
public static void main(String args) {
SampleNotFinalExtends sfe = new SampleNotFinalExtends();
sfe.message();
}
}
This extends not final class.
finalメソッドのオーバライド不可を確認
class Main {
public static void main(String args) {
Parent p = new Parent();
p.print1();
p.print2();
Parent c = new Child();
c.print1();
c.print2();
}
}
class Parent {
public void print1() {
System.out.println("Parent print1");
}
public final void print2() {
System.out.println("Parent print2");
}
}
class Child extends Parent {
public void print1() {
System.out.println("Child print1");
}
@Override
public final void print2() {
System.out.println("Child print2");
}
}
エラー: メイン・クラスsandbox.Mainを初期化できません
原因: java.lang.VerifyError: class sandbox.Child overrides final method sandbox.Parent.print2()V
final変数の中身が参照型の場合は参照先が不変になる（参照先の値は変わりうる）
変数がプリミティブ型の場合は、最初に代入された値が変わらなくなります。
一方で参照型の場合は、変数に代入された参照先のオブジェクト自体は変わらなくなりますが、そのオブジェクトの中身（フィールド）は変更することが可能です。
そのため、ラムダ式や内部クラスで外部の変数を参照するにはその変数が実質的にfinalであることが求められますが、その変数が参照型でフィールドにリストなどを持っていれば、そのリストにラムダ式内でオブジェクトをaddしたりすることは可能になっています。
final変数に一度代入すると代入できなくなることの確認
class Main {
public static void main(String args) {
}
}
Exception in thread "main" java.lang.Error: Unresolved compilation problem:The final local variable list cannot be assigned. It must be blank and not using a compound assignment
final変数でもその中身はfinalでない（変更可能）であることの確認
class Main {
public static void main(String args) {
list.add("str1");
list.add("str2");
list.add("str3");
System.out.println(list);
list.remove(1);
System.out.println(list);
final Obj obj = new Obj();
System.out.println(obj);
obj.id = 2;
obj.name = "second";
System.out.println(obj);
}
}
class Obj {
int id;
String name;
public Obj() {
id = 1;
name = "first";
}
public String toString() {
return "id:" + id + ", name:" + name;
}
}
[str1, str2, str3]
[str1, str3]
id:1, name:first
id:2, name:second
暗黙的なfinal
以下の3つの場合は暗黙的にfinalとして宣言されます。
・インターフェースのフィールド
・try-with-resources文のresource
・multi-catch句のパラメータ
インターフェースのフィールドが暗黙的にfinalであることの確認
class Main {
public static void main(String args) {
Field fields = SampleIF.class.getDeclaredFields();
for (Field f : fields) {
String s = Modifier.isFinal(f.getModifiers()) ? "final" : "not final";
System.out.printf("%s is %s\n", f.getName(), s);
}
}
}
interface SampleIF{
int id = 0;
String name = "zero";
}
id is final
name is final
try-with-resources文のresourceが暗黙的にfinalであることの確認
class Main {
public static void main(String args) {
try (BufferedReader br = new BufferedReader(new FileReader(args[0]))) {
System.out.println(br.readLine());
br = new BufferedReader(new FileReader(args[0]));
} catch (IOException e) {
e.printStackTrace();
}
}
}
Exception in thread "main" java.lang.Error: Unresolved compilation problem:
The resource br of a try-with-resources statement cannot be assigned
multi-catch句のパラメータが暗黙的にfinalであることの確認
class Main {
public static void main(String args) {
try{
multiThrow(true);
} catch (IOException | InterruptedException e) {
e = null;
}
}
private static void multiThrow(boolean bool) throws IOException, InterruptedException {
if(bool) throw new IOException();
else throw new InterruptedException();
}
}
Exception in thread "main" java.lang.Error: Unresolved compilation problem:
The parameter e of a multi-catch block cannot be assigned
試しに別々にcatchしてみます。
class Main {
public static void main(String args) {
try{
multiThrow(true);
} catch (IOException e) {
e = null;
System.out.println("catch IOException");
} catch (InterruptedException e) {
e = null;
System.out.println("catch InterruptedException");
}
}
private static void multiThrow(boolean bool) throws IOException, InterruptedException {
if(bool) throw new IOException();
else throw new InterruptedException();
}
}
catch IOException
実質的なfinal（effectively final）
初期化子のある変数で以下の条件をすべて満たす場合実質的なfinalとみなされます。
・final修飾子がついていない
・代入式の左側に現れない
・インクリメント/デクリメント演算子のオペランドにならない
初期化子のない変数で以下の条件をすべて満たす場合実質的なfinalとみなされます。
・final修飾子がついていない
・確実に未代入であり確実に代入されていないときのみ代入式の左側に現れている*1
・インクリメント/デクリメント演算子のオペランドにならない
メソッドやコンストラクタ、ラムダ、例外のパラメータで、初期化子ありで宣言された変数のように扱われている場合、実質的なfinalとみなされます。*2
finalについて詳細に理解するには、代入について理解しておく必要があるようです。（果てしない。。）
Integer型インスタンスの一部はキャッシュされる。
職場の人がIntegerインスタンス同士を "==" で比較しているコードを目撃して、指摘しようと思いよくよく見てみると、想像に反した挙動になっていたのでちょっと確認してみました。
確認した対象はJava8です。
Integer型インスタンスの同値判定
まずはいくつかのインスタンス生成方法で実験してみます。
new Integer() == new Integer()
Integer a = new Integer(1); Integer b = new Integer(1); System.out.println(a == b);
結果は false になります。
aとbは別のインスタンスなので同値判定はfalseです。（これは想定通り）
Integer.valueOf() == Integer.valueOf()
Integer a = Integer.valueOf(1); Integer b = Integer.valueOf(1); System.out.println(a == b);
結果は true になります。
valueOfは一度生成したインスタンスを使いまわすっぽい？（これはそもそも想定したことがなかった）
オートボクシング == オートボクシング
Integer a = 1; Integer b = 1; System.out.println(a == b);
結果は true になります。
valueOfと同じかな？
Integer.valueOf() == new Integer()
Integer a = Integer.valueOf(1); Integer b = new Integer(1); System.out.println(a == b);
結果は false になります。
newしたらすでに等価なインスタンスが存在しても新たにインスタンスを生成してくれるのはStringと同じみたいです。
Integer.valueOf() == オートボクシング
Integer a = Integer.valueOf(1); Integer b = 1; System.out.println(a == b);
結果は true になります。
やはりvalueOfとオートボクシングは使いまわすみたいですね。
ここまでの実験でInteger.valueOf()とオートボクシングは等価なインスタンスが既に存在すればそれを使いまわす、ということが言えそうです。
が、少し調べてみると、そうでもない場合があるようです。
Integer.valueOf() == Integer.valueOf() ②
Integer a = Integer.valueOf(128); Integer b = Integer.valueOf(128); System.out.println(a == b);
結果は false になります。
オートボクシングでも同様に false になります。
valueOf()メソッドは一部のインスタンスをキャッシュする
Java APIのドキュメントを確認してみます。
このメソッドは、-128から127の範囲(両端含む)の値を常にキャッシュしますが、この範囲に含まれないその他の値をキャッシュすることもあります。
キャッシュするのは-128～127の範囲に限定されているようです。
そのためInteger.valueOf(1)で代入したインスタンス同士は同値となり、Integer.valueOf(128)同士では同値とはならなかったということです。
JDKに付属のソースコードも確認してみます。
public static Integer valueOf(int i) { if (i >= IntegerCache.low && i <= IntegerCache.high) return IntegerCache.cache[i + (-IntegerCache.low)]; return new Integer(i); }
確かにキャッシュから返したり、newしたインスタンスを返したりしています。
おまけ IntegerCache
IntegerCacheは、Integerクラス内に定義されているstaticなインナークラスです。
で、このIntegerCacheのJavadocを見てみると、キャッシュする最大値を（大きくする方向にだけ）変更できるようです。
キャッシュする最大値を変更するには以下のようにVMオプションを設定します。
-XX:AutoBoxCacheMax=365
このオプションを設定して以下を実行してみます。
Integer a = 365; Integer b = 365; System.out.println(a == b);
結果は true となります。（366でやるとちゃんとfalseになりました）
AtCorderで水色になりました！
先日開催されたAGC033にて、念願だった水色にようやくなれたので*1、皆さんに倣って振り返り記事を書きたいと思います。*2
ちなみに、AtCorderで水色はどんなもんかというと↓みたいな感じです。（悪用）
AtCoderで水色って、思ってたよりすごいのか？水色以上なんてツイッターにはぞろぞろいるからそんな感じしない。はやく水色なりたい。
— tobiuo (@tobiuo1990) April 10, 2019
『水色以上の方はGoogleに入れる可能性が充分にあるといっていい』https://t.co/S79pxomrkJ
期間
初ACは2018/11/21なので、165日（5.5か月）で水色になれました。
当初思っていたよりも時間かかりました。というのも、1200くらいのパフォーマンスは割とすぐ出たので、すぐにレートも1200は超えると思っていたからです。実際にはそんなに甘くなく、目標レート相応のパフォーマンスを継続的に出す必要があることを思い知りました。
やったこと
- 1日1AC
- 時間があるときは蟻本読んで新たなアルゴリズムやデータ構造を学習
- ライブラリ作成
- 重点的なテーマ対策
1日1AC
蟻本を購入した後（競プロ初めて2~3か月目くらい）、新たな知識の習得やライブラリの作成などに取り組んでしまい、問題を解くことをおろそかにしていた時期がありました。そうすると明らかにレートが停滞してきて、初めてレートが減少したりABCで2完しかできないことが続いたりしました。（たまたま自分の能力的にここで一つ壁があっただけかもしれません。）
2回連続でABCのCがコンテスト中ACできなかったので、蟻本とかで新たなデータ構造とかアルゴリズムを習得するのを一時中断して、ABC040からC問題を一通り解き始めた。
— tobiuo (@tobiuo1990) February 28, 2019
とりあえずABC040,041は5分くらいでACできた。この差は何？
今と昔の難易度の差？
本番に弱い？
前者な気がしてる
そこでまずはABCのCを解けないと水色は厳しいよなと思いなおし、Cをとにかく埋める、できるだけ毎日ACするようにしたところ、ABCで初めて全完できました。
ABC120
— tobiuo (@tobiuo1990) March 3, 2019
全完(初！)
rank:630
perf:1406
通算
rank:5727
rate:986(+76)
全完してもパフォ1600出るわけではないのか。
今回パフォ1600だすためにな順位413位以上、1時間以内で全完が必要だったみたい。
次も全完できるようがんばろ。
また、以下のような言葉をふと目にすることがありました。
読む力、それは新たな学力を獲得していくための前提条件であり、その意味で「学力の上限を規定するもの」と言うことができます。
また書く力は、獲得した学力を定着させる主要な手段であり、「学力の下限を規定するもの」と言えます。*3
上記の引用は競プロにも当てはまると思っていて、蟻本を読んで新たな知識を習得したりするのは、上限を上げている、と言えます。一方で、問題を解くというのは、すでに習得した知識を実際に使えるようにしている（必要な時に適切に使える確度を高めている）ので、下限を固めている、と言えます。上限ばかりを上げても下限が低いままだと安定してパフォーマンスを出せず、レートも順調に上がっていかないと思うので、継続的にACしていくことは最初は重要だと思います。
いまでは必ず毎日1ACはするようにしています。旅行に行くときなども、事前にいくつかストックして毎日提出する、というようなこともやっていて、これは完全に目的が手段化しています。が行けるところまでstreakを伸ばすというのも現在の競プロの楽しみの一つになっています。
蟻本読んで新たなアルゴリズムやデータ構造を学習・ライブラリ作成
今のところ、ようやく初級編を読み終わったところです。
進め方としては
蟻本を読む（1節）⇒ ライブラリ化するようなものであればライブラリ作成 ⇒ 関連問題をいくつか解く
を繰り返しながら進めました。関連問題についてはこちらを参考にしています。（AtCorder入門時からずっとお世話になってます。ありがとうございます。）
作成済みライブラリは以下の通りです。
- グラフ生成（重みあり・なし。隣接行列。）
- グラフの最短距離を求めるアルゴリズム（ベルマンフォード、ダイクストラ、ワーシャルフロイド）
- 最小全域木（クラスカル）
- Union-Find
- GCD/LCM（ユークリッドの互除法）
- 順列組み合わせ（フェルマーの小定理）
結構作成したつもりだったけど、列挙してみると少ないですね。これからもっと充実させていきたいです。
重点的なテーマ対策
冬季休業とかで時間が多めにあるときに少しやりました。
とは言ってもやったのは、DPとグラフをちょっとまとめてやったくらいです。
競プロやってよかったこと
- コンテストに参加すると楽しい
- 新たなアルゴリズムやデータ構造を習得するのが楽しい
- その他色々
コンテストに参加すると楽しい
さまざまな理由で競プロをしている人がいると思いますが、自分の場合はこれです。コンテストに参加して自分が解けるか解けないか微妙なラインの問題をなんとかして解けたときは嬉しいし、解けなかったときは悔しいです。
あと、コンテスト後に競プロerがワラワラと悲喜交々つぶやいていくのを眺めたり自分もつぶやいたりするのも、楽しみの一つです。
新たなアルゴリズムやデータ構造を習得するのが楽しい
まだ初歩的なものしか習得出来てないですが、新たに習得するたびにレベルアップしたような感じで、楽しいです。また、普段使用しているプログラミング言語の標準で用意されている関数（ソートとか）についてもただ使うだけでなくて、どのようなアルゴリズムで実装されているのか気になって調べたりして、言語自体にも少し詳しくなれました。
これから
次はもちろん青を目指します。自分が努力しても青が精いっぱいかなという感覚ですが、まずは青になってみないとそこらへんは分からないので、何はともあれ青になってみたいと思います。なんとか2019年中に青になれるように頑張りたいです。
そのために、蟻本の中級までは習得したいです。あと400～600くらいまでは埋めたいです。（レート1600は、配点500を半分くらい解ければいいらしいので、600くらいまで埋められれば青になれるはず？）streakも継続して伸ばしていきたいです。
楽しみながら、コツコツと精進していきます。
CODEVS2019の予選にJava製の自前AIを提出する。
ついにCODEVS 2019の予選が開始されました。
そして前回の記事からの懸念事項であるプログラムの提出に無事成功したので、うまくいった一例を記載しておきます。（書くほどのことでもないですが、公式な説明が不足気味な気もするので。）
私がやった方法をざっくり言うと
「Javaで書いて、jarに固めて、実行用のシェルスクリプトを書いて、zipして出した」
です。
「Javaで書いて、jarに固めて」
ここの方法は特に問題ないかと思います。
よければ前回の記事を参照ください。
「実行用のシェルスクリプトを書いて」
以下のようなスクリプトを書きました。
#!/bin/sh
SCRIPT_DIR=`dirname $0`
java -jar $SCRIPT_DIR/submit.jar
『カレントディレクトリに注意して下さい』と記載があったので、dirname とかやってます。
改行コードは \r\n → \n に変換しました。
「zipして出した」
zipしたフォルダの中身はjarファイル一つと先ほど書いたシェルスクリプト一つだけです。
提出物の準備ができたらあとは、クライアントの提出タブに以下の内容を入力します。
ユーザーID：公式サイトで登録したユーザーID
トークン：公式サイトにログイン直後の画面に記載されています。
プログラミング言語：zip
あとは「ファイルを選ぶ」から先ほど準備したzipファイルを選択し、「submit」ボタンを押して5秒ほど待つと成功した旨が表示されます。
