Intern おしまい

昨日で長いようで短かったインターン生活が終わりました。

いろいろ思ったことなど。

  • プログラミングについて。
    • 知識も経験も足りなすぎる。
    • 読み返すと分からない見通しの悪いコードばかり書いてしまった
    • 人のコードを読むのに慣れてない、読むのにめっちゃ時間がかかる。かなしい…
    • オブジェクト指向で、機能が分離しきれてないと超めんどくさい事になるのは、身をもって体験できたから良かったかもしれないw
    • CS専攻してるくせにCSの知識が足りなさすぎる…
  • 語学について。
    • ＼(＾o＾)／
    • 英作文
      • 書けなさ過ぎてびっくりした。
      • ダメすぎるから1から文法やり直す
    • 英会話
      • しゃべるのは日本語でも苦手なんですが…
      • まずは聞くことからやろう
      • ポッドキャストで興味のある分野を聞くと良いらしい

というかここまでダメなのによく選考通ったなって不思議┐(´ー｀)┌
とりあえずこれからは、基本をしっかり固めてかなきゃいけないなと思います。
English,C++,Java,Pythonに関してIntermediateと書けるようになりたいな。
あとICPC!国内大会で賞状もらう!

  • plus plus
    • 姐御好きにはたまらない環境
    • ビリヤード楽しい！
    • Walkersショートブレッドという素晴らしいクッキーに出会えた
    • かゆ〜な+Kiriは神
    • Python便利
    • ShellScript強力
    • Screen便利すぎる！
    • P.S. 今度は字が小さくなっていない事を、お祈り致します。

インターンの同期の人たちは素敵＆優秀な人ばかりで、友達になれただけでも嬉しかった。
また機会があれば集まって飲み会したいなあ〜（*´ω｀*）
そしてまた一緒に働きたいw

インターン最終日に右手の人差指を突き指？捻挫？して、改行が辛いのでこれくらいで…

UTPC

Misc

UTPCに参加しました．
12問中5問通して29位でした．
起きたら12:10だったのと，DPで一箇所MODをとってないところがあったりして2回WA出したのが諸ぼんぼり

最後はずっと座標変換＋回転の問題をやっていたのだけど，全然答え合わなくて悲しかったｗ
オートマトンの状態と連動して動くBFSとか面白いなぁと思ったけど解けなかった．

5時間って短いな┐(´ー｀)┌

ICPC国内予選

ICPC

ICPC国内予選に id:keitanxkeitan と id:kouri128 さんと参加しました！
目標は10位以内だったけど，11位でした．
アジア予選にはでれるらしいけど…
ちゃんと練習セッションやっとけば…ごめんなさい…

Aはやるだけで簡単なんだけど，サブミットするファイル間違ってて2回もWA…＼(＾o＾)／
このせいでなんか頭の中が真っ白になってもうだめぽ状態になってしまった…
Bはkouriさんが通してくれました．座標を2倍に増やして幅優先やればいいのかな．
Cはkeitanが問題読んでくれて，あ，DPだ！と思って僕が書きました．AC!安心．
Eは不閉路を検知できる方法で最短路を求めればいいと思ってBellman Fordを書いたんだけどWA..
自己ループを使ってないっぽいことがわかって，最短路がループがあるところを通ってたらNOになるように変えたけどWA...
方針を変えないとダメだと思い，ダイクストラで[頂点][自己ループしたか]を状態にして，
dp[goal][0] == INF || dp[goal][0] > dp[goal][1]だったらNOに変えてみたけどやっぱダメ．．．オワタェ…＼(＾o＾)／

40010によるとゴールからやってくとループが簡単に発見できるらしい事がわかった．
スタートからやって文字列を後ろに連結してくと，隙間にaa..とかいれてそこからいける場所のコストをどんどん小さくできるか判断するのが難しい．
が，ゴールからやって文字列を前に連結してくと自分のいる場所のコストの先頭にaaとか付けて小さくできることがすぐに分かる，のかな．笑

たしかこのへんでDをkouriさんがじっくり慎重に書いてくれてAC！ありがとうごじあます（；；）
もうEはうまく行かないから違うのに変えようと思ってGに変えて，反射させる方法を全部列挙して最短路を求めよう！
って方針は決まったんだけど，残り20分くらい？しかなくてイッパイイッパイになってしまって，
どこがどの座標になってるかとかどの線分に対応してるかとかよくわからなくなってしまって書ききれ無かった…
実装力不足だ…
Gからやり始めてたら違ったのかなぁ．でもEの方がやりやすそうに見えてしまったんだよね．．．
残りの1分は諦めてずっとstandingsをリロードしまくってサーバーに負荷をかけるという姑息なことをしていたｗ

