続々々々々pku1989

なんか昔ひたすらショートコーディングしてたpku1989ですが、

ふとソース見てたら冗長性があることに気づいて1バイト減らせました。

てことで数ヶ月ぶりの単独1位！ひゃっほーw


いまから環境依存(コンピュータによって結果が変わること)でないことを、

仕様書読んで確認してきますw


22:56 追記: C言語についてはJIS X3010で定められているのですが、

それを見たところ定義された動作(=環境依存でない)ということが分かりました☆


んでちなみに明日はICPC国内予選。がんばるんばw

続々々々pku1989;

研究室配属とかありましたがまぁ軽くスルーでw

pku1989ですが、何かみんな俺と同じ95Bになってて、

いつのまにか94Bの人もでてきて"にょろーん"ってなってたのですが、

昨日mazunさんに教えてもらったテクで95B->94Bになって今1位タイ。

これ誰か93Bにするんだろうなぁ…笑

http://acm.pku.edu.cn/JudgeOnline/problemstatus?problem_id=1989&orderby=clen

続pku1989

この前ちょこっと書いたpku1989ですが、

YUKI.M> さんから"解法すぐ思いついたよ"とか言われてしまいましたorz

YUKI.M> さんがショートコーディング(できるだけ短いプログラムを書くこと)を

していたので、そこに参入してみました。

まず今までのトップが119Bだったので、それを目指してカリカリ。

B:バイト=文字数だと思ってくださいね。

145B->140B->136B->134Bって感じで縮めていって、、

ある時ふと"ここってこうすればいいんじゃね？"って思って一気に118Bに。

ふとYUKI.M> さんを見ると109BでAcceptされていたので、

にょろーんとか思いながらカリカリやっていると

118B->116B->112B->109BとYUKI.M> さんに並び、

ちょこっといじって107Bを達成w

ここまで1時間半ぐらいかかったよ、、疲れたw

んでー、、最後にふとif(a)b=x;else if(c)d=y;を、

a?b=x:c?d=y:1;って書いてみたらコンパイル通ったので、

これで一気に96Bになりました。ということで現在暫定トップ。

YUKI.M> さんグループの挑戦をお待ちしていますw

Cow Math

最近スランプとかぐだぐだ言ってますが、、

理由の１つに魅力的な問題に見えない、という事があって。

いままではどんな問題でも解くのが楽しかったんだけど、

"簡単すぎ"とか"プログラム書くだけ"とか言う問題が嫌になってきて。


でも今日久々に(最近やってなかったから久々なだけかもしれんけど)

楽しい問題に出会いました、、それが pku2132 Cow Math

問題自体はちょと説明が面倒なんですが、


25個の街と、それら任意の2都市をつなぐ道路が与えられます。

各道路には道路番号(重複しうる)が与えられていて、

Bessieは都市1から都市2に行きたいのですが、

"都市1から都市2に行く間に他の都市を通ってもよいが、

同じ都市を2回通ってはいけない"という条件が与えられています。

Bessieは、最大公約数を計算するのが大好きな子なので、

都市1から都市2まで行く途中で通った道路の番号の、

最大公約数を計算して覚えて行きます(笑)


さてここで問題です。Bessieが都市1から都市2に行くには、

沢山の行き方が存在します。それぞれに行き方に対して、

経由した道路番号の最大公約数が存在する訳ですが、

それらの最小公倍数はいくつでしょうか。


という問題です。説明が下手な上に問題がややこしいのでカオスw

最大公約数とか最小公倍数とか出てきて"うわー、、嫌な問題"

って思ったのですが、思いついてみればすごく綺麗な解法があって。

こういう素敵な解法を思いついた瞬間が気持ちいいんだよなぁーって、

改めて感じました。さてここを見たプログラマの方、思いつきますかね？w



説明のためにちょと簡単化した部分とかあるので、

問題解く人はちゃんと問題文を読んでくださいな。



で、明日はニコニコ技術部 京都勉強会を見学してきます。

なんかいい刺激があると嬉しいな、、楽しみ楽しみw

pku

今月に入って何回"pku"ってタイトルの日記を書いただろうかw

600位を突破して589位になりました、、正解数も338問。

