javaにはnext_permutationが実装されていないので自前で実装する. 目的 今回やりたいことはの集合が与えられた時に順列を全列挙する { 1 , 2 , 3 , 4 } 上の集合に対して以下を出力する ( 1 , 2 , 3 , 4 ) ( 1 , 2 , 4 , 3 ) ( 1 , 3 , 2 , 4 ) ( 1 , 3 , 4 …

問題 atcoder.jp 解法 マス目の最短経路を求める問題. BFSを用いる.普通のBFSではなくスタート位置がたくさんあります. スタート位置を先に全てQueueに突っ込んでおきます. そこから幅優先探索を使って最短な距離を求めていきます.

問題 第一回日本最強プログラマー学生選手権-予選- C問題 atcoder.jp リアルタイムで参加したのですが, B問題を無限にバグらせてしまい20分くらいしかかけられませんでした. コンテスト終了後に考察したがわからずでした 方針 今回注目するのは左右の関係で…

bit全探索 フラグを立てて部分集合の全列挙をするときに使うそうです. 理解は未だあやふや. bitのシフト演算の知識と bit演算&の式の理解が必要となります. 概要 部分集合の全列挙 以下のような全体集合があるとします { "dog" , "cat" , "bird" }; 求めたい…

atcoder.jp 二分探索の問題 今いる場所のよりひとつ右側を探す. テクニックとして番兵存在をおくと条件分岐が少し楽になる . また4つの通る候補を見つけた後にどのように処理をするかは参考にあげた方の回答がとても綺麗だった. 参考 こちらの方の回答がって…

Javaで二分探索を実装しました class BinarySearch { static int solve(int[] array, int key) { int left = 0; int right = array.length - 1; int mid; while (left <= right) { mid = (left + right) / 2; if (array[mid] < key) { left = mid + 1; conti…

DPの問題 atcoder.jp これは状態を列挙することと, どのように状態が遷移するかを見ることが必要となる. 今回の場合は文字の長さを i 番目まで見た時に状態がいくつあるか. ABCどれも使わない Aを使う場合 ABまで使う場合 ABCまで使い完成している場合 以上…

多次元DPの問題 dp[len][i][j][k] := 長さがlenのlen−２文字目が i len-1 文字目が j len 文字目が k である. 問題文に適する文字列の種類数 と定義する. import java.util.Scanner; class Main { static final long mod = 1000000007; public static void m…

DP 多次元DP ☆☆☆☆☆(20190819) D - We Like AGC ☆☆☆☆(20190820) D - パスタ (Pasta) 数え上げ ☆☆☆☆☆☆(20190820) https://atcoder.jp/contests/abc104/tasks/abc104_d 二分探索 高速化 ☆☆☆☆(20190820) D - Lazy Faith 決め打ち ★★★★★★★★★ D - Widespread ☆☆☆ S…