2010-09-02から1日間の記事一覧
keyword 位取り表記法 Java 概要 ローマ数字風なルールで書かれた数字が2つ与えられるのでその和をルールに則った形で出力する問題。 実装するだけ。これもソースを紛失してしまった。eclipseで毎回同じファイルを上書きしてるからこうなる。
keyword Greedy Java 概要 複数の問題があり、各問題が何分で解けるかが与えられる。ICPC形式のコンテストで、どの順番で解けば最もよいスコアがでるか、最良の値を求める問題。 簡単な問題から順に解けば良い。ソースは紛失したので略。
keyword シミュレーション Java 概要 アンケートの集計をしてソートする問題。 ソース略。
keyword Greedy C++ 概要 プログラミングコンテストチャレンジブックで解説がつくらしいので予習の意味を込めて挑戦。 文字列が与えられる。文字列の最初か最後を取り除いて、新しい文字列として取り除いた文字をつなげていく。辞書順で最小の新しい文字列を…
keyword 約数 文字列 C++ 概要 文字列s(strlen(s) 候補はstrlen(s)の約数だけ。またs=a^nであるかどうかの判定はO(strlen(s))でできる。 約数の個数が多いと怪しいけどとりあえず投げてみたら通った。
keyword シミュレーション C++ 概要 人々に2,3,...と番号が割り振られる。まず、番号2の人は仕事を免除され、それ以降の人は2ごとに仕事を割り振られて列から取り除かれる。次に番号3の人は…、番号5の人は…となる。仕事を免除される番号をlucky numberという…
keyword 平面幾何 平面走査法 C++ 概要 100個以下の長方形が与えられる。長方形がカバーする部分の面積を求める問題。 Y軸に平行なイベントラインをずらしていく典型的な平面走査法の問題。区間のカバーする長さを毎回求めてやる。
keyword 幾何 C++ 概要 直線から構成された図形が与えられる。合同な図形を判定する問題。直線はすべてX or Y軸に平行。 端点を原点に平行移動して回転させてやればよい。