問題 Editorial 問題 lucky numberとは、それを10進数で表記したときに4と7しか現れない正整数である。 整数nが与えられる。nを複数のlucky numberの総和で表す。lucky numberの数を最小化したい。そのような解のうち、辞書順最小のlucky numberの列を求めよ…

問題 Editorial 問題 単語列wordsが与えられる。それらを全て含む、長さ最小の文字列の辞書順最小を求めよ 1 1 解答 まず、他の文字列に含まれている関係にある文字列たちを除去する。 この除去された文字列は他の文字列に含まれるので、考えなくても問題の…

問題 Editorial 問題 辞書dictが与えられる。 この辞書dictに含まれる単語を使ってしりとりをする。 ただし、同じ単語を複数使っても良い。 しりとりをして文字列を作ることが出来る。例えば"abc"と"cd"と"efgh"でしりとりすると"abcdefgh"という文字列にな…

問題 Editorial 問題 「この文の中にxつのy(数字)が出てくる、またzつのw(数字)が出てくる」というような文であって、 文の中に現れるすべての数字に対して言及していて、 真であるような文を"self-catalogue"と言う。 数字はx,zの部分とy,wの部分が数えられ…

問題 Editorial 問題 アーティストの名前とその人の曲の数artistsがいくつか与えられる。 各アーティストがその人の曲の数だけ出てくるリストであって、 let d v = sum. map (maybe 0 succ. uncurry elemIndex). zip v. tail. tails$ v と定義されるd(x)を最…

問題 Editorial 問題 (凸とは限らない)単純多角形の三角形分割を、辞書順最小でしろ。 引かれた対角線と多角形は、始点・終点以外で交差や触れてはならない 解答 まず、適当に対角線をひいても、三角形分割ができなくなることはない。つまり単純な辞書順gree…

問題 Editorial 問題 数列xs(1 このとき、(\ys xs-> sum. zipWith (*) ys xs)が0より大きく、かつ最小となるような数列を求めたい。 これを辞書順最小で返せ。ただし、要素の大きさは、絶対値が小さい方が小さく、絶対値が同じなら正の数のほうが小さいとす…

問題 Editorial 問題 クラスが複数個ある( 「クラス複数個中からxつ以上のクラスを取る必要がある」という要求が複数( 全ての要求を満たしたい。 ただし、クラスは一つの要求にしか使うことができない。 また、既にとっているクラスが複数個与えられて、それ…

問題 長さnの文字列sに対して length [() | i s!!j] を文字列sのinversion数とする。 int n, int minInv, string minStr が与えられた時、 長さnの文字列で (take n ['a'..])の順列であって 辞書順でminStr以上で inversion数がminInv以上である ような辞書…