一週間

えーと、、いろいろあったなw

土曜日。あ、先週というべきだろうけどw
高校時代の友達に会って色々しゃべりました。
銀閣寺いったり(改修中で大変な恰好になってた)、
東大オケ見にいったり、久々やったし面白かったですw

日曜日。
練習会にちょと顔出してからダンスの練習に。
ダンスって何かって？

月曜日。
朝一にバイト行って、昼過ぎに抜ける。
学科の数名とカラオケ行って、
その後テストの学科打ち上げで。
幹事がシャアのコスプレするとかいうさすが情報学科な感じ。
○○こりん(ニックネームw)に誘われて踊って見ました。
何踊ったかって？恥ずかしいから教えませんがねw
まーオタ共の集まりだけあって素晴らしく楽しかったですw

火曜日。
いつも通りバイトの一日。

水曜日。
家族旅行で琵琶湖に向かう。
近江舞子の海水浴場で姪っ子甥っ子の相手をしたり。

木曜日。
近江舞子に泊ったので琵琶湖まわりを散策。
烏丸半島とかいうところで博物館を見たり。

金曜日。
も一回海水浴して帰ってきた。
そのままバイト行って、サクッと(？)仕事してみた。

明日からバイトが夏休みでー。。
学校もバイトもない一週間とか本当にレア過ぎて感動。
多分暇過ぎてぽけーってなっちゃうので
プログラミング頑張ろうと思いますよw

てことでさっきまで一問といてました、、
これ≫http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=26&category=26&page=show_problem&problem=2427
始めはTLE(時間切れ)だったけどメモ化とか上手く改良したら解けたのではっぴーw

お盆休み中に20問ぐらい解きたいものですねw

バスがエラーだ電車を使え

泣きたいとき

辛いとき

悲しいとき

頑張るとき

明日は学科の打ち上げ。

踊ってきますw

あ、、昨日(一昨日？)は楽しかったです、、

一緒に回ってくれた人どうもありがとう☆

