Latest Entries

SRM 530 Div2  少女思考中〜Now Coding...

今日、東京では雪が降りましたね。
雪って少しの風で舞うから雨天時よりも体が濡れるんですよね。寒いし濡れるし電車は遅延するし窓閉めっぱで中は空気薄いし眠いし雪なんてクソ食らえオラーーー

嗚呼、都会にとって希少な雪を純粋に楽しむことのできていた私の童心はいったいどこへ行ってしまったのだろうか
などとさみしいことを考えキャンパス内を体を縮こまらせて歩いていたわけですが、寒すぎてそして傘の意味がない程に雪が舞い込んでくるので開き直って傘を外して体を伸ばしてみました。
その時たまたま銀杏並木の通りにいたんですけどなかなかの景色でしたね。それまで傘差して下向いて歩いてたので気づかなかったんですけど、静かな寒空の下、葉の落ちた木々がずらっと並んだ通りを雪が舞っている様子には寂しさの中にも美しさを感じました。
短絡的ですけど 厳しさを受け入れて初めて見えてくるものってのはやっぱりあるんだろうな と少し感じました。



今日の2限は授業が無かったので1限後Topcoder SRM530に参加しました。前回レートが300以上落ちてしまったのでDiv2での参加、折角なので全問ACしてDiv1に戻りたいと思っていました。
前回と同様に追記部分にコードを載せました。

250 GogoXBallsAndBinsEasy
ボールと瓶で遊ぶのが好きなGogoさんが、ナンバリングされた瓶の中に入ったボールの数を昇順に並び替えた。この時ボールは一個ずつ移動させた。並び替えた後のボールの数が与えられたとき、それに至るまでの操作の考え得る最大数を求めよ。
というような問題。深くは考えてなかったけれども、元々降順だった場合を想定すれば大丈夫そうだったのでそうした。 

500 GogoXCake
ケーキを切って食べるのが好きなGogoさんが、長方形のケーキを正方形のセルからなる型で切り取る。切り取られた後のケーキの様子から、Gogoさんが本当にその型を使ってケーキを切ったか判断せよ。
というような問題。Gogoさんがケーキを切るルールとして、型を反転・回転させてはいけないというのがあるので、単純に端っこから型の形通りケーキを復元していけば実行時間的にも大丈夫。

1000 GogoXReimuHakurai
Virtual novels(サウンドノベルのことかな?)が好きなGogoさんが、ハクライレイムが主人公のノベル『トウホウ』を「読む」。『トウホウ』にはステージ0からステージN-1までN個のステージがあり、ステージ0から始めてステージN-1までたどり着けばクリア。各ステージには選択肢が設けられおり、選ぶと別のステージに飛ぶのだ。ただし番号が大きいステージから小さいステージに飛ぶことはない。Gogoさんは出来るだけ多く『トウホウ』をクリアしたい。ただし、Gogoさんは毎プレイ、初回からそれまでに選んだことのない選択肢を最低一回は選ぶことにする。 Gogoさんはこのルールに従い最大何回クリアできるか。
というような問題。。。。
問題文読んで笑ってしまった。どうやらDiv1Mediumの方にはキリシマ マリサが登場したようですね。

典型DPっぽいけど未選択の選択肢を一回は選ぶってのがネックだなあとちょっと考え込んだ。選択肢をなるべく節約するクリアルートを繰り返し探索、列挙していけば通るんだろうなとは思ったけどどう実装すればいいか思いつかなかったのでやっぱりDPで解くことにした。制限がない場合の経路数とどう違うのか必死に考えてみたところ、あるStageから選べる選択肢が複数あった時に、そこまでたどり着く方法がいくらあったところで、2つ以上の選択肢に対してその方法を全て試すことはできない、という所に着陸した。
fig20120121.png
ということで、1回でも次のステージのまで進む方法の数を更新したら、今のステージに着く方法の数を1として扱うというコードを書いて提出。結構時間ギリギリだった。



見ると部屋内では3位。異常なまでに高速に1000を提出していた人が2人いたので少しムッとしながら、1000で制限なしの場合の答えを出力するプログラムが落ちるケースを作成。
両人とも撃墜してやりましたよ!ピチューン!!
実はChallengeに成功したのは今回が初めてだったのでテンション上がりました。


高ぶる気持ちを抑えきれずに声高らかに歌い始めました。Summaryを見てみると1000の提出が異常に多かったのですが、制限を無視した解答しか見当たらなかったので私は「ハッハー!お前らアホか――!?」と叫んで踊りだしました。机の上に頭をつけて逆さになり何回転も何回転もしました。テンションの上がり方はとどまることを知らず、まさに青天井でした。終わったら割とすぐに3限目が始まろうとしていたので私はいい気分でスキップ踏んで実験棟に移り、口笛を吹きながら実験を進めていきました。フフン 電子励起♪フフン♪


