sndr https://blog.hatena.ne.jp/sndr/ sndrのブログ https://sndr.hatenadiary.org/ POJ 数学 文字列 問題 http://poj.org/problem?id=1989 (翻訳)K種類の整数N個からなる整数列が与えられるので、その部分列とならない整数列のうち最短のものの長さを答えろ。 解法 整数列の先頭から、K種類の整数が一通り出るところまで進み、さらにその場所からまたK種類の整数が出そろうところまで進み...を繰り返していき、繰り返した数+1が答え。適当な証明 上のアルゴリズムをn回繰り返したとする。 入力の整数列を繰り返しによって進んだところで切って、整数列の集合{s1, s2, ... ,sn}が出来る。(全てのsはそれぞれK種類の整数を全て含んでいる)まず、長さn以下の任意の整数列が{… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsndr.hatenadiary.org%2Fentry%2F20130406%2F1365227226" title="POJ 1989 The Cow Lineup - sndrのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2013-04-06 14:47:06 rich https://sndr.hatenadiary.org/entry/20130406/1365227226 1.0 100%