動画版Wikipedia、Qwikiがホット！

今回はWebサービスの紹介をしよう。

動画版Wikipedia、Qwikiの紹介だ。

Wikipediaは確かに膨大な情報量を持っているものの、文字が多く、煩雑になりがちである。
もともと知りたいものの概要をざっと知るために使っている人も多いはずだが、ものによってはしっかりと読み込まないとわからないものもある。
そんな人のため(?)にあるのがQwikiである。

実際に動画を見ていただいた方がわかりやすいだろう。

ナポレオン
http://www.qwiki.com/q/#!/Napoleon_I

アインシュタイン
http://www.qwiki.com/q/#!/Albert_Einstein

自由の女神
http://www.qwiki.com/q/#!/Statue_of_Liberty

Facebook
http://www.qwiki.com/q/#!/Facebook

いかがだろう。ざっと見るには十分だし、時間も長過ぎない。
開始間もないが中々のトピック量がある。
が、ちょっと検索してみたが、日本のトピックは、あったとしても情報量が少ないようだ。
残念ながら、今のところ個人が項目を追加、編集することは不可能だが、項目の編集については、「こんな情報がありますよ〜」と提案することは可能なようだ。
提案するには、項目のページに行き、「improve this qwiki」ボタンを押して行う。
文章、画像のほか、youtubeにある関係した動画を推薦することでもできる。

個人的にはかなり良いサービスだと感じている。
これからに期待したい。

Codeforces Beta Round #57 (Div. 2)

今回も今回とて最悪な結果ではありましたが、糞コード生産、及び問題を全然解けなかったという生き恥を晒すために今日もBlogを書く。

問題１

与えられた2つのビット列について排他的論理和を求める問題。
ビット列の最大長が100であるため、long longを使用してもあふれてしまう。
素直にストリングを使い、評価していった。

コード

#include
#include
#include
#include
#include

using namespace std;
#define REP(X, Y) for(long long int i = X;i < Y;i++)
#define rep(X) REP(0, X)
void main(){
string str1;
string str2;
string *result = new string;
getline(cin, str1);
getline(cin, str2);
rep(str1.length()){
*result += (str1.at(i) != str2.at(i))? "1":"0";
}
cout << *result << endl;

}

問題2

3つのベース文字列と、それに続く幾つかの文字列が与えられる。
ベース文字列には英字とsignと呼ばれる３つの記号 "-", ";", "_"が含まれているが、signは無視してよい。
続く文字列が、ベース文字列を結合したものであれば、ACCと出力し、結合したものでなければWAと出力する。

文字列系はC++で使い慣れていなかったため、PHPを使い出力した。実は問題を勘違いしており、コンテスト中に提出出来なかったのだが、終了してから完成させた。

考え方としては、ベース文字列からsignを全て取り去り純粋な文字列にした後、全て大文字に変換。
検査文字列も同じようにsignを取り去り大文字にした後、随時ベース文字列を検索し、半角スペースで置換。
最後に半角スペースも取り去り、検査文字列が空になっていなければWAを出力、空であればACCを出力。
この方法だと、ベース文字列Bがベース文字列Aを部分的に含んでいるとWrong Answerが出る。
答え見てもいいけど悔しいのでもうちょっと頑張る。
素直にベース文字列と検査対象文字列をsign抜き取り、大文字か小文字に合わせた上で3!通り試せばよいということだった。
ナイー＾ヴな実装が一番良いようだ。



問題3は解けず。4,5はまだ見てない。
精進だな。。。

CodeForces Unknown Language Round #1で何を学んだか

CodeForces Unknown Language Round #1 では、超マイナー言語Active Tclで、非常に簡単な問題を解いた。

個人的な感想だが、Active Tclはああいうアルゴリズムコンテストには全くの不向きで、これによってC++を使う際にも応用できるTipsを得たとか、そういう話では決して無い。
今回学んだことは恐らくコーディング上のスキルではなくて、限られた時間内で、手探り状態で進まなければならない場合の所作だと思った。

基本はググって解説を見つけて引っ張り出し、試行錯誤しながらサブミットしていくというものではあったが、それでも、開始30分後には、全然知らない言語を使って、簡単にではあるが入力、演算、出力するところまでは出来ていた。

これから時代が進むにつれ新しい言語は次々と開発されていくのだから、文法が今までのそれとは全く違う新しい言語を習得していくことは重要だろうし、多分、自分が全く知らなかった言語で仕事をするということも出て来るんだと思う。
そういう時に、如何に効率よく、分かりやすく、そして素早く、コードを書けるか、ということの練習にはなったと思う。

スパゲッティを量産しておいて偉そうなことを言うなと言われそうだが。
それでも、出場して悪くは無かったと思いたい。

CodeForces Unknown Language Round #1

出場してきました。CodeForces Unknown Language Round #1
言語が分からず、マイナーな言語が使われるとのことだったので、何かなと妄想しつつ待っていると、「Active Tcl」とかいうわけの分からん言語が登場した。

これ、実は開始5分前にアナウンスがあって、標準入力ストリームからどうやって拾ってくるか、どうやって変数に値をセットするか、どうやって出力するかというサンプルコードが挙がってたんだけども、僕はそんなことに一切気付かず、グーグル先生を頼ってひたすらリファレンスを探し回って徒にタイムロスを重ねていた。

笑

