金魚亭日常

読書,ガジェット,競技プログラミング

TopCoder SRM 671 Div 2

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を学んだ.