うーむ。
問題 k 種類の切手から重複を許して h 枚選んで貼ることにより、1 ドルから順に、間をあけずに 1 ドルきざみで何ドルまでの金額を表現できるか求め、そのときの k 種類の切手の額面とあわせて出力せよ。
アルゴリズム h + k が 9 以下という制約があるので総当りで余裕…と思ったら意外と計算時間が数分もかかってしまった！しかしアルゴリズムを最適化したいがめんどくさくなった。有効な . . . Read more
1 問解くのにけっこう時間がかかってしまう。
問題 20 文字以下の文字列のペア src, dst に対して、文字の削除・挿入・変更という 3 つの操作を組み合わせて、src を dst に書き換える最小の手順を与えよ。
要は diff のアルゴリズムを作成せよということですな。
アルゴリズム 基本はバックトラック＋枝刈り＋メモ化。ひとつのペアに対して現実的な時間で解けるようにするだけなら、 . . . Read more