新しいUVaサイトがよく落ちるね。広告を入れるのはしょうがないが、もう少しセンスがあっていいじゃないかな。無駄なスペースを取りすぎ、とくに垂直方向。肝心な問題文をスクロールしてみるという有様。IEもfirefoxも開けない。なんとかしてほしいよ。

今日から使えたGoogle CromeはSafariと同様、ちゃんとアクセスできてよかった。

#11281番の問題はよく勘違いされるようで、自分も最初では間違っていた。やはりちゃんと図形を描いてみることだね。

1. 問題文
丸い円をいくつも与えられて、さらに様々な形の三角形が与えられている。円に入る三角形を教えろ、というのが問題の意味。実際の問題では、円の代わりに孔を使ったり、三角形の代わりに立体の三角プリズムを使っているが。

2. 考え方
三角形の外接円の半径を求め、円の半径と比較すれば簡単に問題が解けそうに思われるが、大きな落とし穴が待ち構えている。

たとえば、下の三角形をよくみてみよう。ブルーの円は外接円だけど、赤の円よりは明らかに半径が大きい。つまり、鈍角三角形に対しては、その最長辺が最小円の直径になる。外接円では全然大きい。鋭角三角形に対しては、外接円が最小円になるけど。

p11281.jpg

上のことを理解すれば、問題は簡単に解けるはず。

問題意識は UVa #11480 Jimmy's Balls による。

つまり、自然数Nを3つの自然数 x, y, z に分割する時の分割数(組合せ数)。ただし、x < y < z。自然数とは1以上の整数のこと。

たとえば、N=10に対して、(x, y, z)は、(1,2,7), (1,3,6), (1,4,5), (2,3,5) の4通りしか選べないので、分割数は4になる。

p11480.png

割とよく遭遇しそうな問題だが、一般解は以下の数式で表される。

  分割数 f = 3p(p-1)+1  if m = 0

      = 3p(p-1)+mp  if m > 0

ただし、p=N/6 (6で割った時の商)、m=N%6(6で割った時の余り)。

いくつかの検証データ(N,f)を書いておく。

 (5,0) (6,1) (7,1) (8,2) (9,3) (10,4) (11,5) (12,7) (13,8) (14,10) (15,12) (100,784) (500,20584)

一般化して、Nをn個に分割する時の数式ってあるのだろうか。

1. 問題
高速性が要求される問題のひとつ。N (3<=N<=5000) 個の入力データから、任意の3つ (x, y, z) を選んで、x+y=z となるTripleの数を求めよ。
なお、入力データはすべて正の整数、32ビット範囲内に収まる。プログラムの実行制限時間が8秒。

2. 実例
次の入力データをみてみる。
1 2 3 4 5 6

1+2=3, 1+3=4, 1+4=5, 1+5=6, 2+3=5, 2+4=6 になるので、答えは6になる。

3. 計算法
入力データの個数が5000までなので、一見簡単に解けそうだが、やってみて、大変さが分かった。出題者の意図は O(n^2) アルゴリズムの提出にある。

自分の順位は現時点では18位なので、まだまだ改善するところを考えないといけないが、つぎのような方法でやってきた。

入力したデータに対し、ソートを行い、グループ化を行う。グループ化というのは、同じ値の入力データをまとめることだ。たとえば、1 1 1 2 2 3 3 という入力データを (1,3) (2,2) (3,2) にクループ化する。ソートにはO(nlogn)、グループ化には O(n) で済むが、ソートの高速化は問題として残っている。

次に、ソートされ、グループ化されたデータに対し、Tripleの数を算出する。

言葉で説明するのが面倒なので、ソースプログラムを使う。勿論分かりやすくするため、一部を書き換えているし、もっと高速化できるところもある。この部分の実行時間はO(n^2)。なお、ans変数は64ビット整数(long long int)でないとオーバーフローになってしまう。

typedef long long llong;
#define SIZE  5000
int N;
unsigned data[SIZE+5];  /* 入力データ(ソート済み) */
int freq[SIZE+5];  /* 同じ値を持つ入力データの個数 */
ans = 0;
if (N == 1) { puts("0"); exit(1); }
for (k = 1; k < N; k++) {
    i = 0; j = k-1;
    while (i < j) {
        if (data[i]+data[i] == data[k]) {
            ans += (llong)freq[i]*(freq[i]-1)/2*freq[k];
            break;
        }
        if (data[j]+data[j] == data[k]) {
            ans += (llong)freq[j]*(freq[j]-1)/2*freq[k];
            break;
        }
        if (data[i]+data[j] == data[k]) {
            ans += ((llong)freq[i])*freq[j]*freq[k];
            i++, j--;
        } else if (data[i]+data[j] &lt; data[k]) i++;
        else j--;
    }
}
printf("140733424702768\n", ans);