実験が終わってすぐに結果を確認してみると1000は落ちていました

方針が間違っていたのかなあと思いつつミスったサンプルを見るとStage0とStageN-1が繋がっていないケースで0でない値を返していた。どうやら、値を1にするという作業が裏目に出て、到達しえないステージに到達する方法が1通り存在するように扱ってしまったようで、そこを修正してやると今度こそうまくいったようです。



今回Div1に復帰することはできたのですが、今回Mediumを通すのが遅かったのでDiv1Easyの提出が一向に早くなっていないようです。なんとかしたいですね。また、自分のレベル的に問題を解きまくることを考えたときにDiv2Hardが丁度いいようだと感じたので暫くこっちで練習していずれはDiv1Mediumを提出できるようになりたいです。
でもDiv1Hardも解かなきゃね。

ところでSummary上で確認されていた1000の提出はSystemTestで全滅していました。ずらっと並ぶFaild System Testの赤い文字からは寂しさの中にも美しさを感じました。

続きを読む

SRM 529 Div1  恐怖マークミス

久しぶりに更新しました。お久しぶりです。
本当はもっと多い頻度でこのブログを使っていけるといいんだけど、どうもいいコンテンツがないのと、一度書き始めるとなんだかんだ長い時間かけてしまうので億劫だったのとですっかり放置してしまいました。
ブログが有効活用できる人は素晴らしいですよね。
私なんかTwitterも使い道が良くわかりません。



Topcoder SRM529に参加しました。3日ほど前のことですが。
こういう感じの記事を書くのは初めてですね。後、今回ソースコードを載せるにあたってSyntaxHighlighterを導入しました。いぇい。
あ、ソースコードは長いので追記の方に載せます。SyntaxHighlighterの設定をいじればどうにかなる気もしますが。

250 KingSort
王様の名前が与えられるから、それらを辞書順に並べよ ただし例えば "Louis XIII" は "Louis XIV"の前に来るように、名前が同じ場合は世代順に並べよ
というような問題。
うひゃー、面倒くさそうーと思いつつ、そして使い方のあやふやなstring.substr()についてググりつつコーディング。スペースの前後で区切って、後ろのローマ数字部分はintに直して、自前の構造体に入れてソートさせた。

これ色々血迷った結果30分ぐらいかかった気が。。。。

そして、Challengeで落とされました。。。IXの存在を忘れてたってのもあるけどなんか他にバグある気がする。ていうか全体的に私がグダグダすぎましたね。ってか構造体定義する必要もなくpair<string,int>で事足りたし。色々と反省の多い問題でした。

600 MinskyMystery
バッグが5つある。最初に全てのバッグを空にして、bag0にN個おはじきをいれた後以下の作業を行う。
Add a marble into bag 1.
    Repeat forever:
        Add a marble into bag 1.
        Empty bag 4.
        While there are marbles in bag 0:
            While there are marbles both in bag 0 and in bag 1:
                Remove a marble from bag 0.
                Remove a marble from bag 1.
                Add a marble into bag 2.
                Add a marble into bag 3.
            End While
            Add a marble into bag 4.
            If bags 0 and 1 are both empty:
                Move all marbles from bag 3 to bag 4.
                TERMINATE THE GAME
            End If
            Move all marbles from bag 3 to bag 1.
        End While
        Move all marbles from bag 2 to bag 0.
    End Repeat
この作業が終わった時、何回おはじきを追加or箱間移動したか。
というような問題。

この意味あんのかよく分からんアルゴリズムに従って手を動かす感じ、センター試験を想起させましたね。時期も時期でしたし。あれ本番に「数値計算とコンピュータ」選んだはいいけど解答欄間違ってたんだよなあぁぁぁ


とりあえず7〜11行目をbag0->bag2、bag1->bag3の移動と考えて、じーっと上記のアルゴリズムを眺めていたら
・bag0はbag2としかやりとりしてない
・bag1はbag1としかやりとりしてない
・bag4が他のbagと絡むのは一番最後だけ
・End Repeatの時点でbag0のおはじきはN個にもどっている
・一番外側のEnd Whileの時点でbag1のおはじきはWhileに入る前の個数にもどっている
・一番外側のWhileに差し掛かった時点でbag0のおはじきの数がbag1のおはじきで割り切れる時そのターンで作業は終了する
等のことが順々に分かっていって、最終的に求めるべき値は
4N(km - 1) + km - N + Σ(k=2to km) ceil(N/k)

kmは1でないNの最小の約数、ceil(X)はXの切り上げ小数点以下切り上げ
であることまで突き止めた。
けれどもNの最大値が大きいので単純にΣ計算したΟ(N)では間に合わないからどーしよー となっているところでタイムアップ。
後から考えてみて、ceil(N/k)の値が等しいkの範囲が求まるから適当に掛け算を使っていけば計算量小さくなるなあということでやってみたら通った。
y=N/xのグラフ描いてみて適当に長方形を描いてみたら計算量はどうやらΟ(√N)になるっぽい。


