お久しぶりです

なんか1週間ほど日記書かなかったみたいだな、、

特に忙しかった訳でもないのだけど…笑”

ICPCとかのコンテストやってると、

"ライブラリ"ってのがあると便利なのです。

ライブラリってのは、各チームごとにまとめた

参考プログラム集みたいなやつのことで。

ある問題を解こうと思ったら、

結構な確率で有名な解法があったりするわけです。

まぁたとえば方程式ならガウスの消去法、とか。

んでまぁ、そんな有名な解法をまとめたのがライブラリってやつで。

有名な解法なんだから毎回毎回頑張って書かなくても、

ライブラリに入れとけばコピーするだけで使えるから便利☆みたいな。

今日も１つライブラリに入れれそうな有名な解法について

勉強してみました。その名も最小費用流。

んー、、どんな例があるかなー、、

(ググってみよう…)

あー、、この前解いたのは、、

発電所がいっぱいあって、都市もいっぱいあって、

各発電所から都市に電力を送信する費用が与えられて、

あと発電所の最大発電量とか都市の電力使用量とかが与えられて、

"一番安くするにはどこでどれだけ発電したらいいでしょう"

みたいな感じの問題でしたわさ。

んで、最小費用流って聞くと、

逆に最大費用流ってのはないの？って思いませんか？

俺は昔思ったのだけどw

詳しくは省略しますが、、一般には解けないのです。

でもまぁ制約条件をいっぱい付け加えていくと解けたりして…(略

まぁ聞きたい人は聞いてくれたらいくらでも教えますよ笑”


アルゴリズム勉強するといろんな知識がつくから

おもしろいなーと思います。


次の練習会が日曜日にあるのだけど、

なんか交換留学でうちの大学に来ている、ヨーロッパのすごい大学生が

一緒に練習会に参加してくれるそうですw

さてめっためったにやられないように気をつけねば…笑"