uvaが新鯖建てやがった。http://icpcres.ecs.baylor.edu/onlinejudge/26日までに移行するとかでｗｋｔｋしてたけど、案の定先延ばし。ちゃんと働かなきゃ！！

http://acm.uva.es/p/v1/152.htmlちょｗｗｗｗ brute forceで行けちゃいました。というかSTL遅すぎ。cだと3秒でacなのにc++&stlだとtleて。

http://acm.uva.es/p/v1/149.html整数座標に無限に木が立ってて、ある地点から見える木の数を求めろという問題。ある木が「見える」というのは、その木の両端が直接見えて、かつ、他の任意の木との隙間の角度が0.01度以上ある場合のことを言うと。木は完全な…

http://acm.uva.es/p/v8/843.htmlカエサル暗号の対応表を作れっていう問題．とりあえず，アルファベットからアルファベットの写像は全単写でなくてはならないので， あるアルファベットaにどの文字に割り当てられたかを示すM[a] あるアルファベットaにどの文…

uvaを解いてみた。 http://acm.uva.es/p/v103/10363.html ○×ゲームの話。英語ではTic Tac Toeというらしい。○×の並んだテーブルが与えられて、それが○×ゲームの局面に成り得るかって問題。×が先攻ね。場合分けすればおk。 http://acm.uva.es/p/v110/11015.ht…

http://acm.uva.es/p/v102/10267.html簡単なペイントソフトをシミュレートする問題．全部で9つの命令がある．命令の詳細については問題参照．言われた通りに動くようなプログラムを作れば良い．ただ，accept率は14.6%．なめてかかると痛い目を見るということ…

http://acm.uva.es/p/v7/706.html数字の0から9をLCD表示形式で出力せよって問題．サンプル見たらどういうことか分かるかと．ただし，サイズsが与えられるので，その大きさで出力しなきゃならない．例えば「５」を例にすると， s=1 − ｜ − ｜ −s=2 −− ｜ ｜ −…

http://acm.uva.es/p/v101/10137.html割り勘問題．n人で旅行に行ったときに，n人が払ったそれぞれの金額が与えられる．旅行から帰ってきてから，みんな割り勘するために，金を移動することになる．その移動する金が最も少なくて済むのはいくらかって問題．ち…

じゃあ，昨日の続きで．頑張って行こうか．ProgrammingChallengeの第一章には，ICPCやuvaに関する一般的な解法テクニックが書かれている．これはほんとに一般的すぎるので，改めて何も言うことはないのでまいっちんぐ．第一章で紹介されている問題は，前提知…

Summation of Four Primes http://acm.uva.es/p/v101/10168.html自然数Nを任意の4つの素数の和で表せという問題．Nこの問題はゴールドバッハの予想を使う．多くの場合ゴールドバッハの予想とは， 4以上の任意の偶数は，2つの素数の和で表せる と言われるよう…

Network http://acm.uva.es/p/v3/315.htmlグラフの節点の中で，その節点に繋がる全ての経路が移動不能になったとき，他のどこかの節点からどこかの節点への経路も絶たれてしまうような節点の数を出力する．上手く説明できないけど，要はグラフの連結成分を数…

Ray Through Glasses http://acm.uva.es/p/v103/10334.html 図を見れば問題の意味は分かると思う．なんとなくだが，光が反射する板が2枚合って，光が反射する回数nが与えられたときに，何通りの反射の仕方があるかを求める問題．動作をそのまま再帰関数で定…

Dungeon Master http://acm.uva.es/p/v5/532.html ありがちな幅優先探索かと思いきや，複数層に分かれたテーブルを探索することに．何故だか萌える．こういう探索問題だと，インデックスの領域あふれを見るのに，index幅優先探索みたいな基本的なアルゴリズ…

The Knights Of The Round Table http://acm.uva.es/p/v101/10195.html 三角形の三辺，a，b，cが与えられたとき，その三角形の内接円の半径を求める問題．内接円の半径は，三角形の面積/sで出る．ただし，s=(a+b+c)/2である．したがって，三角形の面積を求め…

A multiplication game http://acm.uva.es/p/v8/847.htmlp=1から始めて，スタン，オリーが交互に2から9の好きな数字をかけて，先にnに達した方が勝ちというゲームがある．nが与えられたときに，どちらが勝つかを求める問題．二人とも最善の手を採ることが保…

"Mischievous Children" http://acm.uva.es/p/v103/10338.html 同じ要素をa1個，a2個，・・・，am個含む，合計n個の要素の順列は n!/(a1! * a2! * ・・・ * a3!) 20!はオーバーフローするので，最大のaiについてだけ先に約分をしておく．

今，uvaのある問題を解いているのだが，その解法の布石となるものがいくつかあるのでメモっておく．さて，フィボナッチ数列といえば f(n)=1 : n=0,1 f(n)=f(n-1)+f(n+1) : n >= 2 で定義される数列であるが，これを行列で表現したFibonacci Q-Matrixというの…

Levenshtein Edit Distanceの名で知られる，文字列の距離を求めるアルゴリズム．ある文字列aに，挿入，削除，置換といった操作を何度施せば，別の文字列bになるのかを求める．去年のアジア予選で，これをアジャストして使う問題が出た．これもDPなんだけど，…

エラトステネスの篩で瞬殺．こういう問題本番でも出ないかなぁ．デネェナァ・・・