4. スピードの改善
スピードを上げるために、データのソートとグループ化に、2分探索木を使ってみた。順位は14に上がったが、劇的な改善にまだ繋がっていない。最後のtriple数の計算がボトルネックになっているから。

2分検索(バイナリサーチ)のような手法が使えるのではないか、そんな気がしている。ランク1位の時間は0.540秒なので、自分としてはせめて1秒を切りたい。

元問題

余計なことは書かない。一生懸命導いた数式の結果だけをメモしておく。

p11250.jpg

あとは、入力データのm, nに対し、それぞれ多倍長整数(本ブログ参照)を使って、上記の通り、分子、分母に分けて計算し、最後に、ユークリッド互除法で分子、分母を約分し、結果を得る。

数式のネット検索は、Googleといえども、まともにできない。入力の仕方にも、使う変数の文字にも、可変要素が多すぎるかな。

ソースプログラムAを書いて、それをコンパイルして実行可能なプログラムBができあがる。プログラムBを実行したら、画面上の表示内容がAそのものになっている。

そういうソースプログラムAを自己印刷プログラムという。英語ではQuineという。

自己印刷プログラムはふつう、入力を使わない。入力ファイルを画面表示するだけなら簡単に作れるから。

C言語で作られている自己印刷プログラムに以下のようなもの2つがよく知られている。

 

以下のものは多少長いが、いろいろ応用利きそう。

自分自身を表示する。哲学的な要素が含まれ、なかなか奥深い。

1974年度のチューリング賞を受賞したクヌースの受賞講演「芸術としてのプログラミング」にも、

 数年前、Stanford大学の学生たちは、自分自身を印刷する最短のFORTRANプログラムを見つけようとはりきったこともあります。

とわざわざ紹介してある。

平方数とは平方根が整数の数のことだ。小さい順で並べていくと、0, 1, 4, 9, 16, 25, 36, ... となる。あるいは、素因数分解して、すべての素因数の指数が偶数である場合も平方数になる。たとえば、36 = 22x32、素因数の指数がそれぞれ2であるので、36は平方数といえる。平方根を計算することは結構時間がかかるので、素因数が分かるのであれば、素因数の指数を調べるほうがはるかに高速。

1. 問題
 n (0<n<=200000) 個の整数(絶対値は1018よりも小さいが、すべての素因数は30以下。)が与えられた時に、n個の中から任意の2つを選んで、その積が平方数となる(組合せの)数Xを、n個の中から任意の3つを選んで、その積が平方数となる(組合せの)数Yを求め。

2. 実例
 例をもって説明する。
 たとえば、3つの整数 2, -2, 2 が与えられた時、2x2 = 4 になるので、X = 1。また明らかに Y = 0。
 簡単だな、と思うかもしれないが、データの個数が20万、個々のデータの値の大きさを考えると、そう容易く解けないはずだ。しかも、実行時間は3秒に制限されている。
 20万個のデータすべてをここに書き出すことは非現実的だが、20万個のデータが何百組も与えられても、3秒以内に計算を終了させ、正解を出すプログラムを作ることが簡単ではない。すべては高速性にかかってくる。

下は多少複雑な例。それでもデータの個数は100でしかない。

答えは、X=4950 Y=161700。

3. 計算法
 まず、1~2500000の間の、素因数が30以下のすべての値に対し、エラトステネスのふるいを応用して、素因数分解をしておく。2500000を超えた入力値に対しては、単純に1つ1つ素因数分解をしておく。
 ただ、本問題では素因数の指数の奇偶性が問題になるので、個々の素因数に対応して、以下のビットパターンを採用する。

 最下位ビットから bitpat[11] = { マイナス, 2の数&1, 3の個数&1, 5の個数&1, 7の個数&1, 11の個数&1, 13の個数&1, 17の個数&1, 19の個数&1, 23の個数&1, 29の個数&1 };

 「マイナス」はデータが負数を表すビット、
 「2の数&1」は素因数2の指数が奇数なら1、偶数なら0になる。
 「3の数&1」は素因数3の指数が奇数なら1、偶数なら0になる。