900は600の解析中に途中で嫌気がさしてちょっと覗いたくらいでやってません。

結果チャレンジも一回ミスして全問不正解だったためレートがガクンと落ちて緑色になってしまいました。

続きを読む

アンハッピーエンジェル

今日(昨日かな?)は高校の時の同級生と渋谷で遊んできました。
具体的にはゲーセンなりカラオケなりボーリングなりですね。
twitterやらskypeやらで普段から交流が無いわけではないんですが
キャンパス内で普通に見かけるしね
やっぱオフラインで会うというのは違うものがありますね。
普通にキャンパス内で見かけるんだけどね
かなり楽しかったですはい。ボーリングでは2ゲームやって両方140点超えたしね。
相当ツイてた一日でもありました。



ツイてたと言えば今日渋谷の自販機で飲み物(ドクペ)を買った時にこんなものが一緒に出てきました。

↓↓↓↓

ハッピー缶

最初は自販機の誤作動でコーラがもう一本出てきちゃったんだと思いましたが、
どうやらコカコーラが行っているキャンペーンだったようです。
一定の確率で”ハッピー缶”と呼ばれる中に品物が入った缶が一緒に落ちてくるみたいです。
ネットで検索してみるとハッピー缶を手にした人々が結構ブログで報告しているようですし、
銀のエンゼルも当てたことのない私はすっかり調子に乗ってしまったので、
ここで取り上げようと思いました。
ご覧の通り私のハッピー缶の中に入っていたのはイヤホン
(正式名称:HAPPYイヤホン)

でした。

ご丁寧に缶の台座まで付属して、飾るのには何一つ困らない仕様になっています。
さらに貯金箱としての機能(コイン投入口)を搭載
粋な計らいですね、素晴らしい。

続きを読む

助手席は指導員専用

どうやら梅雨が明けたようで、いよいよ夏ですね。
最近いよいよ暑くなってまいりました。
今日なんか特に暑かった気がします。
体力がないと暑さのせいで不注意になるとは聞きますが、
それでも、いつのまにか指を自分の目の中に突っ込んでいたのには
流石に私も驚きました。
痛かったです。



今日は仮免学科試験に行ってきました。自動車教習のあれです。
3月後半から教習所に通わせてもらってるはずなんですけどね。
技能の予約がなかなか取れず、仮免をとるまでにこんなに時間がかかってしまいました。
でも技能の予約が取れなかったのが原因なので
「はぁ〜?まだ仮免許も取ってないの―?遅っせー」
と私に言い放った彼は許されないと思います。

しかし私、免許を取ってどうするつもりなんでしょうね。
友人は皆「お前の運転する車には乗りたくない」とか言うし。
家族の送迎とかですかね。




ところで自動車教習の学科練習問題ってクセがありませんか?
もしかしたら私の通っている自動車学校だけかもしれませんけど。
私アレ気に入らないんですけど。

『次の文章を読み、正しいものには○を間違っているものには×をつけなさい』
という問題文の次に

―夏の夕方に家の前の道路に水を撒いた―(答え○)
とか

―コンサート会場の歩道上で、友達と車座して開場を待った―(答え×)
とかいう文章を平気で出してくるんですよ。
命題じゃねえじゃねえかよ! と初めて見たときは叫びたくなりました。
いやそりゃ出題者側が意図していることは分かりますけど
立ち話して交通の邪魔をしてはいけないってのは分かりますけど
なんかしっくりこねえなあって感じがするんですよね。
夏の夕方に水を撒くのが「正しい」のか、と問い詰めたくなる訳ですよ。
まぁ上の例は極端ですけど


納得いかん

大学前夜ないし東雲

ツイッターに入り浸って周りの新大学生の状況を探っている今日この頃でございます。
だって不安なんだもん。
初めからぼっちで諦めるのはねぇ。。。




4月1日に手続きがあって、晴れて大学生になったわけですが、
今回は忘れないうちにこれまでのハイライト的なものでも書いてしまおうかな、なんて。
備忘録備忘録

続きを読む

Appendix

プロフィール

Author:過密都市
東京の大学に通う1年生 理系
唐傘回しを練習してみたいと思っている。

FC2カウンター

カレンダー

12 | 2012/01 | 02
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 - - - -

天気予報


-天気予報コム- -FC2-

検索フォーム

Twitter

あまりに安易に始めたつぶやき いいのか?

Powered By FC2ブログ

今すぐブログを作ろう!

Powered By FC2ブログ

ブロとも申請フォーム

この人とブロともになる

QRコード

QRコード