メモ化再帰の話

2020,11,9

ABC 182 E 解説放送にてメモ化再帰を難しいと思ったので書く

 

とにかく例題に触れて慣れよう!

例題
  • ABC182E .... グリッドが光る条件はそのグリッドの周りの4方向が光っていることにある。よって大枠として全てのグリッドを見る。1つのグリッドを見るときは、その周りのグリッドも再帰的にみる。ここで、一度見たグリッドは大枠で見たときにO(1)でreturn するため、1つのグリッドを走査する回数は高々1回となる。

 

大切なこと

メモ化再帰はメモ化全探索である。dpは前の状態から今の状態を作るときに使う。メモ化再帰は今の状態を作るために必要な状態をすべて確定させながら今の状態を決める。

 

イメージを大切にしよう。

Visual Studioでbits/stdc++が使えなくなった時の対処法

  1. ツールバーのプロジェクトから<プロジェクト名>のプロパティを選択
  2. VC++ディレクトリを選択
  3. インクルードディレクトリにbits/stdc++があるフォルダのパスを追加。今回は前のバージョンのインクルードディレクトリにbits/stdc++が存在したので、そのフォルダのパスを追加した。

参考サイト: 

docs.microsoft.com

Java備忘録

継承(class A extends B)
  1. オーバーライドしたメソッドはそのまま呼び出す。
  2. もとのメソッドはsuper.メソッド名で呼び出す。
  3. フィールドはできるだけprivate,protectedにする。
  4. コンストラクは上位スーパークラスから呼び出される。つまり、サブクラスのコンストラクタの変更が優先される。
  5. 親クラスの表し方はsuperである。つまり、親クラスのコンストラクタを明示的に呼び出すときはsuper(引数)である。

 

f:id:plown:20201028095324p:plain

アクセスコントロール

 

コンポジション

あるクラスのフィールドで他クラスのオブジェクトを利用すること。要は「部品」。継承とは対極にある?

 

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

C++のmapと同じ。連想配列

HashMap=unorder

TreeMap=order

 

例外処理

if(t==null) throw new NullPointerException();

newできるのはJava.lang.throwableを継承したクラスだけ。

れいがいおthrowするとメソッドは終了

try {
//
例外を発生し得るコード
//
...
} catch(Type1 id1) {
//
Handle exceptions of Type1
} catch(Type2 id2) {
//
Handle exceptions of Type2
} catch(Type3 id3) {
//
Handle exceptions of Type3
}
// etc...
try {
//
例外を発生し得るコード
//
...
} catch(Type1 id1) {
//
Handle exceptions of Type1
} catch(Type2 id2) {
//
Handle exceptions of Type2
} catch(Type3 id3) {
//
Handle exceptions of Type3
}
// etc...
try {
//
例外を発生し得るコード
//
...
} catch(Type1 id1) {
//
Handle exceptions of Type1
} catch(Type2 id2) {
//
Handle exceptions of Type2
} catch(Type3 id3) {
//
Handle exceptions of Type3
}
// etc...

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
を返す

Void printStackTrace(): 例外発生時のcall stack trace を返す

APIが豊富である。

java.lng,java.io,java.utilなどいろんなパッケージにAPIが存在

 

RuntimeException

いくつかの例外クラスは勝手に作成されて(try文の中じゃなくても)throwされるクラスもある

例:NullPointerException()

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