線形代数やらないといけないと思いつつやってない。 問題 n*n行列が与えられる。そのなかからいくつかの要素を以下の制約を満たすように選ぶ。 各行から選ばれた要素の数が奇数個となる 各列から選ばれた要素の数も奇数個となる すべての選ばれた要素の積が…

最後の詰めが甘い。 問題 頂点数nの有向グラフが与えられる。そのグラフ上で長さLのウォークの数が O(L^K) に漸近するとしたとき、Kとして取りうる最小の値を求めよ。 指数オーダなど O(L^K) では表せない場合は-1。 n

問題 2次元上のn*mセルからなる盤面にアリスとボブのトークンが1つずつ配置されている。盤面には壁があり、壁でないセルの隣接関係をグラフにすると木になっている。 アリスとボブが交互にトークンを隣接したセルに移動させる。もしアリスとボブのトークンが…

問題 n個の部屋からなるダンジョンがある。i番目の部屋に入るためには赤い鍵がdoorR[i]個と緑色の鍵がdoorG[i]個必要となる。ただし、白い色のカギがある場合はそれを赤い鍵または緑色の鍵の代わりとして使用することができる。また、扉を開けるのに使用した…

問題 01のみからなる文字列Sと、先の文字列の長さ以下の整数Mが与えられる。 ある文字列の先頭|S|-M文字分と終端|S|-M文字分が等しい場合、その文字列はrotator sequenceであるという。 与えられた文字列に対して、以下のいずれかの操作を適用することができ…

問題 n個の歯車があり、それらはRGBいずれかの色を持っている。また、それぞれのギアが互いにかみ合っているかどうかを示すグラフも与えられる。このとき、かみ合っている2つの歯車は互いに反対方向に回転する。 すべての同じ色の歯車が同じ方向に回転できる…

http://www.topcoder.com/longcontest/stats/?module=ViewOverview&rd=14495 引っ越しとかで終盤手を付けられなかったけど参加してました。 17位でレート上昇。と言っても前回の下がり幅分回収できるわけもなくまだ青いまま。

文字通りの三日坊主で存在を忘れつつあったけど久々に。 225.83+195.87=421.15 / 314位 レーティングは 1623→1648 で順調にHighest更新継続中。

とりあえず定期的に書けるネタとしてTopCoderのSRMとかCodeforcesの記録と反省でも書いていこうかと。 というわけでSRM479も参加してました。 Div.1でEASYだけ解いて123.85点。 Challengeは突けるところを見つけたもののデータ入力に手間取ってる間に先を越…