2011-01-01から1年間の記事一覧
問題 バスケの勝敗表が与えられるので、RPIという指標を計算する。 「RPI = 0.25 * WP + 0.50 * OWP + 0.25 * OOWP」で、定義されそれぞれ、 ・WP : そのチームの勝率 ・OWP : そのチームの対戦相手の勝率(ただし、そのチームとの対戦を除く) ・OOWP : その…
問題 あなたはSeanとハングマンというゲームをやる。これは、順にアルファベットを言っていき、選んだ単語にそのアルファベットがあればそこだけ公開、なければ-1点。あなたは辞書Dの中から1単語選ぶ。Seanはアルファベットリストがあって、そのリストの順に…
問題 今日はD回ゲームをした。勝率はPD%。今までのゲームはG回で勝率がPG%。なんと奇跡的にPD,PGはきっちり整数値となった! PD,PGが与えられる。この時、そのPD,PGが正しい値としてあり得るかを判定して返す。 ただし、今日のゲームはN回以下であった。(D…
1078位で通過ならず。(上位1000人通過)
通過してない。
440位で通過。 http://www.go-hero.net/jam/11/name/phyllo
今年もやってまいりました。登録忘れてて、ギリギリの参加登録。
ひっそりと参加。難しすぎて泣いた。
通過した。
予選落ち。507位、、、orz
いい勉強になった。0点。 基本的に英語の読解スピードが遅く、正確性が低くて悲しい。
なにこの難易度。 体調崩してたから参加するか迷ってたけど、結果的に参加してよかった。
問題 文字列strが与えられる。さらに、いくつか文字列boring[i]が与えられる。 文字列strの部分文字列の中で、boring[i]が含まれない最長の文字列の長さとその最初の文字の場所を答える。 考え方 しゃくとりっぽくやる。部分文字列の最初の位置begと最後+1の…
久しぶりすぎる参加。Div.1のレートが上がってしまったので、またDiv.2に。。
問題 ある2次元グリッドにW(白)かB(黒)が描かれてたものが与えられたとき、そのグリッドについて、(i,j)と(i,j+1)の色が、 (白,白) : なにもしない (黒,白) : その下の2つ(i+1,j)と(i+1,j+1)の色を黒にする (白,黒) : その下の2つ(i+1,j)と(i+1,j+1)の色を白…
やはり、夜中の参加は結構厳しい。 終了近くになって、ノーコンテスト通知。。。
動的計画法(DP)は強力な武器なので、ぜひマスターしたい、でも、うまく適用できない。。 そんな感じなので、今月はできる限りDPの問題を解いて、DP力を上げるようにがんばります。
大地震後、いろいろやることあったりで練習はしてたけどここに書いてませんでした。 SRM500に参加しようと思ったら人数がMAXに達してしまって参加できなかったです、、、 とりあえず、当面はDiv1維持を目標に参加します。
ひどい解き方をしたので。記録。
ホテルから参戦。
問題 ダーツをしている。このダーツは格子点にヒットすることが保障されている。的は正方形で、-100 2つの多角形が与えられ、どちらの多角形にも含まれるような格子点にダーツがヒットする確率を求める。すべての格子点は等確率でヒットする可能性がある。 …
問題 ある半径rの円上の整数点(x,y)がいくつあるか.x^2+y^2=nのとき,その個数は4*( d_1(n)-d_3(n) )になる.d_i(n)はnの約数を4で割ったもののうちで余りがiであるものの個数. 考え方 以下の通り。 http://d.hatena.ne.jp/phyllo_algo/20101106/128905508…
問題 チェスの勝ち負け表が与えられる。もし、3人のプレイヤー(a,b,c)が、 「aはbに勝ち、bはcに勝ち、cはaに勝っている」ような状況がある場合、あいまいであるという。 あいまいな(a,b,c)の組の数を返す。 考え方 やるだけ。 (a,b,c)の組について、もし上…
問題 長方形のボードの各セルに数字またはHが書いてある。 このボードを使ってゲームをする。ゲームのルールは、左上のセルにトークンを置いたところから始めるものとして、「今トークンがいる場所の数字の分だけ上下左右に動く」ことを繰り返す。 ボードの…
問題 長方形パネルがあり各セルには電球がついている。それぞれ0ならばoff、1ならばonをあらわす。 ある(x,y)の場所の電球のon/offを切り替えると、x以下、y以下のすべてのon/offが同時に切り替わってしまう。すべての電球をonにするために必要な最小切り替…
問題 宝物がある場所に埋まっている。 原点からスタートし、ある方向にある距離だけ移動、ある方向にある距離だけ移動、、、を繰り返していった最後の場所に埋まっている。 方向と距離がそれぞれ与えられる。最終地点の座標をこたえる。 考え方 EASTならば0.…
問題 AまたはBの文字をいくつか並べた文字列を考える。 もし、 AはcountA個を超えない BはcountB個を超えない 連続するAの部分文字列の長さはmaxAを超えない 連続するBの部分文字列の長さはmaxBを超えない を満たす文字列は美しい。それぞれのパラメータが与…
問題 3種類の色の長方形がいくつかある。それを順番においていく。必ずひとつ前の長方形の上にはみ出さないように重ねていくときに、最終的に上から見て赤、青、緑の色で一番見えてる面積が広いものの面積を返す。 考え方 やるだけ。 基本的に、その色の面積…
問題 T9と呼ばれる文字入力方式で、文字を入力する。 これは、アルファベットを入力するのに、 a,b,c->2 d,e,f->3 g,h,i->4 j,k,l->5 m,n,o->6 p,q,r,s->7 t,u,v->8 w,x,y,z->9 のように電話のキーパッドの数字1つで表す。このほかに「辞書の次」「新しい文…
問題 いくつかのパッケージをコンテナに詰めていく。 もし、現在のパッケージが現在のコンテナにフィットするならば、このコンテナに現在のパッケージを詰める。もしフィットしないならば、次のコンテナにフィットするかどうかを試す。 これを繰り返し、コン…