などを意味する。

 例えば、6のビットパターンは110、-6のビットパターンは111、10のビットパターンは1010、平方数のビットパターンは0。

 データの積を取ることは、すなわち、ビットパターンの XOR 計算にほかならない。そのXORの結果がゼロになれば平方数、ゼロ以外であれば非平方数となる。

 また、入力データを値がゼロのものとそうでないものに分ける。値がゼロのデータの数がzだとすると、XとYに相当する部分は以下のように算出する。

  X = nC2 - n-zC2 = z(2n-1-z)/2
  Y = nC3 - n-zC3

あとは、値がゼロ以外のデータについてのみ、XとYの値を算出し、上の値に足し加えておけばOK。

4. 結果
 書くのは嫌になるほど、多くのことをトライして、最終的に実行時間を0.480秒に押さえ、現時点でのランク1位にできた。

細かいことは省略するが、ヒントになるものをリストアップしておく。

  1. 入力の値に対するビットパターンは2047以下。つまり、異なる入力データの数は2048通りしかない。
  2. XOR計算 a^b = 0 となるa, bは、a = bに限る。a^b^c = 0となるa, b, cは a^b = c に限る。従って、異なる2048個の値から、任意の2つを取り出してXORがゼロになる計算は2048回(O(n))で済むし、任意の3つを取り出してXORがゼロになる計算は2048x2048回(O(n2))で済む。
  3. 入力データを平方数と非平方数に分けた。平方数同士では、XORがゼロになる。平方数と非平方数とのXORはゼロにならない。非平方数と非平方数とのXORがゼロになるのは、その2つの非平方数が等しい場合に限る。
  4. 入力データの処理にscanf()ではなく、read()関数を使った。getchar()を使ってランク2にできたが、1位になるには、read()を使ってしまった。
  5. 計算のオーバーフローに気をつけよう。整数同士の積に64ビット整数を使おう。

5. ソースの一部

typedef long long llong;
typedef unsigned short ushot
#define MAX    2500000
ushot bitpat[MAX+5];
ushot pp[10] = { 2,3,5,7,11,13,17,19,23,29 };
/* 1~MAXまでの各整数に対するビットパターン */
void sieve(void)
{
    register int i, j;
    int k, p;
    ushot b;
    for (k = 0; k < 10; k++) {
        p = pp[k], b = 1 << (k+1);
        for (j = p; j <= MAX; j *= p) {
            for (i = j; i <= MAX; i += j) {
                if (bitpat[i] & b) bitpat[i] &= ~b;
                else               bitpat[i] |= b;
            }
        }
    }
}
/* MAXを超えた値に対するビットパターン */
ushot factor(llong n)
{
    int k, p, m;
    ushot ans;
    ans = 0;
    if (!(n & 1)) {
        m = 0;
        do n >>= 1, m++;
        while (!(n & 1));
        if (m & 1) ans |= 2;
    }
    for (k = 1; n > 1 && k < 10; k++) {
        p = pp[k];
        if (!(n  0x7fff0dc99530)) {
            m = 0;
            do { m++; n /= p; }
            while (n  0x7fff0dc99530 == 0);
            if (m & 1) ans |= 1 << (k+1);
        }
    }
    return ans;
}

XとYを算出する部分(分かりやすくするため、ソースの一部を書き直した。ソースそのものとは異なる)。なお、freq[a]はビットパターンがaである入力データの個数を示す。

X = Y = 0;
for (i = 1; i < 2048; i++) {
    if (freq[i]) {
        X += ((llong)freq[i]*(freq[i]-1))/2;
        for (j = i+1; j < 2048; j++) {
            if (freq[j]) {
                if ((i^j) > j && freq[i^j]) Y += (llong)freq[i]*freq[j]*freq[i^j];
            }
        }
    }
}

1. 問題

p11200.jpg

上記の通り、各セルには必ず、右下あるいは左下斜めの壁が置かれる。迷路の入口は上、出口は下。左右両側は通行禁止。こういう条件の下で、入口から出口までの異なる通路は果たして何本あるか。ちなみに、右上の迷路では通路が3本、左下の迷路では通路が1本という結果になっている。

2. 入力データの例
 上記の左下迷路に対応する入力データは以下の通り。大きくなると、目視での確認は相当きつい。¥は本来はバックスラッシュ\、右下斜めを表しているはずなのに。

3. 計算法

p11200-2.jpg

セル(r,c)に位置することは、そのセルの下の端の中央にいることと考える。そうすると、周りの壁の形によって、上記の8通りの進み方がある。

証明はまだしていないが、入口1箇所に対応する出口は高々1箇所。従って、1つの入口に入って探索していき、出口ひとつに出くわしたら、それ以降の探索は打ち切り、つぎの入口から探索し続ける、という戦略を取って問題なさそう。また、異なる入口から入り、最終的に同じ出口にいく通路もないと推測する。

