DPというのは不思議で、ただ適当に配列をループで回しているだけに見えても難しい問題を解決してくれていたりします。 実際に解決できているのだから、間違っていることはないのでしょうが、直感的に正しいとはとても思えません。 最近、DPは効率のいい全探…
全域木とは あるグラフがあったとき、そのグラフの全ての頂点といくつかの辺を使って作られた新たなグラフが連結で閉路を持たないとき、新たなグラフを元のグラフの全域木という。 最小全域木 辺がコストを持つとき、コストの総和が最小の全域木を最小全域木…
問題リンク 考察 数列 の和を最大化したいので、できるだけ全ての を に近づけたい。 として問題なさそう。 については が を上回らないのなら が を上回るのなら とすると辻褄を合わせたまま最大化できそう。 こんな感じで数列 を後ろから見て行って数列 を…
範囲を選択して zf で折り畳み作成 折り畳み内で zo で展開、 zc で再度折り畳み zdで折り畳みの削除 zO で折り畳みを削除して展開
struct reporter { reporter() { cout << "construct" << endl; } ~reporter() { cout << "destruct" << endl; } reporter(const reporter &) { cout << "copy" << endl; } reporter(reporter &&) { cout << "move" << endl; } reporter &operator =(const r…
コード vector<uint64_t> prime_factor(uint64_t n) { vector<array<uint64_t, 2>> ret; for (uint64_t i = 2; i * i <= n; ++i) { if (n % i) continue; uint64_t cnt = 0; while (n % i == 0) { n /= i; ++cnt; } ret.push_back({ i, cnt }); } if (n != 1) ret.push_back({ n, 1 }); re</array<uint64_t,></uint64_t>…
問題リンク まず、 を素因数分解し で考えてみます。( はそれぞれ素数) この時 で割り切ることのできる最小の とは です。 これは が必ず素因数として を 個以上もつためであり、 ならば、 は を内包します。( と は互いに異なる素数なので、 は必ず割り切れ…
C++において、staticは複数の意味を持ちます。 関数内に書けば静的変数。 グローバルに書けば内部リンケージ変数、関数。 メンバ変数に書けば静的メンバ変数(ただし別途実体定義が必要)。 さらにinline指定と組み合わせることができ、 グローバルにinline st…
全ての図形は三角形の集合として表せるため、三角形の面積比が相似比の2乗であるかを考える。 と がある。 ここで、 である。 相似比を としたとき、 の底辺 は の底辺 により であり また、 の高さを 、 の高さを としたとき、 となる。 これらより、 の面…
問題ページ 最近JOI(日本情報オリンピック)の存在を知り、過去問を解いたりしていたのだが、おそらくDP的な考え方を使う問題を解いた。1 DPは前の値を使って次の値を計算できるか、次の値を計算するときにはその前の値がすべて計算終了していなければいけな…
コンテストリンク ABCDの4完。 A問題 よくある算数の問題。 ただ、簡単な問題は凡ミスしやすくて苦手。 B問題 s.size()-t.size()だけ全探索しようとしてs.size()==t.size()のケースでwaを出してしまった。 C問題 普通に計算するとのため紙に書いてみる。 そ…
問題リンク 組み合わせ計算で解こうとして撃沈。 どうしたらいいの...と思いながら解説を読んだ。 発想が足りない。 どうしたらいいのだろう。
問題リンク の範囲に2019の倍数があれば答えは必ず0になる。 ということには早めに気付けた。 しかし、愚かな私は2019を倍数に含まない数列に対して、 が最適解だと思い込み、WAを重ねた。 少し考えればわかることなのに...
問題リンク 解説をみて、 が の制約を無視した時の組み合わせの数。というのが理解できなかった。 があるので、これを利用してうまく求めるんだな、なんて思っていたら全く分からず。 文字列Sの中から、それぞれ違う位置にある文字を3つ取ってきたとき、小さ…
自分なりの理解をまとめておく。 環境変数 プロセスが持つ変数。 親プロセスの持つ環境変数は子プロセスへと引き継がれるが、その逆はない。1 プロセスは自分自身の環境変数を自由に書き換えることができ、例えばenvコマンドなどは環境変数を書き換えたうえ…
競プロやっていたら必要になった。 自分なりに理解したことをまとめておく。 重複順列 なんてことはない。 1度選んだものをもう一度選べるというもの。 例えば、1から3の整数の選び方の順列といえば、となるが、 重複順列では一度選んだ整数をもう一度選びな…
C、C++はローカルに関数を宣言できます。1 例えば以下のように stdio.h をインクルードしなくとも、コンパイラは警告も何も発しません。 int main() { int puts(const char *); puts("Hello World!"); } ローカルに宣言された関数識別子の有効範囲はそのスコ…
ローカルスコープで関数を宣言する場合、extern以外の明示的な記憶域クラス指定子を持ってはならない。
6つのアルファベットの並べ方について考えます。 ただし、同じ種類のアルファベットを交換しただけのようなものは区別しません。 つまり、をとしたとき、 この2つは区別されません。 も同様です。 どう計算したらいいのでしょうか？ 重複を取り除いていく考…
- - 抽象文字集合 Unicodeが対象とする文字集合 符号化文字集合 抽象文字集合に非負整数の番号を付けたもの 文字符号化形式 コンピュータ中での符号化文字集合データ表現方法 文字符号化方法 文字符号化形式にエンディアンなどを決定したもの 符号化文字集合…
識別子 [_a-zA-Z][_a-zA-Z0-9]*[%#$]? 定数識別子 (#[%#$])|(#[_a-zA-Z0-9]+[%#$]?) ラベル識別子 @[_a-zA-Z0-9]+ 整数 ([0-9]+)|(&[hH][0-9a-fA-F]+)|(&[bB][0-1]+) 実数 ([0-9]+(?:\.[0-9]+)?[eE]-?[0-9]+)|([0-9]*\.[0-9]*) 文字列 "[^"]*(?:(?:["\n])|(?…
FactoryMethodパターンはあるオブジェクトを生成するインターフェイスを作成し、対象オブジェクトの作成に使用することで、より柔軟にしようというもの。 make_shared<derived> や new derived など、インスタンスの生成はどうしても具体的になってしまう。 オブジェ</derived>…
Prototypeパターン Prototype パターン（英: Prototype pattern、プロトタイプ・パターン）とは、ソフトウェア開発で用いられる、生成に関するデザインパターンの1つである。生成されるオブジェクトの種別がプロトタイプ（典型）的なインスタンスであるとき…
BNFとは バッカスナウア記法のことであり、文脈自由文法を定義する事ができる。 プログラミング言語の構文はこのBNFを使用して定義されることが多い。 分かれば何でもいいので、独自に拡張したBNFや図を使用して定義されることもある。 例として四則演算と括…
THENの後に改行が含まれないとき。 ただし、ネストされたIF文でTHENの後に改行が存在する場合、それ専用のENDIFが必要になる。 ' OK IF A == 0 THEN IF A == 0 THEN ? "OK" ENDIF ' 2つ目のIF文に対応するENDIF ' NG IF A == 0 THEN IF A == 0 THEN ? "NG" E…
はてなのtex記法だとうまく表示されないのでTeXclipで作成した画像を張っ付ける。
こちらを参照しながらバッと書いたもの。 設定エリアの変数値を変更してバイナリファイル名やソースディレクトリ、コンパイラやそれに渡されるオプションを設定する事が出来ます。 coption はコンパイルオプションの、 loption はリンクオプションの略。 # =…
「使えそうっ！」となったものを順次メモる。 Key Effect CTRL-H 1文字削除 CTRL-U 現在入力中の行を削除
終端(EOF)に達した場合、1文字でも読み込まれていたのなら、改行文字を読まずとも成功したものされる。 その場合は文字列バッファに改行文字が含まれないので、 feof 関数を使用してファイル終端による終了か区別する必要がある。 終端に達し、かつ1文字も読…
