プログラミング言語Cやその他で書いたもの。関連するハードウェアやコンテスト等の情報も。admin新しいUVaサイトがよく落ちるね。広告を入れるのはしょうがないが、もう少しセンスがあっていいじゃないかな。無駄なスペースを取りすぎ、とくに垂直方向。肝心な問題文をスクロールしてみるという有様。IEもfirefoxも開けない。なんとかしてほしいよ。CromeはSafariと同様、ちゃんとアクセスできてよかった。#11281番の問題はよく勘違いされるようで、自分も最初では間違っていた。図形を描いてみることだね。丸い円をいくつも与えられて、さらに様々な形の三角形が与えられている。円に入る三角形を教えろ、というのが問題の意味。実際の問題では、円の代わりに孔を使ったり、三角形の代わりに立体の三角プリズムを使っているが。三角形の外接円の半径を求め、円の半径と比較すれば簡単に問題が解けそうに思われるが、大きな落とし穴が待ち構えている。下の三角形をよくみてみよう。ブルーの円は外接円だけど、赤の円よりは明らかに半径が大きい。鈍角三角形に対しては、その最長辺が最小円の直径になる。外接円では全然大きい。鋭角三角形に対しては、外接円が最小円になるけど。上のことを理解すれば、問題は簡単に解けるはず。分割する時の分割数(組合せ数)。自然数とは1以上の整数のこと。4通りしか選べないので、分割数は4になる。遭遇しそうな問題だが、一般解は以下の数式で表される。(6で割った時の商)、m=N%6(6で割った時の余り)。いくつかの検証データ(N,f)を書いておく。(500,20584)一般化して、Nをn個に分割する時の数式ってあるのだろうか。高速性が要求される問題のひとつ。なるTripleの数を求めよ。入力データはすべて正の整数、32ビット範囲内に収まる。プログラムの実行制限時間が8秒。次の入力データをみてみる。なるので、答えは6になる。入力データの個数が5000までなので、一見簡単に解けそうだが、やってみて、大変さが分かった。アルゴリズムの提出にある。自分の順位は現時点では18位なので、まだまだ改善するところを考えないといけないが、つぎのような方法でやってきた。入力したデータに対し、ソートを行い、グループ化を行う。グループ化というのは、同じ値の入力データをまとめることだ。済むが、ソートの高速化は問題として残っている。次に、ソートされ、グループ化されたデータに対し、Tripleの数を算出する。言葉で説明するのが面倒なので、ソースプログラムを使う。分かりやすくするため、一部を書き換えているし、もっと高速化できるところもある。この部分の実行時間はO(n^2)。int)でないとオーバーフローになってしまう。スピードの改善スピードを上げるために、データのソートとグループ化に、2分探索木を使ってみた。順位は14に上がったが、劇的な改善にまだ繋がっていない。最後のtriple数の計算がボトルネックになっているから。2分検索(バイナリサーチ)のような手法が使えるのではないか、そんな気がしている。ランク1位の時間は0.540秒なので、自分としてはせめて1秒を切りたい。余計なことは書かない。一生懸命導いた数式の結果だけをメモしておく。nに対し、それぞれ多倍長整数(本ブログ参照)を使って、上記の通り、分子、分母に分けて計算し、最後に、ユークリッド互除法で分子、分母を約分し、結果を得る。数式のネット検索は、Googleといえども、まともにできない。入力の仕方にも、使う変数の文字にも、可変要素が多すぎるかな。adminソースプログラムAを書いて、それをコンパイルして実行可能なプログラムBができあがる。プログラムBを実行したら、画面上の表示内容がAそのものになっている。いうソースプログラムAを自己印刷プログラムという。英語ではQuineという。自己印刷プログラムはふつう、入力を使わない。入力ファイルを画面表示するだけなら簡単に作れるから。C言語で作られている自己印刷プログラムに以下のようなもの2つがよく知られている。";main(){printf(f,34,f,34,10);}以下のものは多少長いが、いろいろ応用利きそう。}}自分自身を表示する。哲学的な要素が含まれ、なかなか奥深い。数年前、Stanford大学の学生たちは、自分自身を印刷する最短のFORTRANプログラムを見つけようとはりきったこともあります。admin平方数とは平方根が整数の数のことだ。素因数分解して、すべての素因数の指数が偶数である場合も平方数になる。22x32、素因数の指数がそれぞれ2であるので、36は平方数といえる。平方根を計算することは結構時間がかかるので、素因数が分かるのであれば、素因数の指数を調べるほうがはるかに高速。個の整数(絶対値は1018よりも小さいが、すべての素因数は30以下。)が与えられた時に、n個の中から任意の2つを選んで、その積が平方数となる(組合せの)数Xを、n個の中から任意の3つを選んで、その積が平方数となる(組合せの)数Yを求め。