1. 問題
 様々なサイズの長方形(または正方形)の紙Aが与えられている。1枚の紙Aを、折り紙するための4枚の正方形Bに切り分けたいけど、もっとも大きな折り紙Bが得られるような、最適なAがどれかを選べ。

2. 実例
 以下の実例を見てみる。

1枚目の紙10x20では最大5x5の折り紙しか得られない。2枚目の紙40x8では最大8x8の折り紙が得られる。3枚目の紙12x12では最大6x6の折り紙しか得られない。ということで、2枚目の紙を選べば、最大サイズの折り紙を手にすることができるわけだ。

3. 計算法
 縦幅に比べ、横幅の短くない長方形(または正方形。そうでなければ90°回転すればOK)に対して、最大サイズの折り紙(正方形、同一サイズ)4枚は3通りの並び方にしかならない。

p11207.jpg

長方形の縦幅サイズをY、横幅サイズをXとすると、3パターンによって得られる折り紙の最大サイズはそれぞれ、

 パターン1: X/4 と Y の小さいほうの値
 パターン2: X/2 と Y/2 の小さいほうの値
 パターン3: X/3 と Y/2 の小さいほうの値

になる。3パターンに対応する3つのサイズから、最大サイズを得、それが長方形 X, Y に対して入手できる折り紙の最大サイズになる。

さらに、与えられたすべての紙の中から、最大サイズのものをピックアップすれば、答えが得られる。

ということで、本問題は簡単に解ける。残りは実行時間の短縮ということだ。

自分の書いたプログラムは最初0.020秒だったけど、最適化を施し、最終的に0.000秒に到達した。つまり、乗算、除算しないで、ビットシフトでの計算を心がけた。

例えば、元のサイズX, Y を最初から12倍すれば、2, 3, 4で割り切れるので、実数ではなく、整数だけで計算可能になる。

となると、3つのパターンはそれぞれ

 パターン1: min(3X, 12Y)
 パターン2: min(6X, 6Y)
 パターン3: min(4X, 6Y)

に変わり、ビットシフトの性質を考えて、

 3X = (X << 1) + X  4X = X << 2  6X = 3X << 1
 3Y = (Y << 1) + Y  12Y = 3Y << 2

などと工夫すれば、除算も乗算も必要なくなる。

まあ、そんなテクニックは実行スピードの本質的な改善に繋がらないから、分からなくても構わないが、少しでも他人よりもランクを上げたい気持ちがあれば、覚えて損することはないだろう。

2以上の整数nについて、その素因数の和sf(n)の計算法を考える。

例えば、2 = 2 なので、sf(2) = 2。
6 = 2*3 なので、sf(6) = 2+3 = 5。
8 = 2*2*2 なので、sf(8) = 2+2+2 = 6。

2から30までの整数についての sf(n)の値は以下の通り。
2,3,4,5,5,7,6,6,7,11,7,13,9,8,8,17,8,19,9,10,13,23,9,10,15,9,11,29,10.

計算できる最大値 MAX は適宜変えること。ROOT_MAXはMAXの平方根。関数の実行が終了した時点で、配列sf に2以上、MAXまでの素因数の和が格納される。

1. 問題
 使えるカセットテープの長さ(録音時間)と、録音したい曲のリストが与えられ、すべての曲が入るだけの、最も短いカセットテープを探せ。

2. 実例
 実例を見たほうが分かりやすい。

出力結果を見てみよう。

3. 考え方
 詳しいことは問題文に述べてないので、常識的に考えて問題を解いてみた。
 一番録音時間の長いカセットテープは120分だと思う。それはA面+B面での録音時間。片面ではその半分しか録音できない。また、曲の数は最大30とした。

本問題にBFS(幅優先探索)を使った。

構造体
 typedef struct {
  char no; /* 曲の通し番号 */
  char side; /* A面かB面か */
  int a, b; /* A面とB面の録音時間 */
  int prev; /* 前へのポインタ */
 } QUE;
と定義し、1曲目はA面録音として、2曲目以降はA面に、またはB面に録音するように探索キューを展開していく。

つまり、n曲目においては、検索キューに存在しているn-1曲目までの組合せすべてに対し、次の操作を経て、再びキューに入れる。

すべての曲の探索キューを作成した後、短いテープの順に、A面もB面も録音時間に収まるものが探索キューにあるかどうかを調べる。

4. 感想
 DPによる方法も考えてみたが、配列はとてつもなく大きいので断念した。今回のBFS探索法は強引的な面もあったが、実行時間がゼロ秒になっているので、本問題に使えることは間違いなさそう。