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…

計算量の工夫 昨日ABC123に参加してきました. D問題 ボクはコンテスト中には解くことができず解説を見てACしました. x , y , z 個数づつ存在しているa , b , c を全て足して全探索していては到底間に合いません. そこで今回は k の値に制約がついていること…

yukicoder 209 参加記 No.807 umg tours - yukicoder yukicoder２回目の参加となりました. 前回は星2つでリタイアしてしまったので今回は星2つを通そうと意気込んでいました. #A No.804 野菜が苦手 この問題は,条件が100以下と小さいので1から少しずつカウン…

yukicoder初参加してみました.atCoderの方がAGC連続で手も足も出なくて悔しいので参加してみました. Twitterでログインできるのはいいですね. yukicoder contest 208 初参加の感想としては,AtCoderとあまり変わらないのかなと思いました.AtCoderと違いレベル…

2分岐探索 atcoder.jp 問題概要 N日満腹度が0より大きい状態でいる.毎日以下の3つの行動のいずれかをする 代金a円払いbの栄養をえる 代金c円払いdの栄養をえる 栄養を e 失う この状況下で生き残るために払う最初の値段を求める 考え方 最初に栄養をとり残り…

単純グラフ DFS atcoder.jp 問題概要 N頂点M辺の無向グラフが与えられる. 全ての頂点を丁度一回づつ通る経路は何通りあるかを求めよ. 始点は頂点1とする. 解答 今回の問題はDFSを用いて解くことができる. しっかり書いたコードは下に置いておき擬似コードを…

indexに数字以外を餅入りたい時や二つの対応付けしたい時に使う import import java.util.HashMap; 定義 HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); 追加 すでに存在しているkeyを指定したらvalueが上書きされる map.put( key , value ); 取得 : 返り値はvalue 存在しな</integer,integer></integer,integer>…

atcoder.jp 問題概要 ある多角形の全ての頂点の座標が与えられる. 二点の座標が与えられその点を結んだ時に多角形を幾つの図形に分割するかを求める 解法 多角形を考えるのは難しいので多角形の辺と分割する直線の交わる本数を求めることで、幾つの図形に分…

atcoder.jp 問題概要 'a','b','c'の３種類の文字のみを含むN文字の単語を辞書順で出力せよ 考察(TLE) abcの3つの文字なので3進数を使って0ならa,1ならb,2ならcを出力すればいいのかと思い実装したらコードが長くなりTLEしてしまった 解答 この問題は再帰関数…

ベルマンフォード法 ベルマンフォード法とはグラフにおける最短経路を求めるアルゴリズム(解法)の一つ.有効グラフの時に使える.この他にも最短経路を求めるアルゴリズムにはダイクストラ法やワーシャルフロイド法が存在する. 身近な例 : ある駅からある駅に…

排他的論理和 ABC121-D-{X OR World} 有効グラフ ベルマンフォード ABC061-D 単純グラフ ABC054 - C - One-Storke Path 素因数分解 ABC052 - C - Factors Of Factorial DFS ABC054 - C - One-Storke Path 最善手ゲーム ABC048 - D - An Ordinary Game 文字列…

atcoder.jp 最長経路問題 トポロジカルソート DP この二つの組み合わせの問題だった.DPを実行するためにまず初めにトポロジカルソートをした.トポロジカルソートに関しては以前書いたので省く. トポロジカルソート 今回はトポロジカルソート済みとしてDPを行…

トポロジカルソートを書いてみたので記録しておく. ToplogocalSortとは. edgeをソートする方法の一種である。並び替えをします.ソートされた後の配列をみた時に配列の左から右向きのpathは存在するが右から左むきのpathは存在しないようにするということです…

atcoder.jp LCS(Longest Common Subsequence)最長経路問題です。 問題 文字列s , tが与えられた時に共通部分列で最長の物を求める. 最初全探索するのかと思ったが明らかに実行時間が間に合わない。それならばDPだろう.今回のDPの定義としては lcs[i][j] : 文…

atcoder.jp ナップザック問題のversion2.価値に制限がある場合.重さに制限がある場合と解き方が異なります. 提出 DPで解く ナップザック問題といえばおなじみのDPですが今回はDPの定義が難しい.いつもの重さに制限がある場合は dp[i][j] : i 個まで見た時の…

DP(1次元)と全探索の複合問題 abc099.contest.atcoder.jp この問題はこちらにも書いてある通りC問題にしては難しいです.しっかり理解したい方はこの記事読んだ方が100倍わかりやすいです。 提出コード 問題 1 , 6p , 9q のうちから好きな数を選び取り合計をn…

atcoder.jp 考察できるかの問題でした。数学できる人には簡単かもしれない。 問題文に翻弄されてはいけない 問題文では時刻iの時に右にも行けるし左に戻ることもできると示されている。しかし実際問題左に行く必要がなかったのだ。 左に行くくらいなら何もせ…

atcoder.jp ASCIIコードとCharコードを変換してときました。 それぞれの文字に共通して含まれるアルファベットを見つけなくてはならなかったので数字の方が扱いやすいと考えてアルファベットをASCIIコードに変換しました。 int number = ( int ) str . charA…

atcoder.jp class Pair を定義しようの回でした。(x,y）今回でいうと(出席番号,身長)の組みが与えられてその時に身長順でソートしようという問題です.絶対に(出席番号,身長)の組みを変えてはいけないということです。変えてしまうと自分の身長が他人お身長と…

atcoder.jp いもす法 いもす法聞いたことがあるだろうか。私はこの問題で初めてであった。多次元でもできるようが今回は一次元での問題なので理解することができた。 解説こちらのAtCoderの公式解説を見るのが一番わかりやすかった。(他のサイトも探したが次…

atcoder.jp まだまだC問題で苦戦してしまいます。脳筋で全探索だと考えてしまった。 この問題for分の4重ループで通ってしまうのです。 提出コード ABC074C 2WAしてしまいました。サンプルケースは通ったのでいけるかと思ったがダメでした。どこがダメかにら…

atcoder.jp C問題.苦戦しました. 考察 考察できませんでした。与えられたのが100とか出ていたので全探索するのかと思ったが解説を見て、全探索はダメですと言われて悲しくなった。 今回キーとなる考え方は、100点２問よりも200点２問といたほうがポイントが…