んー、、やっぱ学校あるときよりだいぶ捗るなぁ、、

こんなことばっかやってて大丈夫なのかと思うときもあるけど

まぁ世界大会いくぞーって気合で乗り切ることにしてます。


来月TOEICを受けて、再来月に応用情報処理技術者試験とかいうものを受ける予定。

前者は前よりいい点とるのが目標で、

後者は(まわりの声によると)学校の授業+αでとれるものだとかなんとか。


そいや最近iKnow(英語勉強用SNS)行ってないな、、

TOEICもあるしそろそろ再開しないとね、、がんばるんば。

Ave Maria

今日もバイト行ってpkuといういつものroutine.

1人でプログラム書くときはいつも何かBGMを流してるんですが、、

今日は何故かAve Mariaが聞きたくなったので、

youtubeで見つけたAve Mariaをランダム再生してましたw



で、今日もプログラミングネタなんですがー、、

最近10分で書けるお手軽パーサーにはまってますw


えーと、パーサーと言うのはですね、、

「構文解析器」っていう物なのですが、例えば

I wish I were a bird, which can fly! とか言う文を見たときに、

I wish (I were a bird (, which can fly)))! とか言う感じに、

区切ってくれるような、そんな働き方をします。


別の例で言うと、1+2*3+3*5/2-3っていう数式を、

(((1+(2*3))+((3*5)/2))-3)っていう感じで

適切に括弧をつけてくれる、みたいなのも構文解析です。



んで、上の例を見て分かる通り、構文解析ってのはなかなかややこしいんです。

小学生とかだと1+2*3を9 ( = (1+2)*3 ) って言ってしまったり、

にゅうしとかでえいごをなんねんべんきょうしてもがくしゃたちがこのみそうな

ふくざつでこうぶんがいりみだれたようなえいぶんがかいしゃくできなかったり、

なかなか難しいわけですよ。この平仮名の文章も構文解析しにくいでしょ？w


人間が大変なものってのはプログラムするのも大変なわけで、

普通はパーサ(構文解析器)を作るってのはなかなか手のかかる作業なわけです。

でも上のリンクの、10分で書けるお手軽パーサーっていうサイトを参考にすると、

なんか驚くほど簡単にパーサが作れるようになってしまったのですw


詳細を述べるにはLL文法で左再帰があると不味い理由とか、

なんかそういうおもしろくないことを書かないといけないので省略しますが、、

まぁICPCとか挑戦してる人にはこのサイトはものすごく勉強になると思います。


で、"10分で書ける"お手軽パーサーって名前のサイトなので、

本当に10分で書けるのか試してみました。

使った問題はこちら。問題文の解説とかは省略でw


で、さすがに問題を読む時間を含めると間に合わないことが確定してしまうので、

まず問題を読んでから、時刻をチェックしてプログラムを書き始めてみました。

このとき22:10でした。で、まず文法を列挙して、パーサ部分をカリカリ書いて、

最後に入出力部分をカリカリカリカリ書いて、submitしてみたら一発Accept。

そしてこのときの時間が22:19。所要時間がきっかり10分(笑)


いやー、、正直10分で書けると思ってなかったから感動しました。

これでまた一つ知識がついたので世界大会に近づいたかなー、

なんて思ってみたりみなかったり。いや、思ってるんですがw


俺がここ数日pkuで解いた問題を探すと、

パーサの練習になるような問題がいくつかあるので、

興味のある人はやってみてくださいな。

そろそろお風呂入ったかな、、いてきますw

300問目！