今回は言語自体が難しいということで、問題がクソ簡単だった。

!!!---Warning---!!!

下記は糞コードです。参考にしないで下さい。

問　１
指定された数字の階乗を求めよ。

コード

gets stdin number
set sum $number
for {set i 1} {$i < $number} {incr i} { set sum [expr $sum*$i] } puts stdout $number flush

特筆すべき点なし

問 2
5-4とか4-9みたいな文字列がインプットされるので、式を評価せよ
各数字は0以上9以下という縛り
演算子は+か-のみ。

コード

gets stdin number
scan $number "%d%c%d" n f m
if {$f == 42} {
    set result [expr $n + $m]
} else {
    set result [expr $n - $m]
}
puts stdin $result
flush

問 3
n行m列のテーブルがあり、行の左から右へ、上から下へ、1,2,3、、、と数字が書き込まれている。
例えば、3行4列のテーブルの場合、1行目は 1、2、3、4。2行目は5,6,7,8と書き込まれる。
今、1 <= k <= nmとなるkが与えられる。 kは、列を上から下へ、左から右へと遷移していった場合のk番目のセルを指し示している。 k番目のセルに書き込まれた数字を出力せよ。 コード

gets stdin number
scan $number "%d %d %d" n f m
set gyo [expr $m % $n]
set kara [expr $m / $n]
if {$gyo == 0} {
    set gyou [expr $n - 1]
} else {
    set gyou [expr $gyo - 1]
    set kara [expr $kara + 1]
}
set mae [expr $gyou * $f]
set sum [expr $mae + $kara]
puts stdout $sum
flush stdout

解き方
Kを行数+1で割った余りが何行目かを表し、商+1が何列目かを表す。
n行m列目の数値を算出するには　{ (n-1) * 行数 } + m とすればよい。

問 4
3人姉妹にプレゼントを上げなければならない。
長女には一番高いものを、次女には次に高いものを、三女には一番安いものをあげたい。
３つの数字が与えられ、それぞれ商品の値段を示している。どの商品を姉妹のいずれにあげればよいのか、「1 3 2」のような形式で示せ。

gets stdin number
scan $number "%d %d %d" n f m
if { $n > $f } {
if {$n > $m} {
if {$f > $m} {
set l 1
set me 2
set s 3
} else {
set l 1
set me 3
set s 2
}
} else {
set l 2
set me 3
set s 1
}
} else {
if {$n > $m} {
set l 2
set me 1
set s 3
} else {
if {$f > $m} {
set l 3
set me 1
set s 2
} else {
set l 3
set me 2
set s 1
}
}
}
set kekka [format {%d %d %d} $l $me $s]
puts stdout $kekka
flush stdout

もうちょっと綺麗なコードにも出来たが、問題が単純なのでナイーヴに進めた。
Active Tclはささいなスペースにも厳しいので、うっかり変なことをして怒られないか怖かったというのもある。

問 5
与えられた数字に一番近い素数を、数字より大きいものと小さいものを一つずつ、「小 大」のような形式で示せ。

解き方
エラトステネスの篩で終了。

コードは書いたのだが、配列に入れた数値にアクセスする方法が今一つ分からず、時間切れ。


ということで、4問解いて終了でした。
始めのロスが無ければもうちょっといけたかもしれませんが、後の祭り。
上でも述べた通り、検索しても簡単にリファレンスが見つからないような超マイナーな言語とあってか、問題は非常に簡単でした。
C++を使っていれば、解くのに一時間もかからなかったでしょう。(今回のコンテストは二時間半あった)

とはいえ、未知の言語を使って手探り状態でプログラムを組むというのも中々面白いもの。
次回があるのかどうかは分からないけれども、機会があれば参加してみるのもいいかもしれませんね。

Codeforces Beta Round #56

初参加してきました。CodeForces
。。。なんですが。

開始後
コンテストページどこ？
というところで詰まる。

お約束ですね。

では本題へ。今回は問題Aしか見ていないため、Aのみ書く。

問題A

ルームメイトが、主人公のシリアルを、N個の箱のいずれかに隠してしまった。
箱は左から順に0.1.2.3、、、という順番に並んでおり、シリアルの場所についてヒントが与えられる。
ヒントは"To the left of i"或いは"To the right of i"という文面。
要するに、「シリアルは i 番目より左の箱にある。」或いは「シリアルは i 番目より右の箱にある」というヒント。
このヒントを元に、シリアルが入っている可能性のある箱を絞り、最終的に幾つ残っているかを出力する。
ヒントは矛盾している場合があり、箱が残らない場合がある。その場合は-1を出力する。

解き方

Start, End で範囲を指定。その中に幾つの箱が存在しているのかを算出する。

コード

#include
#include
#include

using namespace std;

#define REP(X, Y) for(int i = X;i < Y;i++)
#define rep(X) REP(0, X)

void main(int argc, char* argv[]){
string str[4];
int number_of_box, number_of_hints, start, end;
int number;

while( cin >> number_of_box >> number_of_hints){
start = 0;
end = number_of_box + 1;
rep(number_of_hints){
cin >> str[0] >> str[1] >> str[2] >> str[3] >> number;
if(str[2] == "right"){
start = max(start, number);
}else{
end = min(end,number);

}
}
if( (end - start) < 2)
{
cout << -1 << endl;
}else{
cout << (end - start - 1) << endl;
}

}

}