東工大最強の40010は3位だった．いいなぁ！ｗ
僕は模擬が良すぎてちょっと浮かれすぎてたなと反省．．
あと先輩に頼りすぎだｗ
残りの半年はいろいろ新しい問題にチャレンジしていきたいな．

日記書かなすぎですね┐(´ー｀)┌

ICPC

模擬国内予選楽しかったです．
ライブラリのVerifyもできたしｗ
ただ最後に東大ですら解けない問題に解けそうと思って突っ込んでしまったのが失敗だったなぁと思います．
Dを３人で考えてたら解けてたかもしれないなぁと…
周りが解けてる問題が見えないのって怖い．
でも，２人で交互にコード書いて，残りの１人とペアプログラミングするやり方はうちのチームにあってるような気がしました（*´ω｀*）

期待の新人 id:keitanxkeitan 強すぎるお…

1511 Invitation Cards

PKU

概要

有向グラフが与えられて，エッジにはコストがついている．
N頂点あったら，1番の頂点からN人の人をすべての頂点に行き渡るように移動させて，
そこから１番に返ってくるような，すべての人についてのコストの和の最小値を答えるという問題．
頂点も辺も100万まで．

解法

解き方はダイクストラなのですが，頂点と辺が異常に多いので，何とかしないといけない．．
そこでPKU用の高速なグラフ構造について書きます．
PKUが最適化をしてくれないせいでまたひとつバッドノウハウを覚えてしまいました．
以下のコードは擬似コードなので，足りないところは補ってくだしあ
ちなみに，いつもグラフの問題は，こんな感じで構造を作っています．

struct Edge {
  int to, cost;
};
typedef vector<vector<Edge> > Graph;
Graph g(N);

二重vectorは遅いので，シビアなときとか，頂点数が多いときは，vectorを一段下げて使いまわします．

struct Edge {
  int to, cost;
};
const int MN = 1000;
vector<Edge> g[MN];

これでも駄目なときは，最大次数を見極めて，配列の配列みたいにしていました．

struct Edge {
  int to, cost;
};
const int MN = 1000;
Edge g[MN][100];
int idx[MN];

でもよく考えるともっとうまいやり方があって，全体の辺の数がわかっているのでエッジ配列に詰め込んで，オフセットを付けて見てあげればいいんです．

struct Edge {
  int src, dst, cost;
  bool operator < (const Edge& e) const {
    if(src != e.src) return src < e.src;
    return dst < e.dst;
  }
};
const int MN = 1000, MM = 1000;
int deg[MN], acc[MN + 1];
Edge es[MM];
int N, M;

REP(i, M) {
  int s, t, c;
  es[i] = Edge(s, t, c);
  deg[s]++;
}
sort(es, es + M);
acc[0] = 0;
REP(i, N) acc[i + 1] = acc[i] + deg[i];

REP(i, N) {
  int offset = acc[i];
  REP(j, deg[i]) {
    Edge* it = &es[offset + j];
    // ...
  }
}

こんな感じで，頂点から出るエッジの数と，エッジ配列内のどこからその頂点からのエッジが始まるかのオフセットを計算しておくと，vectorを使わずにメモリも最小限で済みます．
sortをしなきゃいけないけれど，それを差し引いても速いです．

こんな日記でいいんでしょうかｗ

サブミッションスクリプト

PKU

今更だけどサブミッション用のスクリプトを公開してみる…ｗ

submit 1000.cc

みたいな感じでコマンドを実行すると，1000にサブミットできるだけという低機能(^p^)

↓のrubyスクリプトをpku用のディレクトリに置く
http://halwhite.s352.xrea.com/pku.txt
ファイル名をsubmit.rb,
'id', 'pass', form.languageを適当に変える．
あとmechanizeとかをgemで入れてくだしあ．

あと，コマンドを登録する．
僕はbashを使ってるので，
.bash_profileに

submit() { ruby submit.rb $1; }

と書くだけでした．
あと，

test() { g++ -Wall -g -O0 $1.cc && time ./a.out < $1.in; }

こんな感じのテスト用コマンドも使ってます．
微妙に不便です．

SRM466 Div1

Topcoder

はじめて500解けたわーい．
250落ちたしょぼーん．

250は考え方はあってるんだけど，数字を消して書き換えるしか出来ない→桁を増やしちゃいけないって言うことを理解できてなくて，つねに10桁になるまで生成しては比較ってやってしまったorz

500は解いてる最中，頭の中が整理されるに従ってどんどん式が簡単になって，最終的に10行位になって楽しかった．
引いたくじにどう書いていようと関係ないってなんでもっと早く気づかないんだ（´・ω・｀）
東大生がtopcoderの成績いいのって，東大の入試こんな感じの確率の問題ばっかり出てるからな気がする．
彼らは確率漸化式とか超得意なんだよ，たぶん．

ICPCまでに黄色くなる！(ｷﾘｯ