2009-03-25から1日間の記事一覧
1と0からのみなるNの倍数を答えよ、という問題。 先頭の文字は必ず1なので、それを基準に考える。次の桁がAならば余りは10倍してA足したものをNで割った余りになる。(これは高々N個の状態からなるオートマトンで書ける。)余りが0になるまでの遷移をBFSして、…
N!が何桁の数であるか答えよ、という問題。Nは10M程度まで。 クエリが複数個くるので、取り敢えずメモをしておく。桁数はlogで求めることができる。(というかそういう定義になっているはず。)intで10M個持つことはできるが、10M回logを呼ぶとTLEするので、あ…
閉路のない有向グラフが与えられる。すべてのノードは最初は印がついていない状態とする。任意のノードを開始点として印をつける。印をつけたノードから隣接する印のついていないノードへの移動が可能で、そのノードには印がつく。すべてのノードに印をつけ…
モチベーションが出なくて、楽な道に逃げたつもりが、さらに面倒なコーディングという結果に。 250 先頭が0にならないように与えられた数字の任意の異なる二桁をスワップするという操作をK回やってできる整数のうち、最大のものを答えよ、という問題。 高々7…