ABC149 E - Handshake:「~は累積和を用いることで O(1) で求まるので」ではわからない人のための累積和解説
atcoderの解説は往々にしてストロングスタイルなところが好きです。
atcoder.jp 本番さっぱりとけなかったので、後日解説を読みました。
まず、増える幸福度が、ある定数 X 以上になる握手の方法が何通りあるか、を求めることを考えます。
左手で握手する人を先に決めたとき、右手で握手できる人が何人いるかは累積和を用いることでO(1)で求まるのでトータルで O(N)で計算できます。
ここが全然わからなくて、解説の簡潔さを恨みながらようやく理解したので備忘録に残しておきます。
まず、Nの制約が105であるので、一つ一つの握手の幸福度を考えていると間に合わないことがわかります。
ここで、解説にある通り発想を変えて、増える幸福度が定数X以上になる握手の方法が何通りあるかを考えます。しかし、一つ一つの握手の幸福度をそれぞれ見ていくと間に合わないので、「累積和」と呼ばれる手法を使います。
この記事は簡単な累積和の解説記事ですが、僕はこの問題にどのように累積和を適用すればいいのかわからなくてそのまま年を越しました。
ところで、「いもす法」というアルゴリズムがあります。いもす法とは、累積和のアルゴリズムを多次元、多次数に拡張したものです。
こちらの原典の最初の例を読むとなんとなくこの問題への適用方法がわかってきました。例えば、
- 一回の握手の幸福度の取りうる値域(<= 2 * 105)分のサイズの配列を用意。
- 配列を0で初期化。
- それぞれの握手の幸福度をvとしたとき、array[v]を+1。
- その配列に対して後ろから累積和を計算。
とすることで、ある値Xに対して、「array[X] = X以上になる握手の方法の数」となるような配列arrayが得られます(考え方はリンク先の現在入店している人数を数える場合と同じ)。
この配列を用いれば、「array[X] = X以上になる握手の方法の数」がO(1)で求まります。
しかしこのような配列を作成するのに全通りの握手の幸福度を調べているので、配列の構築に計算量がO(N2)かかってしまいます。
そこで、上記のアルゴリズムを片手の分だけで行い、累積和を計算します。
このようにすると、例えば左手が握るゲストの手を固定し、左手側のゲストの値がkのとき、右手側の値がX-k以上になるゲストの数を累積和を用いることで O(1) で求めることができます。 したがって、固定したゲストを全通り試すことで、トータルでO(n)でX以上になる握手の方法の数が求まります。
あとは、このXの値を二分探索で求めます。X以上になる握手の方法の数、がちょうどMになるとき、そのM通りの握手の幸福度を合計したものが答えです。
X以上になる握手の方法の数がちょうどMにならない場合もあるので、その場合は多少考えることが増えますが、その部分は以下の記事がとてもわかりやすかったです。
ABC 128 C - Switches: bit演算を用いて解く
問題文 on と off の状態を持つ N 個の スイッチと、 M 個の電球があります。スイッチには 1 から N の、電球には 1 から M の番号がついています。
電球 i は k i 個のスイッチに繋がっており、スイッチ si1 , s i 2 , . . . , s i k i のうち on になっているスイッチの個数を 2 で割った余りが p i に等しい時に点灯します。
全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは何通りあるでしょうか。
自力での実装では、Sを問題文と同じように二次元の配列でもち、すべてのスイッチのパターンに対して、条件を満たすかどうかを判定していた。
しかし、この問題は『on/offの状態を持つ複数個のスイッチ』に対して『Sで表される参照すべきスイッチ』を選択し、それらの中で点灯しているものの個数が偶数か奇数を判定するというもので、
『『on/offの状態を持つ複数個のスイッチ』に対して『Sで表される参照すべきスイッチ』を選択する』の部分をビット演算を用いて行うことができる。
for (int i = 0; i < m; i++) { int k = nei(); for (int j = 0; j < k; j++) { s[i] |= 1 << (nei() - 1); } }
上記のように、Sで表される参照スイッチの条件を、00101100のように仮に表されるビット列でもつとする。これは例えば3番目と4番目のスイッチを参照する条件を表す時
とすることで 11000(=24)が得られる。
これに、例えばスイッチが5個なら、int max = 1 << 5 (= 100000 = 32)として、for文で回して、論理積を撮って、bitCountをとってやれば良い。
細かいテクニックとして、2で割ったあまりは & 1をすることで取れる。
for (int i = 0; i < max; i++) { for (int j = 0; j < m; j++) { if ((Integer.bitCount(bs[j] & i) & 1) != ps[j]) break; } }
最速回答を見て勉強すると学ぶことが多いです。回答者の方には感謝しか無い。
Java8で追加されたstreamを用いてint型の配列をIntegerのArrayListに変換する
結論
Integer[] arr_integer = Arrays.stream(a).boxed().toArray(Integer[]::new); List<Integer> list_integer = Arrays.asList(arr_integer); ArrayDeque<Integer> deq = new ArrayDeque<>(list_integer);
ABC 141 E - Who Says a Pun? : Z-Algorithm を Javaで実装する
解説の中にあるZ-Algorithmを勉強したので記録。
こちらのリンクが大変ためになった。 www.geeksforgeeks.org
Z-Algorithmとは
Z-Algorithmとは、『Z-Array』を線形時間で構築するアルゴリズムであり、ある文字列に対して、あるパターンが出現するかどうかを判定する際などに用いられる。
Z-Arrayとは「文字列str[0..n-1]が与えられた時、Z[i]は文字列str[0..n-1]とstr[i..n-1]の最長共通接頭辞数であるような配列」である。
Example: Index 0 1 2 3 4 5 6 7 8 9 10 11 Text a a b c a a b x a a a z Z Array X 1 0 0 3 1 0 0 2 2 1 0
例えばここでパターンを "hoge" とおいて、テキストを "fugahogepiyo" としたとき、"hoge$fugahogepiyo" *1に対してZ-Algorithmを適用しZ-arrayの中にパターンの文字列長の値が入っているかを確かめることで、テキスト中にパターン "hoge" が登場するかどうかを判定することができる。
O(n)で解くために、計算途中での共通接頭辞をメモしているのがキモ。 共通接頭辞の始まるindexをL、最後の文字のindexをRとしたとき、str[0..R-L]とstr[L..R]は同じ文字列であることを利用して、計算量を削減している。 つまり、i<Rである時、ナイーブに共通接頭辞を見るのではなくて、すでに計算されたZ[i - L]を利用する。
解答
import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws Exception { final Scanner sc = new Scanner(System.in); int N; N = sc.nextInt(); String S; S = sc.next(); solve(N, S); } static void solve(int N, String S) { int ans = 0; for (int i = 0; i < N; i++) { int[] z = z_algorithm(S.substring(i)); for (int j = i; j < N; j++) { ans = Math.max(ans, Math.min(j - i, z[j - i])); } } System.out.println(ans); } static int[] search(String pattern, String text) { return z_algorithm(pattern + "$" + text); } static int[] z_algorithm(String S) { int l = 0; int r = 0; int[] Z = new int[S.length()]; for (int i = 1; i < S.length(); i++) { if (r < i) { l = r = i; while (r < S.length() && S.charAt(r) == S.charAt(r - l)) { r++; } Z[i] = r - i; r--; } else { int k = i - l; if (i + Z[k] - 1 < r) { Z[i] = Z[k]; } else { l = i; while (r < S.length() && S.charAt(r) == S.charAt(r - l)) { r++; } Z[i] = r - i; r--; } } } Z[0] = S.length(); return Z; }
*1:$はパターン内にもテキスト内にも出現しないことが保証されているとする。
java競プロ環境をvs codeに移行した
表題の通り。intelliJを使っていたけど、重いのと補完が微妙にうまく行かなかったのでvs codeに移行した。
触ってみた感じ、軽量だしvimプラグインもあるしDebug機能がintellJに匹敵するほど強力で競プロには十分すぎるくらい。
一点、intellJと同じように、shift -> shift で全ファイルから名前を指定して開く機能を使いたかったのだが、現状のvs codeではshift二連打は検出していないようだ。
https://github.com/Microsoft/vscode/issues/5280
Feel bad for knocking off JetBrains, but they double-shift is really quite a killer feature.
java使用時に`atcoder-tools test`で発生するエラーに対処した
atcoder-toolsというツールをありがたく使わさせていただいている。
各問のテストケースに対して、テストを自動で走らせてくれる機能があり、以下のコマンドで実行できる。
atcoder-tools test
しかし、java使用時に上記コマンドがうまく行かなかった。java Mainが実行されることを期待しているが、./Main.classが実行されるようだ。
OSError: [Errno 88] Malformed Mach-o file: './Main.class'
やったこと
力技でどうにかした。
run.sh の用意
#!/bin/sh chmod 777 Main.class java Main
atcoder-tools gen時にrun.shを作成
[codestyle] lang='java' [postprocess] exec_on_each_problem_dir='touch run.sh;chmod 777 run.sh;echo "#!/bin/sh" >> run.sh;echo "chmod 777 Main.class" >> run.sh;echo "java Main" >> run.sh'
Test時にrun.shを実行
javac main.java; atcoder-tools test -e "./run.sh"