ちょーと眠いので詳細はまた今度ー(書けるかな？w

テスト終わったー！！

ということで明日から夏休み。

今年は丸2ヶ月あるけど、、

いろいろ忙しいので実質1ヶ月ぐらいかな。

プログラムの練習会とかバイトとか引いたら

残りは5日もない気がしますが、、

まぁ楽しみたいと思いますよ？ひとまず。

今年の夏休みの目標はバイトに行きすぎないこと。

お金より大事なものを手にしたいものですw

テスト期間

のために更新が滞ってました。すいません。

まぁ誰に謝ってるんだっていう話なんだけど笑


ついに明日でテスト終わり。

今日も１つ受けてきた、、簡単過ぎて損した気分w

あと2個あるんだけど、、

3限のはきっと1限のテスト受けてからでも間に合うはず。

問題は1限のフーリエ変換…しんどいけどがんばるんば。

なんと

お湯がでないΣ(-o-;;;)

この暑いときに風呂入らずに寝ろと(泣

テスト

テスト期間はどう過ごすかがなかなか難しいね、、

丸1日テスト勉強しようと思っても6時間ぐらいで飽きちゃうし、、

適当にバイトも入れつつしてたら前日に焦るはめになったりw

今回はまぁテストの個数も少ないのでうまく回せてよかった、、

ってもまだ4分の1しか終わってないけどさw

さーてお風呂行ってからもうちょっと頑張るかw

眠い。

なのに寝れない。何故。

解けないー

pku1113番が解けません。

大抵こういうのってどっかの大会の問題をコピーしたものなので、

その元の大会を探して見て、サンプル入力通してみたのだけど

見事にサンプル出力と一致。んー、、どういうことなんだろうか

問題はこちら。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1113

元ネタはこちら。
http://contest.mff.cuni.cz/archive/neeu2001/

誰か暇な頭のいい人が解いてくれることを期待age(違w

トポロジカルソート

時をかける少女を見ててトポロジカルソートがふと頭をよぎった。

普段は専門用語とか解説するのだけど面倒だから略。

それでもwikipediaへのリンクを張ってあげるのが俺の優しさ(違
http://en.wikipedia.org/wiki/Topological_sorting


時をかける少女見て、、お風呂入ったんだけど、、

一応腕に数字書いてないか確認してみた。書いてなかった。残念。


かわりに見つけたのは2つの注射痕。いや、こう書くと怪しいなｗ

さっき献血行ってきたんです。成分献血ですが。やっと11回目。

最近若い人の献血率がめっちゃ下がってるらしいです。

行きたいけど１人ではちょっとー、、とか言う人は、

言ってくれたら一緒に行きますよ。。偽善ぽくてもいいじゃない。

広げよう、献血の輪。。


タイミングって大事なんですかね。いろいろ逸してそうな気がｗ

まぁ逸してようが気付かなければいいのです、、自分には分からんしｗ


んー、、もうすぐテストですね、、頑張りましょう。

To do or Not to do.

今日はレポートさくっとやって、バイトに行ってきました。

あいかわらずのテスト勉強０。昨日も一日中プログラムかいてたしなぁ…w

テストの予定はー

・来週
火曜　画像処理論(☆☆)
ーカメラで撮影したような画像から必要な情報を取り出す技術
火曜　データベース(☆☆☆)
ー大量の情報を間違いなく処理する技術
木曜　計算機アーキテクチャ(☆)
ーパソコンの仕組みを機械的な面から

・再来週
月曜　技術英語(☆☆☆？)
ー将来論文を書くに当たって知っておくべき知識
月曜　通信基礎論(☆☆☆)
ーAMやFMを始めとした電波通信技術
火曜　オペレーティングシステム(☆☆)
ーパソコンの仕組みをソフト的な面から
水曜　工業数学A3(☆☆☆☆)
ーザ・フーリエ変換
水曜　人工知能(☆☆)
ー実用的なアルゴリズムをもとめて

って感じかなー、、☆は難易度。4段階で。

さてそろそろデータベースとか勉強始めないとなー、、とか言いつつ、

明日もプログラミングの練習会をやってきますw

テスト前だし人が集まるか不安だなぁー。。笑

京都

今日のバイト帰りの電車の中は、浴衣を着た人たちでいっぱいでした。

あー、、祇園祭だねーっていう感じ。

初めて行ったときはまさかあの四条通が封鎖されてるなんて思ってもなくて。

地元にいたら道路封鎖して何かするみたいなこと滅多にないので、

ちょと面白いなぁとか思って見てました。まぁほかにもあったけどw


8月に入ったら五山送り火(いわゆる大文字)があったり、

5月にはすぐそこの神社で葵祭やってたり、

なんか面白いなぁと思ったりします。


あ、、昨日で授業終わりました。お疲れ様です。

なんか高校の同窓会あるらしいんだけど、、

この1月に集まったところじゃない？とか思ったり(笑

まぁどっちにしろ部活の同窓会があるので行けないのです、、

なんでこんな絶妙にかぶるかなぁ・・・。。

部活は規模が小さいから元部長が行かないわけには行かないのよねぇ…w

鯛茶漬け

もう半年ほど前から鯛茶漬けが食べたくて食べたくて。

でも鯛高いんだよねー、、まぁ少なくとも安くはないw

んでどーしよっかなーっていう状態が続いてたんだけど、、

ついに今日買ってきました鯛の切り身。


今ご飯が炊き上がるのを待ってるところ…

あぁ、、楽しみだ…(笑

四つ葉のクローバー

今日1日、お疲れさまでした。

何かいいことありましたか？

ほんの1つでもいいことあったなら、、

それを糧にして生きていけば楽しいよね、きっと。

明日もいいことありますよーに。

胃の中の蛙 大会を知らず

(いつものごとくタイトルと本文は関係ありませんw)


icfpって大会が今日の朝4時から丸3日間あって、、

参加する気満々で長い長い問題文を1時間もかけて読んで、

TCP使うとかいうからソケットとか調べつつ書いて、

やっと準備ができた！と思ったら、

大会に参加するために配られてるプログラムが、

我が家のパソコンではどう頑張っても動かなかった。

なんて寂しい。俺の朝の4時間を返せ(笑)



なんか最近、やたらとfirefoxやらが重い。

というかPCが全体的に重い。

昔実家で使ってた富士通のパソコンは、夏場に３Dゲームとかすると

ちょっとずつ動作が遅くなっていって、

最後には止まってしまうというすばらしいパソコンだった。。

扇風機の風をあてると復活するという熱に弱いPC…

まぁ置いてる場所も熱のこもりやすい場所だったんだけどね。


さてそろそろテストですよ、、がんばらなくちゃね、、

まずは月曜提出のフーリエ変換のレポートなわけだけど、、

これどこから手をつけたらいいんですかい？？

なんか複素積分の香りがぷんぷんするわけですが。

テストにも複素積分出るのかなぁ・・・しょぼんぬ。。

後期までの予定。

今週金曜 演習レポート締め切り(ハードウェア)・発表会
今週土曜〜来週火曜 ICFPプログラミングコンテスト(この前のICPCとは全く別物)
来週月曜 フーリエ変換レポート締切り
来週火曜 前期最終授業日。待ち遠しい。
来週水曜〜土曜 何もないのでテスト勉強
以降日付で。
 
7/20(Sun.) どっかにでかけるはず。
7/21-30 テスト週間。頑張る。
7/25 テストの最中に演習レポート締切り(ソフトウェア)

8/4(Mon.) 学科打ち上げ
8/5-7 家族旅行(未定?)
8/17-18 高校物理部OB同窓会
8/29-9/1 合宿前乗り(ってか親と石垣島旅行)
9/2-9/10 サークル夏合宿＠宮古島
9月末 どっかに旅行したい。

9月は結構何もないんだなー、、
去年みたいにバイトばっかの夏休みってのは寂しいので、
いろいろ頑張りたいと思いまする。

icpc

正式に通過者が発表されたみたい。
http://sparth.u-aizu.ac.jp/icpc2008/d_result.php

大学別に色分けしたみたいなんだけど、
なんか色の数が多すぎてよくわからない事態になってる笑

七夕

♪笹の葉 さらさら〜


花火を見に行きたいです。

いや、もちろんテスト終わってからだけど。

十三の花火とかすごいみたいですね〜

http://www.yodohanabi.com/

haskell

俺は普段C++っていう言語でプログラミングしてるのですが、
最近haskellって言語がおもしろいと聞いてここ1週間ほど勉強(本を読んでただけ)

さっきふと実際にソースを書いてみようと思って、
本も何も見ずに書いてみました。

main = putStr "Hello, World\n"

コンパイルして実行したら

Hello, World

と表示されて感動。これC++で書くと、

#include <iostream>
using namespace std;
int main(){
    cout<<"Hello, World"<<endl;
    return 0;
}

っていう長いプログラムになるのだけど、
haskellだとたった1行でいいから気持ちいいなw

誰か一緒に勉強する人を募集中ー◎

ICPC Japan Domestic

タイトルの意味はICPC日本国内予選ってことで。

ついに今日 ICPC:International College Programming Contestの

国内予選がありました。結果は…まぁ日記の続きを読んでください。

ちょと他のSNS…っていうかまぁ日本一巨大なアレに書いてたのを転載。

一応ネットで公開して変なことは書いてないと思いますが何かあったら教えてね。

んで今回は新しくURL教えた人もいるので結構ワクワクw

質問やらなんやらコメント大歓迎なんでどーぞよろしく☆

ではここから日記開始ーw


---


珍しくハイテンションです。理由はこちら。

http://icpc.tanaka.ecc.u-tokyo.ac.jp/icpc2008/common/guest_standings_en.php

ちなみにうちのチーム名はd3sxpです。

なんと7位。アジア地区予選(という名の実質国内予選)にいけるじゃないですか！

問題はこちら。今回は日本語なのでいつもよりは読みやすいはず。

http://icpc.tanaka.ecc.u-tokyo.ac.jp/icpc2008/common/guest_top_en.php
(左側のA B C D E Fってのが問題番号で、jaっての押すと日本語で出てきます)


難易度的にはー、、

A：日本語を読み間違えなければ簡単。難易度★
B：問題がとにかくややこしい。ちゃんと問題文を整理できたら、
単に素因数分解したらいい問題だと言うことが分かるはず。難易度★★
C：P,Q,Rの組み合わせが27通りしかないので全部の場合を試してみる。
アルゴリズム思いつけば後は頑張って実装するべし。難易度★★★
D：メモ化というかDPというか。グラフ理論でもとけるんじゃないだろうか。
こういう問題に"十分慣れてていれば"そんなに苦労はしない。難易度★★★
E：幾何系のライブラリが十分に用意されてるかどうか。難易度★★★★
F：俺はアルゴリズム思いつきませんでした。難易度★★★★★

まぁ国内予選らしくA問題から解いていけばいい問題セットでしたね。


ではー、、調子のって我がd3sxpがどういう風に解いたかをダイジェストw
あー、、ダイジェストなんていいから解法教えろって人は下の方まで飛ばしてねw

16:15 開始15分前。この頃が一番心臓バクバク。
演習で部屋を使ってた人たちが帰っていく。
みんなに応援を受けて頑張る気になる。

16:25 開始5分前。用意万端、チームで集合。さて頑張るか。

16:30 国内予選開始。予選参加者みんなが一斉に問題を見ようとして、
サーバーに負荷がかかってなかなか問題が見れない。我慢我慢。

16:32 まだ見れない。我慢我慢。
16:34 まだ見れない。そんなバカな!刻々と時間は過ぎて行く…汗
16:35 なんか前の机のチームが見れたらしい。うちはまだ。我慢…我慢…。

16:36 問題やっと見れたー!!! ということで俺たちの国内予選やっと開始。

コンテスト中は時計見てる余裕なんてなかったので以下時間は省略。
まずA問題に目を通す。太郎くんと花子さんが何枚かずつカードを持っていて、
そのうち何枚かを交換するらしい。で、交換した結果、太郎くんの持ってる
カードの合計と、花子さんが持ってるカードの合計を、等しくするような
交換の方法はありますか？という問題。

太郎くんも花子さんも最大100枚のカード持ってるのに、
そんなのめちゃくちゃ難しいやん！と思ってA問題を無視。
(後に実は誤読だったことが判明…まぁ詳しくは後で。)

次はB問題を見る。問題がややこしい、、とりあえず放置。
続いてC問題、D問題を見る。解けそうな気もするけどややこしいなぁ…
さらにE問題、F問題を見る。もはや解けそうな気すらしない。

んー、、簡単に解けそうな問題が1問もない。。正直焦る。
国内予選はAが一番簡単なはず、と思ってもう1回Aに戻る。

Aの問題を再読。さっきは太郎くんと花子さんが"何枚か"カードを交換する、
と読んだけど、実は"1枚だけ"交換する、なんじゃない？と思い出す。
それだったら太郎くんが100枚、花子さんが100枚持ってても
交換する方法は100*100の1万通り。余裕じゃん！って思ってプログラミング。
さらさらーと書いて(といっても実際書いてるのは別のメンバーだけど)
submit(提出)。Correct Answerってことで1問正解☆

あとから聞いたんだけどこの問題は日本語がまぎらわしくて、
"1枚だけ交換する"とも、"何枚か交換する"とも読めたんだとか。
英語の問題には"one card"って書いてあるので"1枚だけ"が正解だったらしい。

で、A問題が解けたのでB問題へ。
7で割った余りが1か6になる数、つまり1,6,8,13,15,20,22,28…ってのを
月曜土曜数と名付けるらしい。なんだそれは(笑)　で、ある月曜土曜数nを
とってきてその約数を考えたときに、その約数のなかに1とn以外の
月曜土曜数が含まれていない数を月曜土曜素数と名付けるらしい。なんだそれは(笑)
で、別のある数Xが与えられた時に、そのXを割り切ることのできる月曜土曜約数を
全て挙げなさい、という問題。まぁ1は除くとかややこしいことは置いておいて。

実際の問題はあとひとひねりぐらいヤヤコシイ文章が入ってて、
問題解こうと焦ってるこっちの頭の中は完全にカオス。
ちゃんと問題を理解したら実はただの素因数分解問題だということに気づき、
submit。 Correct Answerだと返事がかえってきて２問目正解。
実はこのころ東大のトップチームはすでに3問目を終えていたらしい。早っw

続いてC問題へ。
コンピュータの中では0と1の信号で処理されるって話をよく聞くと思うけど、
それは論理回路っていって、ANDとかORとかそういうもので構成されているのです。
で今回はそれを0と1と2の3種類にして、ANDとかORとかもちょっとややこしく
してみたけど君たちにそれが理解できるかな？みたいな問題。

見て数秒でアルゴリズム思いついたのでコーダーのカマエ君に伝える。
5秒ぐらいで適当に説明。通じなかった。10秒ぐらいかけてちゃんと説明。
んー、、伝わらないな。30秒ぐらいかけてゆっくり説明。あ、通じた(笑
俺は説明能力に乏しいようで毎回こんな無駄会話が繰り返されてますw
あ、ちなみにコーダーってのは実際にプログラムを書く人のことです。
この大会は3人チームなんだけどパソコンが1台しか与えられないのよね。
実際にプログラムを書くのはカマエが一番早いので、俺はアルゴリズム(解法)
を考えたり、コーダーのミスを指摘したりとかそんな役回りw

で、カマエがプログラムをカリカリ書いてくれる。カリカリ。カリカリ。
できたので提出してみる。Wrong Answerが返ってきた。あれ？？ 汗”
アルゴリズム間違ってないはずだしなぁ…とか思いながら2人でチェック。
問題を見てない人には分からないと思いますが-(Q*P)みたいに括弧の前に
マイナス符号がつく可能性があることをすっかり忘れてました。ごめん!!
で、それをカリカリーと直してsubmit。今度はCorrect Answerをもらって。
という訳で3問正解になりました。Wrong Answerのときは本当に焦ったけどw

で、続いてD問題をやりはじめる。西田くんっていうもう一人の子が、
事前に問題を読んでくれてて、一番解きやすいのを俺とカマエに教えてくれます。
いつもどおり問題の説明を受けて3人でちょっと考えてー…
PFS(priority fast search)というよくある方法+メモ化で解けることが判明。
カマエとプログラムを書く作業に戻ります。

D問題は、正方形のタイルがw*h個並んでいて、、ロボットがその中を動いて
左上から右下まで行きたい、という問題。ただ各タイルには"まっすぐすすめ"とか
"右へ曲がれ"とか書いてあって、その通り進むと右下のタイルまでいけない
場合があるのです。タイルに書いてある内容を無視するとその分罰金を
支払わなくてはいけないのだけど、とにかく右下のタイルに進みたい、と。
じゃぁ罰金の額を最小にするにはどういう風に右下まで行ったらいいですか？
という問題。んー、、俺の説明能力でこれちゃんと説明できてるのだろうか。
時間がある人はぜひ問題見てみてください、、上にも書いたけど
http://icpc.tanaka.ecc.u-tokyo.ac.jp/icpc2008/common/guest_top_en.php
の左の方にあるAとかBとか書いてある部分のjaをクリックすると見れますので。

で、まぁカマエとここはこうした方がいいんじゃないかーとか言いながら
調子よく書いてたのだけど、ここで問題が発生。1回罰金を払ったタイルを
もう一回通るときに、再度罰金を払う必要はないんじゃないか？という話が。
そうなると"罰金を払ったタイル"を覚えておかないといけなくなるから、
今までやってた方法では解けなくなってしまう。うー、、ここまで書いたのに！！

カマエと2人で悩むもやっぱりこの方法では解けないという結論に。
落ち込みながらとりあえずE問題にすすむ。

E問題は大玉ころがしをする問題。大玉転がしをしたいのだけど、
回りにいっぱい障害物があって、あまり大きな大玉だと障害物にぶつかってしまう。
けど見栄えとか考えるとできる限り大きな大玉を使いたい。
じゃぁ障害物一覧から大玉の最大サイズを計算してください、という問題。

幾何問題っていうんだけど、こういう平面上を何かが動く見たいな問題は
数式がいっぱい出てきて大変なのです。で、今まで全然解けていなかったのだけど、
今回は事前に数式集みたいなのをネットでみつけてたので、用意してました。
するとすると、その数式集を駆使すれば解けることが判明。
てことでカマエはひたすら数式集をコピーし始め、
俺と西田君は数式集にない式を自分で作り出す作業に入る。

で、きっかけはなんだったか忘れたけど、西田くんが突然D問題の解法について
俺にしゃべり始めてきた。俺は「あー、、その方法は無理だったよ、、だって
罰金を払ったタイルを覚えてなくちゃいけないからさ」とか返事をする。
すると西田くん、「え？何で？」ってreply。俺「だって1回罰金払ったタイルって
次にもう1回通るときは罰金払わなくていいじゃん」とか応答。
西田くん「え？もう1回通るときでも罰金払わないといけないよー？？」
俺硬直。「え？なんですと？ならさっきまで書いてた解法で解けるじゃん！！」

ということでカマエをたたき起こして(笑)D問題に戻る。9割がた完成してたので
あとはちょっと手を加えるのみ。提出してみる。Correct Answer !!

実は俺もカマエも問題ほとんど読んでないのですよ。それは悪いことではなくて、
西田くんが先に問題を読んで、上手くまとめてくれたのを聞いてるわけです。
でもそうすると今回の様に、「問題を自分で読んだ西田くん」と、
「問題を西田くんから聞いた俺とカマエ」で解釈が変わってくることが時々。
実際にプログラム買いてるのは俺とカマエであることが多いので、
間違ってプログラムを書きだすと大変な目にあってしまうことがあるわけで。
その辺今後の課題かな。2人以上で問題を読むとかしてもいいかもしれない。。
アジア大会とかで英語の問題になると読み間違えも起こりうるしねー。

って感じで4問正解したのでこれは予選突破できるのではないかとか思いつつ
E問題の大玉転がしに戻る。ちょっと気持ちにも余裕が出てきて、時間を見てみると
1時間45分経過してのあと1時間15分とかだった気がする。
数式集からコピーしたのは、高校数学頻出の「点と直線の距離」にはじまり、
「点と線分の距離」やら「線分と線分の交差判定」やら、
さらには「ベクトルの内積」やら「ベクトルの外積」やらとにかくいっぱいw
あと足りない分は自分たちで式を作って、ごりごりごりごり書きました。
各問題にはテスト用入力とその模範解答が用意されてたので、まずはそのチェック。
初めはなかなか答えが会わなかったのだけど、「大玉を転がす直線上に
障害物があったときは全然転がせないので0を返す」とか、
「ゴールのすぐ近くに障害物があるとゴールまで大玉を転がせない可能性がある」
とかいろいろやると模範解答どおりの答えが出るようになりました。
この時点で残り20分ちょっと。この問題に55分もかかったんだなぁ(汗+笑)
で、提出してみるとCorrect Answer！！なんと5問正解！！
始めて幾何の問題を時間内にとけてみんな感動。公式集の力はほんとすごい。。
そしてチーム全員で公式集をネット公開してくれている人に感謝。
ちなみにこんなページです。 http://nya3.jp/libicpc/
(プログラミングの公式集のことをライブラリと言ったりします)

で、あと20分。もしや結構上位なんじゃないかと思ってランキングを見てみると
その時点で暫定6位。おおっ、、去年16位だったのに比べればかなりの快挙w

(ちなみに去年の結果はこちら)
http://www.logos.ic.i.u-tokyo.ac.jp/icpc2007/jp/domestic/result.html


最後F問題は時間がかかるアルゴリズムしか思いつかず、、
結局ラスト20分ぐらいを無駄にはしてしまったけどよく頑張ったと思う。
その間にどっかのチームに抜かれて7位にはなってしまったけど、、
目標5位とか(無理だろうなとか思いながら)言ってたのに比べれば
本当すごい結果だと思うわ、、まぁトップ4は東大独占なわけだけど(汗)

アジア地区予選の会津地区は10月末、会津大学で行われるそうです。
(アジア地区予選はペキン地区とかマカオ地区とか10ヶ所ぐらいでありますw)
んー、、ただで会津まで旅行できるなんて素晴らしい、、頑張るよまぢで！

というわけでダイジェストは終了ー、、長いお付き合いありがとうございます。

1時間半も日記書いたの初めてだわ、、wcってコマンドで文字数測定すると
どうやら7000文字以上打ったらしい、、90分で7000文字ならそれなりじゃない？笑





で、実際に参加した人とかアルゴリズムに興味がある人向けの解法解説。

まぁあくまでうちのチームが解いた方法なので最適解かは知りませんが。。

まずA問題。
太郎君のカードを入力する際に、その合計TAROsumを計算。
花子さんの入力の際にもその合計HANAKOsumを計算。
太郎くんのカード最大100個と花子さんのカード最大100個の組み合わせは
100＊100＝10000しかないのでそのすべてに対して、
交換するとTAROsumとHANAKOsumがどう変わるかを計算。
で、この2つがイコールになるときに値を出力、なければ-1を返す。
まぁこれぐらいは(問題の読み間違えさえなければ)解けるはず。
最後まで問題の読みにくさにハマってしまったチームの人はどんまいです。

次にB問題。
まず300000以下の全ての月曜土曜素数を求めます。
方法は簡単。月曜土曜数を小さな数から順に(1,6,8,13,15…)生成して、
それより小さな月曜土曜素数全てで割ってみます(1を除く)。
どれかで割り切れたら月曜土曜素数じゃないし、それ以外は月曜土曜素数。
そうして月曜土曜素数をすべて求めたら、入力を1つずつよんで、
１つ１つ月曜土曜素数で割れるかをチェック。割れたら出力したらOK。
問題がややこしいのでどうしてこうなるのかはよく考えてみてね。
ヒントは問題文中の「月曜土曜数aが月曜土曜数bの月曜土曜約数であるためには、
aがbの普通の意味の約数であれば必要十分であると，簡単に証明できる。」
っていう一文。まぁ頑張って考えてみてください。

次にC問題。
カッコで計算の順序が定められてる問題は、スタックを使うと楽です。
まずP,Q,Rを0,0,0として次の操作をします。次に0.0.1として同じことをして、
これを計27回、最後に1,1,1として次の操作をして、結果が2になった回数が答え。
PとかQとか考えるの面倒だったので以下のように入力データを直接改竄。
string inputstr=(入力)
for(int p=0;p<2;p++){
for(int q=0;q<2;q++){
for(int r=0;r<2;r++){
string tmp=inputstr;
replace(tmp.begin(),tmp.end(),"P",(char)p+'0');
replace(tmp.begin(),tmp.end(),"Q",(char)q+'0');
replace(tmp.begin(),tmp.end(),"R",(char)r+'0');

int ret=何か処理();
if(ret==2)answer++;
}}}
まぁこんな感じでPとかQとかを初めに隠蔽してしまうと後が楽になります。
で、準備としてminus、number、opっていう3つのスタックを用意して、
変数numOfNotを0で初期化しとく。ちなみにnumOfNotは直前のnot記号の数ね。
後は前から1文字ずつよんでいくたびに、その文字が
'0'か'1'か'2'だったら、変数numOfNotをチェックして、
偶数なら0か1か2をそのまま、奇数ならそれをnotした値をnumberにpush。
'('だったら変数numOfNotをminusにpush。
これは'('の前にあったnotの数を表す。
'+'か'*'だったらそれをopにpush。
')'だったらnumberから2つpopした値を、
opからpopした演算子('+'か'*')で処理して、
さらにそれをminusからpopした値の数だけnotした値をnumberにpush。
'-'だったら変数numOfNotを1インクリメント。そうでなかったら0にする。
ということをします。ちょとややこしいので注意が必要ですが。
まぁnot演算子を無視して言うと、閉じ括弧がくるまで今の状態をひたすらpush。
閉じ括弧が来たときに計算するべき値は、直前とその前に決まった値(number)で、
どういう演算をするべきかというと直前の演算子(op)だから、という感じかな。
なんかどう説明したらいいのか分からんのでコメントなり何なりで質問どうぞw

んー、、Cの説明が上手くできなかったのだけど気にせずDの解説へ。
この問題は各タイルについて、どの方向から来たかが分かれば
次にどの方向に行くのにどれだけコストがかかるか、が分かります。
例えば左から来たときに、そのタイルが「直進しろ」タイルであったとして、
そのまま右に進むには罰金は0。向きを変えて下に進むには右折する必要があるので
右折分の罰金を払えばいいことがわかります。だから、
「今のタイルのx座標」「今のタイルのy座標」「来た方向」の３つを記憶して、
「これまでにかかったコスト」の小さい順のものからどんどん次のタイルに進めて
いってやります。これは「これまでにかかったコスト」順のPFSに相当します。
で、あと重要なのが、「一旦(X,Y)のタイルに向きZ(例えば左)から来たら、
以降同じ(X,Y)のタイルに同じ向きZから来ることはない」ということ。
だってコスト順にPFSしてるのだから、以前ここに来たということはその時は
今のコストと同じか、それより小さいコストできたはず。わざわざ大きなコストで
同じことする必要ないよねー、って感じいうことで。
これを使うと状態数が(Xのサイズ)*(Yのサイズ)*(向き)となって、
つまり最大で30*30*4、計算するとたった3600通りで表せます。
だいたい今のコンピュータは(プログラムにもよるけど)1秒で1000万ぐらいの状態を
処理できるので3600通りなんてほんと一瞬なわけで。そんな感じで実装しました。

Eはごりごり頑張って、という感じだなぁ、、サンプル入力が親切なので、
サンプル入力で通らないものをチェックしていけば条件を忘れることはないはず。
あとは幾何ライブラリを駆使することとバグを埋めないようにがんばることかな。

Fは去年京大から世界大会に行った先輩に教えてもらったのだけど
今ひとつ理解できてないのでまた理解できて暇だったらそのうち。



あー、、日記を2時間15分も書いてたようです。
普段は20分ぐらい書いたら飽きるんだから、
アジア大会行けるのがよほどしかったんだろうなぁ＞俺

まぁ他の大学で国内予選出た人とかにも見てもらえたらいいなーと思いつつ
この1万1000文字にもおよぶ日記を終わりにしたいと思います。

てかmixi1万1000文字も書けるのか!?


最後に。いつも書いてますがこの長ったらしい文章を読んでくれて、、
なんかいろいろ応援してくれて、、ほんとありがとうっ

合宿終わりましたー

結構楽しかったので良かったです、、あんましゃべってなかった1回生ともしゃべれたし。

うちのサークル3回生で引退なんよねー、、合宿で潜るのもあと13本。少なすぎるー。。(泣




ttp://jp.youtube.com/watch?v=PQiPm7n7Uv8
(リンククリック出来るようにしてたけど勝手に再生されるので消しました)

とあるサイトで紹介してたから見たけど18秒じゃ間に合わん気がする(笑)

そしてこれ百貨店のCMらしいんだけど百貨店との共通点がいまいち(w

本日のバグ。

printf("％d\n"-4*value);
気づくのに数十分かかりましたよw

世界がグーグルになったら

Googleに染まる世界 http://news-walker.net/2008/06/22212620.html

これおもしろすぎるw

ちなみに元ネタはここらしい http://www.snurfy.com/if-google-ruled-the-world/


一番笑ったのはマクドの看板に "over 99 billlion sold" って書いてあったこと。

googleはこういうの風にデカさをアピールすることが多いよねー、、

"メールボックスは6000MBもあります!"みたいな感じでさw
(参考：http://mail.google.com)


んー、、今日もあんま充実してなかったなぁ…笑”

お詫び。

昨日ぐらいの日記に今週の金曜日が国内予選って書きましたが、、

この週末でなくて来週の週末の間違いでした(汗

この土日は新歓合宿ということで串本に潜りに行ってきます、、

どうやら天気がよくないとかなんとかでちょと心配だなぁ・・・


久々にprojectEulerを1問解きました。
http://projecteuler.net/index.php?section=problems&id=98

RACEとかCAREみたいな文字列が数千個与えられて、

その中でアナグラム(文字の入れ替えで別の単語になる)ものを

探してくるのが第一段階。さらにその各文字に0-9の数字を当てはめていく。

例えば上の例だとCに1、Aに2、Rに9、Eに6をあてはめると、

CARE=1296、RACE=9216となる。

んで実はこの2つはどちらも平方数(ある自然数の2乗した数)に

なっているんだけど(1296=36*36, 9216=96*96)、

そういうものの中で一番大きい数(この辺の詳細な定義は問題文をw)を

出してくださいとか言う問題。第2段階がちょっとてこずったけど、、

Accept(正解)もらえたときは結構すっきりしました☆



で、、第一段階のアナグラムぐらいだったら国内予選にも出そうなので、

ちょと勉強になるかなーって感じで書いてみる。といっても一瞬で終わるけど。

ある文字列A、Bが与えられたときに、それらがアナグラムか判定する

アルゴリズム(ピタゴラスイッチではなくw)を考えてくださいw

とりあえず単純で記述量が短いものを考えてみてね。答えはちょっと下に。
















正解は、文字列Aと文字列Bをソートして、その2つを直接比較する、というもの。

C++だったら

string strA,strB;
cin>>strA>>strB;
sort(strA.begin(),strA.end());
sort(strB.begin(),strB.end());
if(strA==strB)cout<<"アナグラムじゃん!"<<endl;

とまぁ上2行の入力部分を除くと3行で判定できちゃうという。

覚えておいて損はないのではないでしょうか？？

ちなみに計算量についていうと、

文字列A、Bの長さをnとしたときに、

ソートはnlognでできるので、O(nlogn)の時間で判定できます。


じゃぁ、O(n)ではできないのか考えてみましょう。

(と言うかほんとに今考えたw) O(n)でも可能ですね。

プログラムは長くなりますがソートしなければいいのです。


例えば文字列A、Bには小文字しか入らないというのであれば、

文字列に含まれる各アルファベットの数を数えたら良いですね。

コードはこちら。コンパイルしてないから間違ってるかもだけどw

string strA,strB;
cin>>strA>>strB;
int cntA[256],cntB[256];
for(int i=0;i<strA.length();i++)cntA[ strA[i] ]++;
for(int i=0;i<strB.length();i++)cntB[ strB[i] ]++;
int same=1;
for(int i=0;i<256;i++){
    if(cntA[i]!=cntB[i]){
       same=0;
       break;
    }
}
if(same)cout<<"アナグラムじゃん!"<<endl;

まぁこんな感じになると思います。

計算量はO(strA,strBの長さ+アルファベット数)になるので、

文字列の長さが短くてアルファベット数が多いときは、

ソートした方が事実上早くなるなんてこともありえます。


んー、、たまにはタメになるコンテンツも書かないとな、

と思って書いてみましたがどうでしょうかね、、

感想があったら(というかなくても)何かコメントよろしく!(笑



あ、、上では省略してしまいましたが、

strAとstrBの長さが違うときはアナグラムにはなりえません。

その場合はすぐにbreakするなり何なりして、処理を減らしましょう◎

努力

知り合いに、音大に通ってる人がいるのですが、、

なんか学祭のオケに入れたとかいうメールが来ました。

学祭のオケとか学校でかなり上位じゃないと入れんのだろうし、、すごいなw

まぁそいつは昔からすっっっごい努力家なんできっと実を結んだのだと思います。

日付的には空いてるのでそいつの勇姿をみてこようと思います、、まだまだ先だけどねw



ICPCに奮起しだしたのが去年の12月末。23日ぐらいだったっけな？

調べてみるとそれからといた問題が、pkuで60問、uvaで40問、projectEulerで80問。

projectEulerは簡単なのが多いので1/3として30問ってことにすると、

6ヶ月で130問といたことになります。うわ、、予想外に少ないなこれは。。

毎週練習会もしてるし気持ち的には1日1問は行ってると思っていたのだけど。。

国内予選はこの金曜日、、ちょっとでもがんばらねばw


あ、今日は5km走って来ました◎