2006/08/20 Sun.
「情報オリンピック日本委員会」とかいうものの存在を知っている人はどれだけいるでしょうか。いわゆるIT版オリンピック。
つい最近に開催されたらしい「第18回国際情報オリンピック」というので、日本の高校生が優秀な成績を残したとか。
上記の委員会は、この国際大会に日本代表選手を派遣する事業を軸にしているらしのだが、先日まで存在知らなかったぞ。
選抜試験もあるらしく、過去問が公開されていたので覗いてみた。うーむ、これは激しく難しいな。例題その1でもコピペ。
三角形の形は辺の長さで決まる。
順番に3つの正整数が与えられたとき、辺の長さがそれらの値と一致する三角形が存在するかどうかを調べ、
存在するなら鋭角三角形、直角三角形、鈍角三角形のいずれかを判定し、次の入力へ進む。
三角形が存在しないとき、それまでに入力された三角形、直角三角形、鋭角三角形、鈍角三角形の個数を
空白で区切って出力し、それ以降の入力は無視して終了する。
入力の中には必ず三角形が存在しないようなものがあると仮定してよい。
入力の行数は判らないが各行には3つの正整数が空白で区切って書かれている。ただし、各整数は100以下とする。入力ファイルの改行コードはCR+LFである。また、出力ファイルにおいては出力の最後の行にも改行コードを入れること。
| 3 | 4 | 5 |
| 2 | 1 | 2 |
| 6 | 3 | 4 |
| 1 | 1 | 1 |
| 1 | 2 | 3 |
| 4 | 1 | 2 | 1 |
| 3 | 4 | 5 |
| 2 | 1 | 2 |
| 6 | 3 | 4 |
| 1 | 2 | 3 |
| 1 | 1 | 1 |
| 3 | 1 | 1 | 1 |
三角形がどうこうという以前に、この問題文の日本語の意味が理解できない自分には、もはや成す術は欠片もありません。
ってか、直角三角形、鋭角三角形、鈍角三角形って何？いや、直角三角形くらいはわかるけど、残りの2つって何ですか。
一応解説も付いていたけど、読んでも自分には意味不明。やはりプログラマには数学の知識も求められるのだろうか。
ページの横幅とかの都合上、微妙に編集しちゃってますけど、意味を捻じ曲げるような書き方はしていないので。
三角形の3辺の長さがa, b, c の時、a + b > c, c + a > b, b + c > aが成り立つ。
また、正の数a, b, cがこの3不等式を満たせば、これらを辺の長さとする三角形が存在する。
cがa, b, cの最大値の時、c + a > b, b + c > aは明らかだから、a + b > cが成り立つかを調べれば十分。
よって、三角形が存在するかを判定は、入力された3つの数の最大値を求め、それと他の2数の和とを比較すればよい。
最大値のほうが真に小さいとき三角形が存在する。
ここまでの解説は着いていける範囲。要するに、3辺の長さが提示されていて、それで三角形が作れるかどうかってことね。
3辺の長さがa, b, cの三角形が存在する時、a <= c, b <= cとする。
長さa, bの辺に対する角が鋭角であることは明らかである。
さらにcの2乗 < aの2乗 + bの2乗の時、cに対する角は鋭角、
さらにcの2乗 = aの2乗 + bの2乗の時、cに対する角は直角、
さらにcの2乗 > aの2乗 + bの2乗の時、cに対する角は鈍角である。
これはアレですか、ピタゴラスの定理ってヤツですか？「3:4:5」の三角形の場合、「3の2乗 + 4の2乗 = 5の2乗」ってアレか。
プログラムでは直角三角形、鋭角三角形、鈍角三角形を数えるカウンタを用意する。
入力された3つの数a, b, cの最大値がcになるように値を交換する。
a + b <= cならカウンタの値を出力しプログラムを終了する。
そうでなければaの2乗 + bの2乗 - cの符号により、対応するカウンタに1を加える。
俺は今この場で誓う。三角形を扱うプログラムは一切書かねえからな！どう見ても俺にはCADプログラミングは無理そうです。
2006/08/21 Mon.
「第5回日本情報オリンピック 模擬試験1」の「問題1」の「入力2」をPerlで解いてみる。ってか、言語指定されていないし。
全部が意味不明じゃ、この業界のカースト制度の最下層を這いずり回って生きてる自分の有りもしないプライドが許しません。
use strict;
# 入力を設定
my $input =
"4 25 26\n" . "87 79 87\n" . "8 17 15\n" . "55 49 83\n" . "10 95 86\n" .
"10 95 86\n" . "80 18 82\n" . "40 41 9\n" . "94 13 82\n" . "34 30 16\n" .
"15 46 27\n" . "62 34 88\n" . "81 56 58\n" . "35 37 61\n" . "58 56 68\n" .
"33 56 65\n" . "35 71 51\n" . "6 76 93\n" . "27 26 25\n" . "63 36 42\n";
# 改行で分割
my @input_array = split (/\n/, $input);
my @array;
foreach (@input_array) {
# 半角スペースで分割
my @temp_input_array = split (/[\x20]/, $_);
# 配列へのリファレンスを設定
push (@array, \@temp_input_array);
}
# 成立した三角形の総数
my $total_count = 0;
# 成立した直角三角形の個数
my $flg0_count = 0;
# 成立した鋭角三角形の個数
my $flg1_count = 0;
# 成立した鈍角三角形の個数
my $flg2_count = 0;
foreach (@array) {
# デリファレンスしてソートした配列から3辺の長さを取得
# ソートしてあるため、$var3は常に最大値
my ($var1, $var2, $var3) = sort {$a <=> $b} (@{$_});
# $var3が最大値である場合、「$var1 + $var3 > $var2」「$var2 + $var3 > $var1」なので、
# 「$var1 + $var2 > $var3」が成り立つかをチェック
# if (($var1 + $var2) > $var3 && ($var1 + $var3) > $var2 && ($var2 + $var3) > $var1) {
if ($var1 + $var2 > $var3) {
# 総数をインクリメント
$total_count++;
# 判定内容によって三角形の種類を算出する
# 鋭角 : cの2乗 < aの2乗 + bの2乗
# 直角 : cの2乗 = aの2乗 + bの2乗
# 鈍角 : cの2乗 > aの2乗 + bの2乗
if (($var3 ** 2) < (($var1 ** 2) + ($var2 ** 2))) {
# 鋭角三角形
$flg1_count++;
} elsif (($var3 ** 2) == (($var1 ** 2) + ($var2 ** 2))) {
# 直角三角形
$flg0_count++;
} elsif (($var3 ** 2) > (($var1 ** 2) + ($var2 ** 2))) {
# 鈍角三角形
$flg2_count++;
}
} else {
# 三角形の条件を満たさないものがあれば終了する
last;
}
}
# 結果の標準出力
print "$total_count $flg0_count $flg1_count $flg2_count\n";
C:\>perl test.pl 10 4 1 5
なるほど、何となく意味わかった気がする。問題文で「出力はファイル」とか言われてるけど、そこは省略ってことで。
入力もグダグダな書き方になったけど、どういう入力を仮定すりゃいいかわからんから、とりあえずソースにベタ書き。
もう今日はこれが書けたから満足だ。はぁ？仕事？いいですか皆さん、仕事よりも大事なことは山ほどあるのです。
なお、上記の問題文の理解とコーディングに際して、「gadult」より以下のヘルプメール（原文ママ）を頂いた。ご協力感謝。
鋭角三角形は三角全部90°未満、鋭角～は一角90°より大きい。要は鋭角→直角→鈍角。
二等辺三角形は名前のとおり、二つの辺しか等しくない。三つ等しいと正三角形になる。
あと、累乗＝べき乗だけど累乗のが目じゃー。
変換が適当なのは、自分と「gadult」のメールのやり取りではいつものこと。累乗ってべき乗と同じだったのねー。
2006/08/22 Tue.
「第5回日本情報オリンピック 模擬試験1」の「問題2」の「入力5」をPerlで解いてみる。これは俺でもわかるな。
use strict;
# 結果格納要配列
my (@arr1, @arr2, @arr3, @arr4, @arr5);
# 入力の変数を宣言、割り切れる数（公約数）を配列に設定
my $var1 = 1849232;
for (my $cnt = 1; $cnt < $var1; $cnt++) {
if ($var1 % $cnt == 0) {
push (@arr1, $cnt);
}
}
my $var2 = 1265264;
for (my $cnt = 1; $cnt < $var2; $cnt++) {
if ($var2 % $cnt == 0) {
push (@arr2, $cnt);
}
}
my $var3 = 2238544;
for (my $cnt = 1; $cnt < $var3; $cnt++) {
if ($var3 % $cnt == 0) {
push (@arr3, $cnt);
}
}
# 重複データのみ取得
@arr4 = &get_same_value (\@arr1, \@arr2);
@arr5 = &get_same_value (\@arr3, \@arr4);
# 結果を標準出力
print join ("\n", @arr5);
# 重複データ取得サブルーチン
sub get_same_value {
my $one = shift;
my $another = shift;
my %temp = ();
@temp{@{$one}} = ();
return grep { exists $temp{$_} } @{$another};
}
C:\>perl test.pl 1 2 4 7 8 11 14 16 22 28 44 56 77 79 88 112 154 158 176 308 316 553 616 632 869 1106 1232 1264 1738 2212 3476 4424 6083 6952 8848 12166 13904 24332 48664 97328
まずは指定された各値の公約数を取得。それをそれぞれ配列に設定して、重複データのみを取得すれば解決ってワケだな。
配列Aをハッシュのキーに設定して、配列Bの値がハッシュのキーとして存在すれば、その値を返すサブルーチンがポイント。
これが方法としてはスマートかどうかわからないけど、とりあえずこれで正解通りの値は取得できた。解説を読んでみる。
どうやら「最も単純な方法」というやり方においては、自分の解法は合致しているらしい。工夫するとこうなるらしいが。
- 1から「最小値の平方根」までのループを作り、最小値が割り切れるか否かをテストする。
- 割り切れた場合、そのときの「除数」と「商」を約数リストに記録する。
- 約数をすべて求め終わったら、そのリストをソートして昇順（小さい順）に並べ替える。
- 昇順に並んだ約数リストの各値がその他の入力データを割り切るか否かを順にテストする。
- すべて割り切れた場合、公約数として出力する。
知らん！そんなやり方は知らん！複雑で速いロジックよりも、速度は微妙だけど単純なロジックの方が俺は好きなんです！
ちなみに、仕様書を書いていて頭が疲れた時にやってみた。頭の体操になると思ったが、何も考えない方が疲れ取れるな。
2006/08/23 Wed.
出社直後から即DRとか無理。記述が怪しい部分とかは巧妙に飛ばしてみたけど、後になって突っ込まれないことを祈るのみ。
2006/08/24 Thu.
2006/08/25 Fri.
とりあえず昨日で試験環境へのリリースが終了。試験に激しく手間取ったが、無理やり全ケースを網羅。疲れた。
本番環境への適用は明後日の日曜日の午前10時から。今月は前半がヒマっぽかった割には後半が激務だったな。
シャレにならないレベルの次期開発の開発項目をまとめておきたいと思ったが、今日一日はやる気無しで過ごすことに。
「Simple Scheduler」を少々改造して再アップ。カレンダー画面周辺の修正のみ。自分でも頻繁に使ってて地味に役立つ。
それにしても、この「Simple Scheduler」で使ってる「ツェラーの公式」、こんなの考え出した人はどういう思考回路してるんだ。
# ツェラーの公式
sub get_weekday {
# 局所変数を宣言
my ($year, $month, $day) = @_;
# 月が3未満である場合
if ($month < 3) {
# 月に12を加算
$month += 12;
# 年をデクリメント
$year--;
}
# 返却値を設定（0～6が返り、日曜日から土曜日に対応する）
return
($year + int ($year / 4) - int ($year / 100) + int ($year / 400) +
int ((13 * $month + 8) / 5) + $day) % 7;
}
もう少し色々と使い勝手のいいスケジューラにできないものかと考えてみたけど、どんな機能がありゃ便利なんだろう。
sendmailが使えるサーバーだったら、予定時刻の一定時間前になったら携帯にメールを送るとかってやれるんだけどな。
機能追加するとしたら、ファイルアップロードとかか？予定に関連する資料を上げておけば、何かと便利になるかもしれん。
「Tacky's Room」というCGI配布サイトに「アン帳」なるスケジューラがある。一ヶ月分の予定を全表示か、いいかもしれない。
「Microsoft Outlook」とかのように、カレンダーを数ヶ月分まとめて表示するのも、予定を扱いやすくなるかもしれないな。
気まぐれに「Simple Schedulerで検索」してみたら、同名のスクリプトがあった。レイアウトがアレだが、使いやすそうだ。
さっさと切り上げて、立川のビックカメラへ。定時で帰ろうとしてMP3プレイヤーを聴こうとしたら、右側から音が聞こえん。
断線したっぽいので、新しいイヤホンを買う必要がある。適当に見て780円の「VR102SV」という型のイヤホンを購入。
コードの巻き取りができるってのは良さそうだと思ったんだが、プラグ側のギリギリまで巻き取ることができなかった。
音は悪くなかったんだが、巻き取り部がプラグ側まで寄せられないことで、中途半端な位置に垂れ下がって重いっての。
やはり巻き取りとかは考慮しないで、自分で巻くなり何なりする普通のイヤホンの方が良かったかな。安物買いの銭失い。
2006/08/26 Sat.
午前中に起きてやるべき事を済ませ、昨夜にS保から誘われていたボウリングと飲みに行くことに。新宿に16時集合。
40分遅れて着き、K岡に場所をメールで聞きつつ、コマ劇横のミラノボウルへ向かう。この時はまだ携帯の異変に気づかない。
5階17番レーンへ向かうと、K岡とS保と後輩のS貝が。3フレームほど投げてて、俺の順は全部飛ばしてやっていたらしい。
とりあえず3フレーム分を投げてから一息つく。結局1ゲーム目のスコアは150、悪くはないけど良いって言えるほどではない。
そこそこ久しぶりなボウリングであるせいか、この辺で右肩に筋肉痛が。S保に付き合って14ポンドとか投げるんじゃなかった。
2ゲーム目は145で終了。とりあえず2ゲームでの平均が140ちょいを上回っていれば、今までの総平均スコアも上がります。
ちなみに、今まで雑記で書いているボウリングのスコアは、酒が入っている時のスコアは一切含めていません。いないはず。
普通なら飲み終わった後にボウリングってパターンだし、平均スコアを算出するのはかなり久しぶりな気がするな。
2004年1月1日から記録に残してあるゲーム数は35ゲーム、平均スコアは144.00となった。前回集計時より+0.21ポイント。
さすがに平均150を超えるのは苦しそうだな。とりあえずは目の前の目標ってことで、平均145を突破することを狙いますか。
で、18時半くらいから「凛火 総本店」にて飲み会。本店ってこんなトコにあったのね。渋谷の店舗しか知らんけどさ。
ボウリングのメンバーから後輩のS貝が抜けて、そこに7人くらい追加。急な飲み会の割にはかなり集まったな。
やはり「凛火」だけあって、和食の質は高レベル。炊き込みご飯に関してはかなりの絶品。また食いに行きたいぞ。
そこで2時間半ほど時間を過ごして、二次会はカラオケ組と飲み直し組とで別行動ってことに。自分は後者を選択。
怪しげなものを取り扱う通販系の会社に勤務するY崎氏の案内で、コマ劇の近くの「小江戸」という店に移動。
メンバーは自分とK岡とY崎氏とN村。なかなか濃いメンバーですが、飲み屋についてのしょっぱなのトークがさらに濃い。
あまりにも濃すぎるために、ここに詳細を記述すると自分の人格までもが疑われそうになるので、細かい話は無しにしとこう。
簡単に言っておくと、Y崎氏が勤務する会社の業界に身を投じると、やはり多少なりともアレ系の知識は増えてしまうってこと。
ここで23時ちょい過ぎまで飲んで（自分はほとんど飲まなかったけど）食って（つまみ系が美味かったな）解散って流れに。
やっぱり休日は金を使ってでも遊びに行かないと、家でゴロゴロしてるだけじゃストレスも発散できやしませんな。