メモ化再帰の話
2020,11,9
ABC 182 E 解説放送にてメモ化再帰を難しいと思ったので書く
とにかく例題に触れて慣れよう!
例題
- ABC182E .... グリッドが光る条件はそのグリッドの周りの4方向が光っていることにある。よって大枠として全てのグリッドを見る。1つのグリッドを見るときは、その周りのグリッドも再帰的にみる。ここで、一度見たグリッドは大枠で見たときにO(1)でreturn するため、1つのグリッドを走査する回数は高々1回となる。
大切なこと
メモ化再帰はメモ化全探索である。dpは前の状態から今の状態を作るときに使う。メモ化再帰は今の状態を作るために必要な状態をすべて確定させながら今の状態を決める。
イメージを大切にしよう。
セグ木の使い方
例題
Java備忘録
継承(class A extends B)
- オーバーライドしたメソッドはそのまま呼び出す。
- もとのメソッドはsuper.メソッド名で呼び出す。
- フィールドはできるだけprivate,protectedにする。
- コンストラクトは上位スーパークラスから呼び出される。つまり、サブクラスのコンストラクタの変更が優先される。
- 親クラスの表し方はsuperである。つまり、親クラスのコンストラクタを明示的に呼び出すときはsuper(引数)である。
コンポジション
あるクラスのフィールドで他クラスのオブジェクトを利用すること。要は「部品」。継承とは対極にある?
Delegation(委譲)
継承とコンポジションの中間の関係。
あるクラスを操作するために別のクラスを必ず経由させる。そのためにコンポジションと同じ文法形態をとる。
Upcasting
基底クラスのメソッドで引数を基底クラスにしておけば引数を派生クラスに変更しても正しく呼び出される。安全。親クラスの型の参照で子クラスを指すことでポリモーフィズムを達成しやすい。ただし、子クラス独自のメソッドを呼び出すことができない。
Downcasting
安全でない型変換でClassCastExceptionが投げられる。
これは包含関係を考えれば問題ない事がわかる
列挙型enumの使い方
enum 名前 {a,b,c}
ポリモーフィズム
継承とかでプログラムの拡張を支援
オーバーライド
オーバーライドされるのはpublic メソッドだけ
変数はされない。
インターフェース
class A implements B
抽象クラスより抽象度合いが高い。
実装を全く持たない。
C言語のヘッダファイルみたい。
1つのクラスが複数のインターフェースを持つことができる(多重継承)。Javaでは複数のクラスを継承することを禁止している。
変数は永遠にstatic
抽象クラス
クラスとインターフェスの中間
このクラスそのものはnewされない。子クラスを経由してのみ存在できる。
abstract class A{
public abstract void play(Note n);
}
このplayメソッドは必ず子クラスでオーバーライドされなければならない。
子クラスで親抽象クラス
リスト
List<クラス名> A =new ArrayList<クラス名>
ArrayList=配列
LinkedList=順序配列
Set
C++のsetと同じ
HashSet=unorderedset
TreeSet=orderedset
Map
HashMap=unorder
TreeMap=order
例外処理
if(t==null) throw new NullPointerException();
newできるのはJava.lang.throwableを継承したクラスだけ。
れいがいおthrowするとメソッドは終了
try{
例外が起こりそうな処理を普通に書く
}catch(Type1 a){
}catch(Type2 a){
}......
Typeに一致する処理だけ行われる。
どのクラスでも記述可能
コードの複雑化の抑制 : これはC言語のプロキシをイメージすればよい
例外クラスの作り方
class A extends Exception{
}
全ての例外をキャッチする
catch(Exception A){
}
これはcatch列の最後に記述する。その他の例外処理として記述する。
Exceptionクラス
String getMessage():詳細なメッセージを返す
String toString(): 詳細なメッセージを含んだクラス情報を返す
Void printStackTrace(): 例外発生時のcall stack trace を返す
APIが豊富である。
java.lng,java.io,java.utilなどいろんなパッケージにAPIが存在
RuntimeException
いくつかの例外クラスは勝手に作成されて(try文の中じゃなくても)throwされるクラスもある
catchしないのでmainメソッドまで到達
入出力
java.io.File : pathに関するクラス(ファイルを参照していない)
ファイル処理
- パス操作
- ディレクトリの作成
- ファイルの種類の判別
など
書き方は自分で調べる。
String fileName="AAAAA.txt";
PrintWriter writer = null;
writer = new PrintWriter(new
BufferedWriter(new FileWriter(fileName)));
writer.println("writing to the file ...");
writer.println("completed.");
String fileName = ".project";
reader = new BufferedReader(new FileReader(fileName));
String line;
while *1 != null)
System.out.println(line);
}
Path path = Paths.get(".project");
List<String> allLines = Files.readAllLines(path);
11/9
コンカレンシ(Concurrency)
並行プログラミング(Concurrent programming):
複数の処理を同時動作させる。時間的に同時ではない。
cf.) 並列:時間的に同時に動作
並行は並列を含む。
タスク : 断片化された処理内容
スレッド : タスクを実行するのがスレッド
イベント駆動型のアーキテクチャを実現できる。(ポーロングがなくなる)
スレッドの作成
スレッドで利用するクラス
implements Runable
extends Thread
mainメソッドでは、
new Thread(new クラス名).start();
または
ExecutorService exec=Executors.newCachedThreadPool();
exec.execute(new クラス名);生成
exec.shutdown();待つ
スレッドオプション
t.join() : スレッドtの実行が終了するまで中断
まとめ
コンポジションを使うのがよい。
振る舞いの違いは継承、状態の変化はコンポジション
has-a , is-a を意識してコーディングする。
*1:line = reader.readLine(
巡回セールスマン問題
既に道の候補があり、どの道を選んで最短で行くかではなく、
全ての<ノードを通るとき>という条件が追加されている。
よって、今どのノードを通って最後にどのノードにいるのかをメモするデータ構造を用いる。
dp[S][V] := bit列で表されたSが状態。Vが最後のノード。初期状態はdp[1][0]=0;
最終的に求める値はdp[1<<n-1][i] i=1,2,3,...n-1
となる。
また、この手の問題はNが小さくなるため、ワーシャルフロイド法で回り道する最短路を計算することもある。
キーワード : 全てのノードを通る
ABC 180 E
LCS (最長共通部分文字列)
例題
- ABC 141 E