10万本の棒の交差判定
ICPC勉強会、4月の模擬戦でした。
レベルが均等になるようにと組まれたペアですが、私のお相方は一つ上の主席の先輩…恐れ多い。
今回は全文英語のまま。ただし辞書の使用可、Javadocの参照可。でももちろんパソコンは一台です。
問題のレベルが高かったような気がする。A問題は単純な計算ですぐ解けて、B問題は文字列生成で再帰。
後者のコーディングは先輩に任せていたんだけれど、途中でバックトラックについて聞かれてオドオドしながらメソッドを書くことに。
バックトラックって、コードで見るとわかりにくい気がする。同じ再帰でも、DFSはわりとわかりやすい。
C問題は直線の交差判定だったのですが、なんか少年が部屋で床に棒を投げる話。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2653
で、この棒の本数が最大で10万本。ありえない。1秒に1回投げても10日じゃ終わらない。この少年確実に狂ってる。
まぁ要はその10万という数がポイントでして、普通のごり押しだと時間超過かメモリオーバーを起こします。
交差判定を後ろから進めていくとか、同じ大きさのboolean配列を使うとか、そんな工夫が必要。
D、E、Fは宿題になりました。二分法とかDPとかです。未だにDPを1から書けてない…
今回は他研の先輩が参加していて楽しかったです。
先輩の発表
休日だけど問答無用で学校です。
午前中、前とは違うクラスで実習TA。
insertion sortをJavaでやって、余裕のある人はRandomなんて使っちゃったりするという。
mainメソッドに引数を忘れて実行できなかったりとか、配列の中身の表示方法とか、くらいだったかな。
そんなに大きな問題はなかったように思えます。
隣のクラスに行って、見慣れた顔ぶれとsysoutの感動をわかちあったりしました。
昼は研究室の人たちで駅前のカレー屋さんへ。
戻ってきて備品の買い出しやら何やらして、ゼミナール。
私の指導先輩(?)の発表があったのですが、なんかもう遠い存在に見えて泣きそうでした。
先輩が私と同学年だったときと比べると、自分が情けなくてしょうがない。
でも自分のペースでやってるんだ、気にしすぎず気にしなさすぎず、適度に気にしていこうと思う。
私も学会とか行って、何か問題点を探して、自分のできることを探して…
そういえば他の授業に対して目を向けていなかったななんて思ったり。担当教員さんがどう出るかはわかりませんが。
終わってからは月1の食事会。(飲み会だけど飲む人があまりいないので)
焼肉とピザをおいしくいただきました。楽しかった。
HTTPからオブジェクト指向へ
午後から一年生の実習へ。
今回は違うクラスの番だったので、新しい学生たちを見ることになります。
とりあえず、前回も散々やったのに、CentOSの端末からemacsを起動するところからできていない人が多数。
まぁ、最初は「これが何をしているのか」(コンパイル、stdio.hのinclude、などなど)がわからないだろうし
動作を理解しているTAや教員からすれば「どうしてそこでそうなった…」なミスも、仕方ないのかな。
しかし変数宣言が関数の先頭でなくてもローカルでは動くんだな。C言語なんだけども。
なのに、提出してこっちのシステムに正誤チェックさせると構文解析でエラーが出るという。しかも解読不能。
問題点だと思いました。
実習の終わりのあたりで、ゼミナールのグループにいた子に廊下で「○○研の方ですよね」と声をかけられた。
そこから色々と話している内にどんどん一年生が集まってきて、最終的に7人くらいになっただろうか。
研究室配属やゼミナールについてなど色々と質問をしてきてくれた。頼られるのは嬉しい。
全員に名前や所属(ゼミナールのタームやサークルなど)を聞いたので、今後の繋がりも期待できそう。
もう興味を持っている研究室があるという子がいたので、とにかく先生に会って話をするよううながしたりしましたが
もし踏ん切りがつかなかったら私がどうにかしてあげるからと言っておきました。
だって、せっかくここに入ってできることを見つけられるんだもの。
興味があるんですって言われて嫌な顔するような先生はいないし(もしいたとしたら背中を押したりはしない)
いい方に事は運ぶと思うんだ。
そのあと研究室ではメールチェックしたりファイルの整理したり。
Wicketの本は、ほんとに最初の最初を読んでみました。
矢野勉さんがプログラミングに対してどう構えてきたか、そしてどういう思いでこの本を書いたのか、
うんうん、と頷きながら丁寧に読みました。
とりあえずわかったことは、WicketはこれまでのstrutsのようなHTTP(request&response)的なフレームワークではなく
極力設定ファイルとしてのxmlを排除し、Javaプログラムだけで動的に処理を行っているフレームワークだと。
とにかく「オブジェクト指向」という言葉が大プッシュされてました。
strutsのようなフレームワークだと、限界があるみたい。
とりあえず私が今まで読んでたWTPに出てきたようなものとはまず概念から違うようなので、
気持ちを切り替えて読んでいこうと思います。
しかし、そろそろ自分がゼミで研究の進捗状況を発表しなければいけないかもしれない。(当初より早まった)
どうしよう、とりあえずWTPの本の内容をまとめるのと…
それと、私の根本にある、目標のこととかも話した方がいいかな。
Wicket到着
今日は2限から一年生のゼミナールへ。研究室から5人の院生さんとぞろぞろ。
内容としては正直少し難しいのですが、チーム対戦という形をとったので
この時期の一年生には、交流的な意味で、大変よいきっかけとなったのではないでしょうか。
隣のスペースから来た先生も、そうしたほうがよかったなぁ、なんてぼやいていました。
新たに加わったグループはレゴを使ったロボットを動かしていました。そこにも同期がいました。
それでグループで一緒にお弁当を食べたのですが、最初に「中学からプログラムやってました」と自己紹介した子の隣を
すかさずゲットし、熱烈なアピール。
C言語はわかるけどJavaはわからないと言っていた。でもでも、プログラムに興味を持ってくれているのはとても嬉しい!
プログラミングコンテストや、うちの研究室の勉強会の話をしました。今後何らかの形で関わっていけたらいいなぁ。
3限は授業です。ひたすらプログラミング…というか、問題が難しかったので、データ構造を作るところまで。
ComparableとかArraysのsortメソッドとか、ダイクストラでよく使うので、そこはまぁ大丈夫。
ただ、問題を解く部分が…数秒で終わるような処理が思いつきません。
計算時間の見積もりは、うちの研究室の核と言っても過言ではありませんからね。
その後ある先生の忘れ物を発見したので届けに行って、就活を終えた他研の同期と立ち話して、サークル寄って、
三年生の授業にお邪魔してきました。C言語でソケット通信してました。
やった覚えはあるけど、そういえばあまり理解してなかった。なのでサークルの後輩の質問に少し答えただけ。
あとはこの授業に私を呼んだ(?)ドクターの方に挨拶したり三年生に「TAなんですか!?」と言われて
いや違う違うってテンパってあわあわして「○○研究室ですか!?」とか言われて研究室の説明をして
先生には「また君か。もう何なの?(下級生の授業に)来すぎじゃない?もうTA認定。」と言われ
よく言えば自分の存在が広がっていく。普通に言えばでしゃばってる。
けどそれで研究室の宣伝というか、下級生の研究に対する意欲の向上というか、そういうのに繋がったらいいなぁ。
そして、満を持してWicketの本が届きました!
著者は矢野勉さん。ビックリした。というのも、twitterで普通にお互いフォローしあっていたもので。
普通は逆なんだろうけど、私はtwitterから知りましたので、驚きました。
どれくらいかかるかは全くわかりませんが、…読んでいきます。はい。
先輩に「ここは大事」「ここは軽く流して」と目次を案内してもらったので、とりあえず使えるようにならなくちゃ。
あとは、それを使って何をするかですね。所属する班も、やっていて楽しいこともあるのだけれど
自分がそこで何をするか。自分がそこで何ができるか。これがないと研究じゃなくてただの遊びになっちゃうからね。
今週の授業TAの予習をして、少し遅めの帰宅。
帰りが一緒になった先輩と研究室の話をしていたときに
「山下はすごい勉強してると思うよ」
と言われて、素直に嬉しかった。
勉強って別に人から認めてもらうものではないけれど、それでも、見ていてくれていることが、素直に嬉しかった。
カスタムコンポーネントの作成
3限はプロコン勉強会。
とりあえず、座標系における移動については、move配列を用意できるようにならなければ…
例えば、int move = {{1,1},{1,-1},{-1,1},{-1,-1}}みたいな感じで配列を用意すれば
x座標にmove[i][0]を、y座標にmove[i][1]を加算する処理を、for文でiを変化させながら行っていけば
簡単に座標系における移動ができます。if文いっぱい書かなくても済みます。
あとは幾何の交差判定で、isLeftメソッドが出てきました。内積の計算ですね、幾何には必須。
それとプレオーダー、ポストオーダー、インオーダーと二分木の生成など、今回はためになる話が多かったです。
それからは書類を少し整理して、WSP本の仕上げへ。カスタムコンポーネントの作成です。
これにはUIComponentBaseを継承するUIコンポーネントクラス(xmlに登録するために文字列を返すだけ)
UIComponentTagを継承するタグクラス(属性フィールドをメンバとして持ち、コンポーネントのmapにputしていく)
Rendererを継承するレンダラクラス(タグの開始部分と終了部分における出力)
TLDファイル(カスタムタグの定義と同様)
を、用意します。
で、
faces-config.xml(UIコンポーネントとレンダラを登録)
を編集します。
あとはJSPで、カスタムタグと同様にprefixを定義し、body内で使っていきます。
全部サンプルが載ってたからサクサク進んだけど、これ自分で作れって言われたらちょっとキツいなぁ…
Tokenizerとか初めて聞いたし、あとタグクラスでコンポーネントの属性をputしていく時に
バインディングが指定されているかどうかで処理が分岐したりとか、このあたりはややこしかった。
まぁともかく本は終了!これで基礎はさらえたはず。
そろそろゼミの発表の資料作らなきゃなぁ。どうも私、一週間早まりそうなので。
今日はお客様の多い日でした。
他研からプロコン勉強会に参加しにきてくれた同期、他研から授業の質問に来た同期、
サークルの新歓ついでに顔を見せてくれたOBさん。
今後もより入りやすい、風通しのよい研究室でいたいなぁと思う。
カスタムコンポーネントのために
朝、電車の中で印刷した分を少し読んだ。
今度はカスタムコンポーネントを作ってみる、らしい。これもソースは特に問題なく読めそうなので
さっさと実装できそう。問題は、これらの知識を使って何をするかだな…
2限の実習は寝坊と体調不良で、参加できませんでした。申し訳ない…と言っても、ボランティア扱いだけど…
ゼミ長がこんなんじゃあ、情けないですね。
昼頃学校に行って、まず奨学金の書類をもらってきました。色々書くものが多いです。
それから他研に遊びに行って、そこにいた同期と先生とおしゃべり。
その研究室のメンバーに関する話、とある授業の存在意義、プログラミングに対する見識などなど…
さて研究室へ、と思ったら廊下で同期に出くわし、更に別の他研へ。
やっぱり横の繋がりも大事だよなぁ、と思って。そこでは院生の方などとはお話できませんでしたが
また遊びに行こうかな。みんなの就活状況、研究内容、色々知りたい。
戻って研究室のプリンタの修理。お手入れしただけだけど。いまのところ大丈夫そう、かな。
5限のゼミナールでは三角形分割のアルゴリズムについての発表と、プログラム添削エディタについての発表。
両方とも去年の今頃に見学に行った時から何度か発表は聞いているので、少しは理解できたかも。
先生の「迷走は大事だよ。研究は迷走だからね」は、名言だと思いました。
その後、明日のプロコン勉強会のために問題を少しやってみる。
二問解けた。再帰と、単純な計算だったので、特にひねったことはしていないのですが…
後者がA問題、前者がB問題といったところでしょうか。
勉強に関係ないけど、サークルの原稿を書かないと。
あとはオープンラボのことを頭に入れておいて、それから来週のゼミの食事会の準備もしなきゃ。