Open20
競技プログラミングめも
Re_F競技プログラミングで使える標準入力の処理の仕方の例
標準入力の受け付け方を定期的に忘れてしまうので、メモとしての残した。
参考とする問題
入力例
N Q
L_1 a_1,1… a_1,L1
⋮
L_N a_N,1… a_N,L_N
s_1 t _1
⋮
s_Q t_Q
Java の場合
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int Q = sc.nextInt();
int[][] a = new int[N][]; // Out of Memoryを防ぐため二項目は宣言しない
for (int i = 0; i < N; i++) {
int L = sc.nextInt();
a[i] = new int[L]; // ここで二項目を宣言する
for (int j = 0; j < L; j++){
a[i][j] = sc.nextInt();
}
}
for (int i = 0; i < Q; i++) {
int s = sc.nextInt();
int t = sc.nextInt();
System.out.println(a[s-1][t-1]);
}
}
}
JavaScript の場合
より短く書けるが、Javaのような標準入力を1行ごとに受け付ける方式を再現するために、 args.shift() で行列を抽出する形にしてみた。
process.stdin.resume();
process.stdin.setEncoding('utf8');
function main(input) {
// 入力を改行区切りのstringの配列で受け取ったのち、さらに各行をint配列に変換する
const args = input.trim().split("\n").map(e => e.split(' ').map(n => parseInt(n, 10)));
const [N, Q] = args.shift(); // shift で配列を切り出しつつ宣言する
let ln = [];
for(let i = 0; i < N; i++) {
ln[i] = args.shift();
}
for (let i = 0; i < Q; i++) {
const [s, t] = args.shift();
console.log(ln[s-1][t-1]);
}
}
main(require("fs").readFileSync("/dev/stdin", "utf8"));
Java の仕様
剰余計算
- Java は負の数を割った際の余りは負の数で出てくる。
- そのため、正しく余りを出す際には特殊な処理をする必要がある。
int x = -34;
int m = 5;
int r_1 = x % m; // -4 （数学的に誤り）
int r_2 = (x % m + m) % m; // +1 （数学的に正しい）
Java での順列並び替え（NextPermutation）
Java には C++ には存在する「特定の引数に対して順列を出力する関数」が存在しないため、自前で実装する必要がある。以下の記事に参考実装があったため転記する。
NextPermutation
NextPurmutation 順列組み合わせ
static String nextPermutation (String s) {
ArrayList<Character> list = new ArrayList<>();
for (int i=0; i<s.length(); i++) list.add(s.charAt(i));
int pivotPos = -1;
char pivot = 0;
for (int i=list.size()-2; i>=0; i--) {
if (list.get(i) < list.get(i+1)) {
pivotPos = i;
pivot = list.get(i);
break;
}
}
if (pivotPos==-1 && pivot==0) return "Final";
int L = pivotPos+1, R = list.size()-1;
int minPos = -1;
char min = Character.MAX_VALUE;
for (int i=R; i>=L; i--) {
if (pivot < list.get(i)) {
if (list.get(i) < min) {
min = list.get(i);
minPos = i;
}
}
}
Collections.swap(list, pivotPos, minPos);
Collections.sort(list.subList(L, R+1));
StringBuilder sb = new StringBuilder();
for (int i=0; i<list.size(); i++) sb.append(list.get(i));
return sb.toString();
}
使用例
String s = "ABC";
while (true) {
System.out.println(s);
s = nextPermutation(s);
if (s.equals("Final")) break;
}
// → "ABC", "ACB", "BAC", "BCA",... 辞書順の表記
Java 標準入力
基本形
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] A = new int[N];
for (int i = 0; i < N; i++) {
A[i] = sc.nextInt();
}
System.out.println(N);
}
}
最大公約数：ユークリッドの互除法
二分探索も使っているあわせ技の問題だった......。
public static long GCD(long A, long B) {
// swap する
if (A < B) {
long tmp = A;
A = B;
B = tmp;
}
// 再帰的に算出する
if (B == 0) {
return A;
} else {
return GCD(B, A % B);
}
}
最小公倍数
// 最大公約数を利用することで求まる
long gcd = GCD(A, B);
long lcm = (A*B)/gcd;
StingBuilder を使いこなそう
ここ最近、文字列結合による処理の遅さによりTLEが出ている......。
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int H = sc.nextInt();
int W = sc.nextInt();
String[] S = new String[H];
String[] T = new String[H];
for (int i = 0; i < H; i++) {
S[i] = sc.next();
}
for (int i = 0; i < H; i++) {
T[i] = sc.next();
}
StringBuilder[] Sw = new StringBuilder[W];
StringBuilder[] Tw = new StringBuilder[W];
for (int i = 0; i < W; i++) {
Sw[i] = new StringBuilder();
Tw[i] = new StringBuilder();
}
for (int i = 0; i < W; i++) {
for (int j = 0; j < H; j++) {
Sw[i].append(S[j].substring(i,i+1));
Tw[i].append(T[j].substring(i,i+1));
}
}
Arrays.sort(Sw);
Arrays.sort(Tw);
boolean all_ok = true;
for (int i = 0; i < W; i++) {
if (! Sw[i].toString().equals(Tw[i].toString())) {
all_ok = false;
break;
}
}
System.out.println(all_ok ? "Yes" : "No");
}
}
Math.pow（累乗計算）で long 型の範囲が必要な場合
Math.pow の返り値は float 型になるため、引数が大きくなると桁あふれして正しい値が計算できません。
そのため、必要な場合は long 型に対応するように処理を自作するしかありません。
累乗計算
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
long B = sc.nextLong();
long ans = -1;
for (int i = 1; i <= 19; i++) {
long A = 1;
// 自前の累乗計算
for (int j = 0; j < i; j++) {
A *= i;
}
if (A == B) {
ans = i;
break;
}
}
System.out.println(ans);
}
}
DP法
「1 円を払い、袋 i から一つの文字を選択する」または「何もしない」という2つの手段から、消費コストと得られるリターンの最大値 or 最小値を計算することに効果的な DP 法が利用できるのでは、という発想まではできていた。実装力がおいてついていなかった。（参考：https://www.youtube.com/watch?v=Y0UEyW64CzM）
DP 法
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
// dp 法
// 初期化
int dp_no = 105;
int[][] dp = new int[dp_no][dp_no];
for (int i = 0; i < dp_no; i++) {
for (int j = 0; j < dp_no; j++) {
// Integer.MAX_VALUE にすると +1 でオーバーフローしてマイナスになり、Max.min の計算がおかしくなるので注意。
dp[i][j] = 100000000;
}
}
dp[0][0] = 0;
String T = sc.next();
int tl = T.length();
int N = sc.nextInt();
// 袋は N 袋分ある
for (int i = 0; i < N; i++) {
// dp は同列のものはすべて直上のものと一旦は同じ値になる
for (int j = 0; j < dp_no; j++) {
dp[i+1][j] = dp[i][j];
}
// 入力文字数分 A だけ loop を回す
int A = sc.nextInt();
for (int j = 0; j < A; j++) {
String S = sc.next();
int sl = S.length();
// これまでにできた文字に、文字 Si_ai を追加して T と完全一致するかを調べる
// これまで一致した文字位置 k に sl を足すと、一致するなら必ず tl 以下になる必要がある
for (int k = 0; k+sl <= tl; k++) {
boolean ok = true;
// 文字列が完全一致するかを調べる
// acbde を作りたいとき ab に cde を追加したり
// abc に de を追加したりして完全一致する場合があるので、
// 以下のような書き方にならざるをえない。
for (int l = 0; l < sl; l++) {
if (T.charAt(k+l) != S.charAt(l)) {
ok = false;
break;
}
}
if (ok) {
dp[i+1][k+sl] = Math.min(dp[i+1][k+sl], dp[i][k]+1);
System.out.println("i:" + i + " k:" + k + " dp:" + dp[i+1][k+sl]);
}
}
}
}
if (dp[N][tl] > 10000000) {
dp[N][tl] = -1;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println("");
}
System.out.println(dp[N][tl]);
}
}
双方向リスト
- https://atcoder.jp/contests/abc344/tasks/abc344_e
- 参考：https://atcoder.jp/contests/abc344/submissions/51478027
なお、想定解答でも Java だと一ケースで TLE になりそう。
双方向リスト
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
HashMap<Integer,Integer> ushiro = new HashMap<>();
HashMap<Integer,Integer> mae = new HashMap<>();
int N = sc.nextInt();
int[] A = new int[N];
for (int i = 0; i < N; i++) {
A[i] = sc.nextInt();
}
// 双方向リストの構築
// 最初の要素 A[0] に対する pointer(Integer.MIN_VALUE) も作成しておくのが味噌
mae.put(A[0], Integer.MIN_VALUE);
ushiro.put(Integer.MIN_VALUE, A[0]);
for (int i = 1; i < N; i++) {
mae.put(A[i], A[i-1]);
}
// 最後の要素 A[N-1] に対する pointer(Integer.MAX_VALUE) も作成しておくのが味噌
mae.put(Integer.MAX_VALUE, A[N-1]);
ushiro.put(A[N-1], Integer.MAX_VALUE);
for (int i = 0; i < N-1; i++) {
ushiro.put(A[i], A[i+1]);
}
int Q = sc.nextInt();
for (int i = 0; i < Q; i++) {
int type = sc.nextInt();
if (type == 1) {
int x = sc.nextInt();
int y = sc.nextInt();
ushiro.put(y, ushiro.get(x));
ushiro.put(x, y);
mae.put(ushiro.get(y), y);
mae.put(y, x);
} else if (type == 2) {
int x = sc.nextInt();
// この位置で nxt/prv に格納しておかないと、remove で削除されてしまう
int prv = mae.get(x);
int nxt = ushiro.get(x);
ushiro.remove(x);
mae.remove(x);
ushiro.put(prv, nxt);
mae.put(nxt, prv);
}
}
int ptr = Integer.MIN_VALUE;
while (ushiro.get(ptr) != Integer.MAX_VALUE) {
ptr = ushiro.get(ptr);
System.out.print(ptr + " ");
}
}
}
int 型と long 型のいつものミス
文字列の最大値が 10^6 なので組み合わせ数を考えれば、int では収まらないという判断ができたはずだった。もしくはどのようにいじっても残り 12 問が AC にならないあたりで long 型を考えるべきだった。
最初からすべて long 型で書けばよいという話もあるが、明確に int, long を使い分ける意識を持ちたいため、あえて int, long を使い分ける。
Re_Fさすがにもう少し真面目&効率的に勉強しないといけないと思ったのでメモをしておく。
初中級者が解くべき過去問精選 100 問
競プロ典型 90 問
AOJ ALDS
Re_FJava 正規表現と String クラス/Pattern&Matcher クラス
以下のあたりの記事が見やすいかもしれない。
String クラスの matches と Pattern クラスの matcher の違いは以下の記事を参照してください。簡単にいえば、String クラスの matches では内部的に Pattern クラスの compile と matcher を利用しており、繰り返して使う場合には compile が余分に回ってしまい効率が悪いとのことです。
問題例
Pattern, Matcher を使うときれいに解ける。
ただ、正直 m.find() を使いたくない。なぜならば、 m.find() は内部でシーケンスが進む（状態が変わる）ので、シーケンス状態を実装者が把握しておかないといけないためである。（確実に m.reset() をかける必要がある）
個人的には、Matcher m = p.matcher(S); をした段階でマッチしたグループ一覧の配列が生成され、そこから p.findGroup($groupCount) などで該当のマッチした文字列グループを直接引っ張ってこれる方が嬉しい。その場合、結局は外部でシーケンスを管理することにはなるが、その方がシーケンスが明示的となるため意図しない挙動が防げそうである。
// java.lang パッケージはデフォルトで読み込まれている（Integer, String, System とか）
import java.util.*; // Scanner クラスなどが入っている
import java.util.regex.*; // Patter クラスなどが入っている
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
String S = sc.next();
int ans = 0;
Pattern p = Pattern.compile("[ATGC]+");
Matcher m = p.matcher(S);
while (m.find()) {
ans = Math.max(ans, m.group().length());
}
m.reset();
System.out.println(ans);
}
}
初中級者が解くべき過去問精選 100 問
綺麗に解けなかった問題のふりかえり
000~999 を検索文字として、文字列S（Smax= 30000） を検索することまでは容易に発想でき、解答の方針も何個か立っていたが実装が今一つできなかった。
貪欲に計算するために、検索文字位置の idx を保存し、また文字が全部マッチしたかを確認する必要があった。
方針は割りとすぐにわかり、直角ならば素直に傾きの算出をすればよい。ただし実装方法で TLE/MLE して詰まる。Perl なら $x = [+{y=>1}, +{y=>4},...] みたいにハッシュの配列を作るところだろうか。Java でもハッシュの配列を作るべきだったか、できたんだろうか。Set を配列に埋め込むとか？
参考１：https://atcoder.jp/contests/joi2007ho/submissions/37859166
参考２：https://atcoder.jp/contests/joi2007ho/submissions/33207503
参考１は面白い解き方だった。数字の桁を増やしてうまく格納するようだ。
参考２は私が書きたかった形だった。boolean なら 5000*5000 でも MLE にならないらしい。
Re_FJava での競プロ高速化に向けて
ABC344 にて、双方向リストを素直に実装したら想定解でも TLE になったので、標準入出力などを見直した。
以下は長いのでトグルで閉じておく。
- https://atcoder.jp/contests/abc344/submissions/51714593
- https://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b
- https://jpliterature.hatenablog.com/entry/java-method-of-console-input-output
標準入出力高速化関数群
import java.util.*;
import java.io.*;
import static java.lang.Math.*;
public class Main {
public static void main(String[] args) throws Exception {
useStdIO();
solve();
close();
}
private static void solve() {
int N = nextInt();
println(N);
}
// 高速化などのためのリスト ===========================================
private static BufferedReader br;
private static StringTokenizer st;
private static PrintWriter pw;
// IO 系 ----------------------------------------------------
private static void useStdIO() throws IOException {
init(false, "", "");
}
private static void useFileIO(String inputFileName, String outputFileName) throws IOException {
init(true, inputFileName, outputFileName);
}
private static void init(boolean useFileIO, String inputFileName, String outputFileName) throws IOException {
if (!useFileIO) {
br = new BufferedReader(new InputStreamReader(System.in));
pw = new PrintWriter(System.out);
} else {
br = new BufferedReader(new FileReader(inputFileName));
pw = new PrintWriter(new BufferedWriter(new FileWriter(outputFileName)));
}
}
// 標準入力系 ----------------------------------------------------
private static int nextInt() { return Integer.parseInt(next()); }
private static long nextLong() { return Long.parseLong(next()); }
private static char[] nextCharArr() { return nextLine().toCharArray(); }
private static double nextDouble() { return Double.parseDouble(next()); }
private static int[] nextIntArr(int n) {
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt();
}
return res;
}
private static int[] nextIntArr(int n, int offset) {
int[] res = new int[n + offset];
for (int i = offset; i < res.length; i++) {
res[i] = nextInt();
}
return res;
}
private static int[][] nextInt2dArr(int rows, int cols) {
int[][] res = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
res[i][j] = nextInt();
}
}
return res;
}
private static long[] nextLongArr(int n) {
long[] res = new long[n];
for (int i = 0; i < n; i++) { res[i] = nextLong(); }
return res;
}
private static long[] nextLongArr(int n, int offset) {
long[] res = new long[n + offset];
for (int i = offset; i < res.length; i++) { res[i] = nextLong(); }
return res;
}
private static long[][] nextLong2dArr(int rows, int cols) {
long[][] res = new long[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
res[i][j] = nextLong();
}
}
return res;
}
private static String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
private static String nextLine() {
String s = "";
try {
if (st != null && st.hasMoreTokens())
s = st.nextToken("\n");
else
s = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return s;
}
// 標準出力系 ----------------------------------------------------
private static void print(Object o) {pw.print(o);}
private static void printf(String format, Object... args) { pw.printf(format, args); }
private static void println() {pw.println();}
private static void println(Object o) {pw.println(o);}
private static void println(int[] a) {
StringBuilder sb = new StringBuilder();
for (int i : a) {
sb.append(i);
sb.append(" ");
}
println(sb);
}
private static void println(int[][] a) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
sb.append(a[i][j]);
sb.append(" ");
}
sb.append("\n");
}
print(sb);
}
private static void println(long[] a) {
StringBuilder sb = new StringBuilder();
for (long i : a) {
sb.append(i);
sb.append(" ");
}
println(sb);
}
private static void println(long[][] a) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
sb.append(a[i][j]);
sb.append(" ");
}
sb.append("\n");
}
print(sb);
}
// 加工系 -------------------------------------------------
private static void sort(int[] a) {
List<Integer> b = new ArrayList<>();
for (int el : a) { b.add(el); }
Collections.sort(b);
for (int i = 0; i < a.length; i++) {
a[i] = b.get(i);
}
}
private static void sort(long[] a) {
List<Long> b = new ArrayList<>();
for (long el : a) { b.add(el); }
Collections.sort(b);
for (int i = 0; i < a.length; i++) {
a[i] = b.get(i);
}
}
private static void sort(int[] a, Comparator<Integer> comp) {
List<Integer> b = new ArrayList<>();
for (int el : a) {
b.add(el);
}
Collections.sort(b, comp);
for (int i = 0; i < a.length; i++) {
a[i] = b.get(i);
}
}
private static void sort(long[] a, Comparator<Long> comp) {
List<Long> b = new ArrayList<>();
for (long el : a) {
b.add(el);
}
Collections.sort(b, comp);
for (int i = 0; i < a.length; i++) {
a[i] = b.get(i);
}
}
private static <T extends Comparable<T>> void sort(T[] a) {
List<T> temp = new ArrayList<>();
for (int i = 0; i < a.length; i++) {
temp.add(a[i]);
}
Collections.sort(temp);
for (int i = 0; i < a.length; i++) {
a[i] = temp.get(i);
}
}
private static <T> void sort(T[] a, Comparator<? super T> comparator) {
List<T> temp = new ArrayList<>();
for (int i = 0; i < a.length; i++) {
temp.add(a[i]);
}
Collections.sort(temp, comparator);
for (int i = 0; i < a.length; i++) {
a[i] = temp.get(i);
}
}
private static int[][] copy(int[][] orig) {
int[][] temp = new int[orig.length][];
for (int j = 0; j < orig.length; j++) {
temp[j] = Arrays.copyOf(orig[j], orig[j].length);
}
return temp;
}
private static <T> void swap(T a, T b) {
T temp = a;
a = b;
b = temp;
}
private static long powLong(long a, long b) {
long pow = 1;
for (int i = 0; i < b; i++) {
pow *= a;
}
return pow;
}
private static void close() {
pw.flush();
try {
br.close();
} catch (IOException e) {
e.printStackTrace();
}
pw.close();
}
}
幅優先探索
深さ優先探索と幅優先探索のどちらかでいけることはすぐに分かった。しかし、その2つの違いを厳密に検証せずに再帰関数の方が個人的に実装しやすいと思い、深さ優先探索で実装した結果、行って戻ってのエネルギー回復の無限ループにハマって時間切れとなった。非常に悔しい。
参考
Re_Fセグメント木
ぱっと見解けそうでセグメント木の概念を知らないために、結局解けなかった。セグメント木の概念を知った後だと、べき乗の探索をどう調査/管理するかいう点で一からセグメント木の概念を再開発しようと頭を捻っていたんだなぁということに気づいた......。
Re_FJava での構造体またはPair/Triple的なデータ構造の作り方、ときどきソート
C問題で恥ずかしい失態をしてしまった。
Java では構造体の機能がなく、 C++ の vector のようなものもない。データ構造として Pair はあるが今回のC問題のように3つのデータセットを配列に入れて、特定のキーでソートするということが既存の機能では存在しない。
この問題の解決法は、「構造体のようなクラスを作成する」ということなのだが、今までずっと避け続けてきていたために今回のC問題にど真ん中に突きつけられて、解けずに終わってしまった......。
基本ではあるが、身になるものが多かったので非常に勉強にはなった。次からは大丈夫であろう。
学んだこと
- 構造体のようなクラスの作り方を学んだ
- そもそも static なクラスの作り方が朧げだったので学べた
- クラスを使ったソートの方法を学んだ
-
Arrays.sort(cards, (c1,c2) -> Integer.compare(c1.C, c2.C));の書き方に面食らったが、perlを思い出すと同じような形だと気づいた
-
Java で構造体を表現するクラス
private static void solve() {
int N = nextInt();
Card[] cards = new Card[N];
for (int i = 0; i < N; i++) {
int A = nextInt();
int C = nextInt();
cards[i] = new Card(i+1, A, C);
}
// perl の sort {$a <=> $b} @arrays と同じノリとなる
// cards を List<Card> cards = new ArrayList<>() で用意した場合は、
// cards.sort(Comparator.comparingInt(c -> c.strength)); で sort する
Arrays.sort(cards, (c1,c2) -> Integer.compare(c1.C, c2.C));
// Queue<Integer> queue = new Queue<Integer>(); で add&remove してみることも考えたが、
// 最終的にソートする必要があったため、ArrayListとした。
// そもそも可変長配列を使うにはこちらで十分。
// なお、可変長配列にVector型もあるが、パフォーマンスの関係でもう使われていないらしい。
List<Integer> list = new ArrayList<Integer>();
int minA = 0;
for (int i = 0; i < N; i++) {
if (cards[i].A > minA) {
minA = cards[i].A;
list.add(cards[i].idx);
}
}
Collections.sort(list);
int m = list.size();
println(m);
for (int i = 0; i < m; i++) {
print(list.get(i) + " ");
}
}
// この形でクラスを作成することで、構造体がないJavaでも構造体のようなものを作ることができる。
static class Card {
int idx;
int A;
int C;
Card(int idx, int A, int C) {
this.idx = idx;
this.A = A;
this.C = C;
}
}
bit 全探索
bit 全探索に至る発想自体は
各鍵が正しいかダミーかの組み合わせは 2^N 通り
の文言の時点で早く行き着いたが、bit 全探索の実装自体が曖昧だったため、実装に手間取ってしまった。あと、簡単のために桁数計算をしていおいたが、急ぎのために変数名も雑になってしまった。
bit 全探索
// 鍵の正誤を総当りするにあたり、取りうる2進数の桁数を取得しておく
long ii = powLong(2,N);
String bi = Integer.toBinaryString((int)(ii-1));
int len = Integer.toBinaryString((int)(ii-1)).length();
// bit全探索 で全ての組において、テストをチェックする
// テストがパスすれば組み合わせを +1 する
int ans = 0;
// bit全探索の全通りのloop
for (int i = 0; i < 1 << N; i++) { // 1<< N は 2^N とみなす
// 鍵の組み合わせ毎にテストを確認する
boolean ok = true;
for (int j = 0; j < M; j++) {
// テスト結果と一致するかを確認する
int cnt = 0;
for (int k = 0; k < C[j]; k++) {
// 正しい鍵の個数をカウントする
int tmp = A[j][k];
if ((1 & i >> (len-tmp)) == 1) { // 鍵の組み合わせに対して bitをずらし、左からX番目の鍵が「正」かを確認している
cnt++;
}
}
// R の結果に一致するか
if (
(cnt >= K && R[j].equals("o"))
|| (cnt < K && R[j].equals("x"))
) {
} else {
ok = false;
}
}
if (ok) {
ans++;
}
}
bit 全探索にてポイントとなるのは、1 << N と (1 & i >> (len-tmp)) == 1 の処理であろう。
-
1 << Nは「1を左方向に N 桁ずらした数字」を取得する（= 2^N） -
(1 & i >> (len-tmp)) == 1は i の左から len-tmp bit 目のフラグが立っているか
を見ている。
bit 全探索というと面食らうが、この2点の書き方さえ押さえれば通常の全探索と同じ実装となる。
参考
Re_F法則の定式化について
文章から法則は簡単にわかるが、それをコードの形に落とし込むための定式化ができなかった。純粋な実力不足を痛感させられて悔しい。
解法としては、
- レベル K を配列用いて単純に転写してレベル K+1 の配列に移す
- （レベル 1 を作り、それをもとにレベル 2 をつくり、そこからさらにレベル 3 を作り......を目的のレベルまで繰り返す）
というシンプルなものであったが、配列を用いた方法での道筋をぱっと描けなかった（レベルK→レベルK+1→レベル K+2 の拡張しながらコピーするイメージが持てなかった）のと、再帰関数での考え方に囚われてしまったことが原因となる。
定式化について
コードを書くにあたってその法則を定式化するのは非常に有用となる。今回であれば、
という定式化をいかに早くできるかがポイントとなる。これは DP 法でも同様であり、コードの書く速度が変わってくる。
Re_Fbit 全探索
前々回に続き、bit 全探索であった。ただし、今回は bit 全探索に気づくまでにあまりにも時間がかかりすぎた......非常に悔しい。
今回の問題であれば、「N 個の売り場に行くか行かないかを選んでいる『組み合わせ』」という発想から、「2^N の組み合わせならば bit 全探索だ！」 という考えに行き着かないといけなかった。
bit全探索
int min = Integer.MAX_VALUE;
for (int i = 0; i < 1 << N; i++) { // 1<<N は 2^N に同じ
boolean[] chk = new boolean[M];
int cnt = 0;
for (int j = 0; j < N; j++) { // 2^N の2進数表記の桁数は N なのだから 0~N でずらす
if ((1 & i >> j) == 1) {
for (int k = 0; k < M; k++) {
if (S[j].charAt(k) == 'o') {
chk[k] = true;
}
}
cnt++;
}
}
boolean all_chk = true;
for (int j = 0; j < M; j++) {
if (!chk[j]) {
all_chk = false;
}
}
if (all_chk) {
min = Math.min(min, cnt);
}
学んだこと
bit 全探索のポイントとなるのは、1 << N と (1 & i >> j == 1) の処理である。
- 1 << N は「1を左方向に N 桁ずらした数字」を取得する（= 2^N）
- (1 & i >> j) == 1 は i の右から j bit 目のフラグが立っているかを確認する
2 について、私は組み合わせの順番（ABCD...）と揃えるために 1001... の bit フラグを左から頑張って数えようとしがちであった。しかし、bit フラグは単なる組み合わせを表すだけで、右から数えようが左から数えようが同じである。気にせずに右へ bit シフトすればよい。
Re_F累積和
要素数 N である配列 A について、区間 [l, r) （0 <= l < r < N）の総和を計算するための方法となる。
累積和
int N = nextInt();
int Q = nextInt();
int[] A = nextIntArr(N);
int[] S = new int[N+1];
// 累積和の計算
S[0] = 0;
for (int i = 0; i < N; i++) S[i+1] += S[i] + A[i];
for (int i = 0; i < Q; i++) {
int L = nextInt();
int R = nextInt();
println(S[R] - S[L-1]);
}