久しぶりのプログラミングコンテスト参加。 2完＋2半で48位。

問題 w*hのグリッドに分割される牧場があり、各セルには、何もいないか、1匹のアヒルがいる。牧場にはN匹のアヒルがいて、全てのアヒルを縦か横方向に1列に連続して並べたい。 しかし、座標(a,b)にいるアヒルを座標(c,d)に動かすためには、|a-c|+|b-d|秒かか…

問題 1x1のセルによって構成される長方形がある。各セルには、何もないか、コインが1枚のっている。 各ターンに、上下左右のどれか1方向に全てのコインを1セル分動かすことができる。 もし長方形の外側にでてしまったコインは消える。 正確にKコインだけを残…

問題 n匹のウサギちゃんがいて、何匹かのウサギちゃんだけが知っている2つの噂をすべてのウサギちゃんに広めたい。 ただし、各ウサギちゃんが伝えられるウサギちゃんは決まっており、さらに、1日に1つの噂しかその決まったウサギちゃんに広められない。 全て…

問題 立方体ブロックの塊が2つ与えられる。それぞれの塊は板のようになるようにくっついている。 2つの塊がブロックを共有しつつくっつくとき、全体でブロックがいくつになるか。 考え方 座標が100*100*100程度なので、各ポイントにブロックがあるかどうかを…

ooox-o--- 4完 258pt 34位 問題をしっかり読みましょう。

問題 二分木が与えられる。ある途中のノードが消された場合に、そのノードの子以下のノードすべてが削除される。どれか1つのノードが消される。このとき、残ったノードの中で葉であるノードの個数を答える。 考え方 まず葉となっているノードを見つける。 削…

問題 a^b^c^d^... mod mの値が何になるか？ 考え方 aとmが互いに素ならばオイラーのφ関数を使って、指数部分は「b^c^d^... mod φ(m)」とみなすことができる。これを繰り返していくことで、指数部分の計算をすることができる。(特に、指数部がφ(m)に等しいと…

問題 2次元平面の格子点(座標がどちらも整数の点)に木が植えてある。原点に立っていて、任意の方向を見ることができるが、木がある場合はその後ろにある木は見ることができない。範囲-a 考え方 対称性から第1象限の部分だけ考えて4倍すればよいことがわかる…

惨敗！！！Tシャツもらえない！！！

参加！！！ Tシャツがもらえるらしいのでがんばりたいけど、、、

問題 ある目盛だけ書かれた丸い時計がある。数字が書かれておらず、しかも時計が回転してしまっていて正確に何時何分かわからない。目盛は30度ごとについている。 適当な目盛を選んで、そこからの短針と長針までの角度が与えられる。あり得る時間で一番早い…

問題 ある整数Nとtargetが与えられる。 整数xをもしy*z==xとなるy,z(>=2)に分解できるとき、xはyとzに分解することができる。 整数Nを上記のように分解していったときに、常にtargetの数値が出てくる場合は"Yes"、そうでない場合は"No"を返せ。例えば、N=12,…

最近なんだかんだでさぼってたので、ちゃんと目標決めて頑張りたい。 とりあえず、今年中は以下を目標にしてがんばる。 できる限りコンテスト参加する SRMは無理じゃない時間ならできるかぎり参加の方向(調子なども含む) あんまり参加してなかったコンテスト…

oooo-x---- 400pt 42位 とあるセミナーがニコ生でも放送するという情報を直前に聞いたので、ニコ生見ながらまたーり参加。

問題 ある機械があり、leftボタン、rightボタン、enterボタンがついている。 ある文字列が与えられたとき、その文字列の一番左にカーソルがある。enterボタンを押すと、カーソルのある文字を出力し、出力した文字の部分は空白' 'に置き換わる。 文字列の辞書…

問題 動物園にNアニマルがいる．といってもウサギとネコの2種類しかいない．それぞれの種類において，彼らの身長はすべて異なる． キツネのJiroはウサギとネコの見分けがつけられない(←！)．そこで，すべてのアニマルに「あなたと同じ種類のアニマルで，あな…

問題 w*hのマスのそれぞれの高さが与えられる．そこに十分な量の雨が降ったとすると，各マスに溜まる水の総量はいくらか． 水は縦横4方向にのみ流れ，端のマスから外へは無限に水が流れていってしまう．例 16661 61116 16661 の場合は，真ん中付近の111の部…

問題 Fox Cielさんは1次元のマスの道路を左端から右端へ移動したい． 各マスには雨が降った場合泥だらけになる確率が与えられる．雨が降りました． Cielさんは1マス先か2マス先に移動することができ，できるだけ泥だらけのマスを避けたい． 両端のマスは必ず…

大敗北．たぶん，最近過去問演習さぼってたのと，ちゃんとTCO過去問やってなかったせい．

問題 各部屋は通路でつながっている。 2つの勢力があり、各部屋をそれぞれの勢力に割り振り、それぞれの勢力の部屋同士が通路でつながっていないようにしたい。(両勢力は少なくとも1つの部屋を所持する) しかし、部屋の数と通路はすでに建設中で、通路を壊す…

問題 Facebookでの「知ってるかもしれない人」featureの改善をする。 Facebookでは友達は対称であるが、推移性はない(AがBの友達ならばBはAの友達、でもAがBとCの友達だからといってBとCが友達とは限らない)。 今、n-friendという用語を定義する。2人が友達…

念願の黄色。

一応、直近の目標を達成したので、これまでの反省とこれからの目標を。

問題 いくつかの数字の配列が与えられる。これをk個のグループに分けたい。ただし、条件として「各グループの数字の分散の値の和が最小となるようなグループ分け」にしなければならない。 この時、分散の和が最小となるグループ分けの「分散の和」を返す。 …

問題 nのk-multifactorialをfac_k(n)とし、(n-χ*k)が0より大きいものの積と定義する。 例えば、14の3-multifactorialは14*11*8*5*2=12320となる。 より正確に書くと、 fac_k(n) = n if k>=n fac_k(n) = n*fac_k(n-k) if k nとkが与えられるので、fac_k(n)を…

問題 与えられた文字列の後ろにいくつかの文字を追加して回文を作りたい。最短となる回文を返せ。 考え方 文字列をひっくり返したものを元の文字列とずらして重なるかどうかを比較していって、元の文字列と同じ部分まで同じになったらひっくり返した文字列で…

いい問題。

もう、ぼろくそ。。。

問題 何人かのホットドック屋さんが通りで商売している。しかし、互いにDメートルは離れて商売したいと考えている。このとき、それぞれがDメートル離れるためには最低何秒かかるか。ホットドック屋さんは1秒で1メートル動けるとする。 ホットドック屋さんの…