1問も解けなかった.
Easy
最初は,一番大きい四角形からどちらかの辺を減らしていく,っていうのにしていたけどだめだった. Editorialの通りに,
- 片方の辺について全て調べる
- 塗ることのできる面積 / その時の辺の長さ or もう片方の辺の長さ のうち小さい方をとって面積を計算する
って感じで全部調べるといけた.
Medium
Editorial の通りに単純に全部調べていてはPythonでは間に合わなかった. Python で解いている人は2人いて,
- abc = d を a*b = d/c にする
- a*b をkey,bのindexのlistをvalueにした辞書を作る
- dをcで割り切れる場合について,その時のcのindexが整列済みのbのlistのどの部分に挿入できるかを考え,条件を満たすものの個数を数える
って感じだった. 最後のcの挿入位置を探す部分も2分探索しないと間に合わなかった.
collections.defaultdictとbisectを学んだ.