もう毎日がpku一色になってます(笑

今日は久しぶりにバイトに行って、帰ってきてから鍋を作りつつpku。笑"

んでー、記念すべき300問を突破しました。はっぴーw

300問めはこちら。

500個の点が2次元平面上にあることを考えてみてください。

んで、各点と各点の位置関係、つまり"AはBの真北にある"とか、

"AはBの南西にある"とかいうのが10,000個与えられたとき、

その制約を満たすような500個の点の配置は存在するかどうか、という問題です。

さてうちのチームの人には解法を考えてもらいましょうか。

初めて"続きを読む"をつかってみるテスト。

PKU

未だ14人しか解いていない問題が解けたのでとってもハッピー☆

で、その問題はこちら。

http://acm.pku.edu.cn/JudgeOnline/problem?id=3679

ま簡単に説明すると…問題のページにあるような、

何個かの町(ブロック)と、それらを結ぶstreetが与えられます。

んで、各ブロックごとに、そこを手に入れたときの利益が与えられてます。

Tomは自転車で好きなところをグルッと回ってきて、

図の赤線みたいな閉路を作ることが許されています。

で、閉路の中のブロックをTomは手に入れることができるので、

そのときのTomの最大の利益はいくらですかーって問題です。

あとTomは20秒以内に帰ってこないといけない、とかいう制約があって、

(ブロックの1辺がちょうど1秒で走れる距離)これによって問題が

だいぶ簡単に(といっても大変だけど)なっています。


解法の説明もしようかと思ったけど、

この日記を見て挑戦する人もいると思うのでやめておきます。


ちょうどこの3日ほどスノボ行ってて、

PCが手元になかったので、今まで解けなかった問題をいっぱい考えてたら、

ちょうどこの問題の解法がひらめいて、実装してみたら通ったっていう。

バグを出すことなく一発でAcceptされたのですごく嬉しいです☆

ちなみに今769位で286問正解だそーです。

PKU

pkuが復活して数問解いたら、もう800位になってました、はっぴー

http://acm.pku.edu.cn/JudgeOnline/userstatus?user_id=mirac

このページの左上赤字が今のランキングで、

右側にだーっと並んでいるのが今までに解いた問題。

279問も解いてるとなかなか壮観w

あと1週間ぐらいで300問行きそうだねー、、頑張ろう。

あ、明日から3日ほどスキーいってきます。楽しみーw

PKU

pkuは昨日数時間復帰しましたがまた落ちました

PKU

pkuは今日も落ちてますorz

pku

この前頑張るぞーって書いたPKUなんですが、

今日で3日連続で落ちてます。んー、、つまりサイトにアクセスできません。

なんか中国は旧正月らしくて、ちょうどそれでいう元旦から落ちて、

今日で3日目。わざとなのかわざとじゃないのか…そろそろ復旧してくれんかなw

まーおかげでテスト勉強ははかどりまして。

初日かつ山場の今日を乗りきったのでなんとかなるかなー

それにしてもサイト一つ落ちただけで全然落ち着かないのだけどどうしたものだろう…

解けないー

pku1113番が解けません。

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

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

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

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

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

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

今日のpku

Contest - South Central China 2008 hosted by NUDT

ぼろぼろに負けました。スコアボードを見たときの愕然さはかつてないものでしたw

---

来年の目標を決めようと思います。

あぁ、、俺は誕生日みたいな「一年ごとに来る区切り」の前後で「今年」「来年」と

言ったりするのだけど、、これはあまり一般的では…というか使われないらしいねw

まぁそれでも俺にとっては来年であることに変わりないノですが。え、、変？w



来年の目標。

・いろんなことに挑戦する
・プログラミングスキルをつける
・喋り下手を克服する
・身だしなみに気を配る
・感情を表に出す、コントロールする
・どんなことに対しても許容幅を広げる
・将来をよく考える


まぁ幅広い分野…というかまとまりのない目標だけど、、頑張ろうと思います。

目標はよく立てるんだけどすぐ忘れるんだよなぁ…


ということで目標に1つ追加。

・目標を達成する

目標を忘れない、ではないところが重要w

夜更かしする

↓
起きるのが遅くなる
↓
その夜なかなか寝れない
↓
夜ブログを書くのにパソコンをつける　　　←いまここ。
↓
いつのまにかネットサーフィン
↓
また夜更かしする


まぁそんなことはどうでもよくて笑

今日はpku(北京大学)のプログラミング問題をいくつかといてました。

とりあえず解けたのは問題番号で2570、2571、2572の3問。

適当に問題選んだけど、どっかの国の2000年国内予選問題だったみたいです。

難易度としては日本と同じぐらいなのかな〜、、勘だけどw

問題をコピーして説明とかしたかったのだけど、

大学の電源工事中とかでホームページが見れなくなっちゃってるのでまた今度…w