Cyber Bird

夏休みも終わり、新学期に入ったなあ。
友達を罠にハメようと画策した末、見事に自分が返り討を喰らって…
級長になりました(笑)

2学期の級長って面倒なんだよな。体育祭あったり文化祭あったりで…。
ま、高校時代の楽しい思い出づくりと思えば。

---

今日はパソコン甲子園2日前なので、もう大詰め(?)です。
そういえば、パソコン甲子園はてっきり去年同様、午前だと思っていたのに、
見事に13:30～だったので、午後に予定していた広島県科学オリンピックセミナーは
出られなくなりました。やったー

本日の問題はこちら。
パソコン甲子園2007年予選の第8問です。ちなみに18点だったか。

それでは続きからどうぞ。

3日ぶりの更新。部活で演奏会のリハーサルや本番で忙しかったですが、
無事成功しました。

パソコン甲子園昨年の過去問「迷子の双子」です。
問題文・入力例等は、AOJにあるので下のURLからどうぞ。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0223

また、パソコン甲子園公式から過去問とその解説をPDFで見ることもできます。

http://web-ext.u-aizu.ac.jp/pc-concours/2011/03/03_kakomon.html

では、続きからどうぞ。

こちらが俗に言われる「アリ本」こと「プログラミングコンテストチャレンジブック」です。
9/3(土)にパソコン甲子園に出場するのですが…2週間でこの本の初級部分の内容を
身につけて挑むという無謀チャレンジ中です＾＾；



昨年の10月頃に刊行されたようで、プログラミングコンテストで出題される問題を
効率よく制限時間内に解ききるためのアルゴリズムを解説し、問題と解説を載せた
良書です。内容が新しく、主にTopCoderやGoogle Code Jamの問題を取り扱っているようです。
よかったら、みなさんも是非どうぞ。

---

それでは今回解いた問題です。これからもこんな形式でソースを載せることが
あるのではと思います。

01ナップサック問題その2
重さと価値がそれぞれw[i],v[i]であるようなn個の品物があります。これらの品物から、重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めなさい。

　※制約
　・1≦n≦100
　・1≦w[i]≦10^7
　・1≦v[i]≦100
　・1≦W≦10^9

＜入力例＞
4 5 // 4...n(品物の数)、5...W(最大の重さ)
2 3 // 1番目の品物のw,v
1 2 // 2番目の品物のw,v
3 4 // 3番目の品物のw,v
2 2 // 4番目の品物のw,v

＜出力例＞
7

※※若干問題を書き換えている箇所がありますが、問題内容自体は同じです。

ソースコード等は続きに載せる形です。

旧ブログ｢Im Laufe der Zeit｣(@FC2)を放置したまま新ブログに逃げてきました＾＾；
どうも、levelfourです。これでブログは6個目だと思われます。

最早毎度御馴染、音楽・プログラミングを趣味とする学生です。

音楽については、好きなアーティストは今のところJUJUだけど、J-popに疎く、
主にClassic&Jazzを好みます。あ、でもフュージョンが一番カッコいい。

プログラミング歴は2年2カ月程(2011/8現在)、VB→C++→C→C++と転向してきた
異端児(?)です。場合によってCを使ったりC++を使ったり。
アセンブリ(GAS)もたまに使います。実用的ではないけど。
2年以上やってきたのに腕前は上がらず。
まあ、最初の半年をVBでつぶしたのと、その後WinAPIやDirectX、Qtみたいな
ライブラリで遊んでばっかりで、まともにアルゴリズムの勉強もしなかったせいだと思われる。

ちなみに、アニメも少々。ここのところずっと忙しいので、本当に暇なときにだけ少し。
好きなキャラはフェイト(なのは)、シャルル(IS)。
マンガだったらイエロー(ポケスペ)。ポケモンはもうマンガしかわかりません。
全員金髪という金髪好き。変態と言われても否定はしない。

そんな感じで日々精進するlevelfourの足跡です。

たぶん、メインはなんか問題解いたりプログラム書いてソースうｐ、が
基本になるんじゃないかと思います。
すこしでも他人の参考になれたらなーとか思ったり思わなかったり。

これから長い間お付き合いいただければ幸いです。