staticの意味

C++

C++において、staticは複数の意味を持ちます。

関数内に書けば静的変数。
グローバルに書けば内部リンケージ変数、関数。
メンバ変数に書けば静的メンバ変数(ただし別途実体定義が必要)。

さらにinline指定と組み合わせることができ、

グローバルにinline staticした場合、staticが優先され内部リンケージ変数、関数となりますが、
メンバ変数として使ったならば、inlineが優先され全ての翻訳単位で同一のアドレスを指すようになります。

調べていたら、C++ではconst変数というだけで内部リンケージになるそう。(C言語は普通に外部リンケージ)
何もわからなくなってきた。

面積比は相似比の2乗

数学

全ての図形は三角形の集合として表せるため、三角形の面積比が相似比の2乗であるかを考える。

\triangle A と \triangle B がある。
ここで、 \triangle A \sim \triangle B である。

相似比を n : m としたとき、 \triangle B の底辺 b は \triangle A の底辺 a により b = a\frac{m}{n} であり
また、 \triangle A の高さを c 、 \triangle B の高さを d としたとき、 d = c\frac{m}{n} となる。

これらより、 \triangle A の面積は \frac{ac}{2} 、 \triangle B の面積は \frac{a\frac{m}{n}c\frac{m}{n}}{2} である。
ここで、面積比は \frac{ac}{2} : \frac{a\frac{m}{n}c\frac{m}{n}}{2} 。

これを整理していく。

両辺に2を掛け ac : a\frac{m}{n}c\frac{m}{n} = ac : ac\frac{m^2}{n^2}
両辺をacで割り 1 : \frac{m^2}{n^2}
両辺に n^2 を掛け n^2 : m^2

よって、相似比 n : m の図形の面積比は n^2 : m^2 である。

DPに対するメモ

競プロ

問題ページ

最近JOI(日本情報オリンピック)の存在を知り、過去問を解いたりしていたのだが、おそらくDP的な考え方を使う問題を解いた。1

DPは前の値を使って次の値を計算できるか、次の値を計算するときにはその前の値がすべて計算終了していなければいけない。

例えば再帰関数は必要になれば自分自身を呼び出し前の値を計算する。
一度計算した値を保存しておき、無駄な計算を省いたメモ化再帰を用いた場合、DPとほぼ同じになる。
これはDPにおいても再帰においても、現在の値を計算するのに必要な前の値はすでに計算が終わっているからだ。

巨大な問題を解くのに、そのまま解くのではなく、再帰的な部分問題に分割し、小さなものから前の結果を利用して解いていく。

DPテーブルの添え字は状態を表しているので、
DP[状態1][状態2] = その時点での最良
としてやるといい？のかな？

  1. 解説AC↩

ABC177 感想

競プロ

コンテストリンク

ABCDの4完。

A問題
よくある算数の問題。
ただ、簡単な問題は凡ミスしやすくて苦手。

B問題
s.size()-t.size()だけ全探索しようとしてs.size()==t.size()のケースでwaを出してしまった。

C問題
普通に計算すると O(N^2)のため紙に書いてみる。
そうすると、 1 \times (2 + 3 + 4) + 2 \times(3 + 4) + 3 \times (5)となっていることに気づく。
累積和を使ってAC。

D問題
幅優先探索して友好関係のある塊を用意して、それぞれの塊にいる人同士を最大になるように合わせていく。
解説を読んで、確かに一番大きい塊のメンバー数が答えだなとなった。

反省

C問題のきれいな解法を思いつけるようになりたい。

D問題を苦労して解いたのに茶diffで少しがっかりしたが、union-findというデータ構造を使うだけだそうな。
知らなかったぞ...

E問題はコンテスト後、解説を読みあっさりACできた。
頑張ればコンテスト中に通せたのではという思いがある。

ABC133 C

競プロ

問題リンク

L, R の範囲に2019の倍数があれば答えは必ず0になる。
ということには早めに気付けた。

しかし、愚かな私は2019を倍数に含まない数列に対して、 L \times (L + 1) \mod 2019 が最適解だと思い込み、WAを重ねた。

少し考えればわかることなのに...