2012-01-01から1ヶ月間の記事一覧
300 N曲あって、P曲分の長さのプレイリストを作る。プレイリストには各曲1回以上含まれねばならず、また同じ曲を流す場合は間にM曲以上他の曲がないといけない。何通りのプレイリストが存在するかmodで計算せよ。見た瞬間「うげっ」ってなったが「各曲1回以…
2805 Pegs 5*5のペグソリティアの盤面がある。操作の後、盤面に残るペグの数を最小化せよ。BFS 3493 Chessboard Puzzle N*Mの盤面にそれぞれ数が書かれている。盤面の各マスを黒か白で塗る。隣り合っている2マスの色が異なる時、その2マスの数の積だけ点が入…
1650 Integer Approximation 分母分子がL以下の分数で、Aに最も近いものを求めよ。Farey数列やるだけ 3157 Java vs C++ JavaかC++の識別子命名規則で識別子が与えられるので、互いに変換せよ。やるだけ 3683 Priest John's Busiest Day 結婚式がいくつかある…
3682 King Arthur's Birthday Celebration 王様の誕生日にお祝いを始めて、コインがK回目に表を返すまで何日でも続ける。i日目には2i-1の金額を使う。日数と費用の期待値を求めよ。式を立てて計算する 2594 Treasure Exploration 閉路のない有向グラフにおい…
3417 Network 木構造にM本の辺を加えたグラフから2本の辺を取り去って、グラフを非連結にしたい。取り去る辺は、1本は最初からある木の辺で、もう1本は加えられた辺でないといけない。何通りの方法があるか。取り去る辺のうち、木の中の辺の方に注目すると、…
3375 Network Connection ネットワークインタフェースと、パソコンをつなぐ。それぞれは数直線上にある。すべてのパソコンをいずれかのインタフェースにつなぎたい。複数のパソコンにつながれるインタフェースがあってはいけない。ケーブル長の和を最小化せ…
2752 Seek the Name, Seek the Fame 与えられた文字列のprefixにもsuffixにもなっているような文字列の長さをすべて求めよ。まずKMPテーブルを作成する。すると、なぜか次のアルゴリズムが正解を返す。 1. p = L とする。 2. p > 0 である限り、p を解として…
TopCoder, PKU などで頻出の英単語です。 単語の意味は、競技プログラミングをするのに十分な程度しか載せていません。
2432 Around the world 地球上の何点かにFJの友人がいる。それぞれの友人はある緯度の位置に住んでいる。いくつかの友人のペアの間に、その間を結ぶ航空便が存在する。航空便は、移動する緯度が少ない方の向きで移動する。友人1の場所から始めて、地球一周し…
2778 DNA Sequence DNAはA, T, G, Cからなる列である。長さnのDNAで、病気因子となるDNAの部分を含まないようなものの数 mod 100000を求めよ。Aho-Corasickを用いて遷移行列を作り、バイナリ法で累乗する。
不快すぎる 250 「王の名前 ローマ数字」がたくさん与えられるので、王の名前順にソートし、同じときはローマ数字順でソートするというソートをせよ。ローマ数字を計算するのが面倒。 600 わけのわからないアルゴリズムを実行したときにある処理のステップ数…
3180 The Cow Prom 牛がたくさんいて、いくつかのペアの間にひもがある。牛のいくつのグループが適切なダンスをできるか？適切なダンスは、そのグループのすべての牛がロープを引っ張って同じ方向に回れるということである。英語を読み、強連結成分分解する…
1987 Distance Statistics Treeと同じ 1563 The Snail 木登りをしている人がいる。昼間は登る。夜は少し下がる。登れる高さは日に日に短くなっていく。木のてっぺんより高いところに到達するか、地面より低いところについてしまうまでにかかる日数を求めよ。…
4018 High security N個のパスワードが与えられる。パスワードは5文字で、各文字はA-Za-z0-9のどれかである。0例えば1,3,5文字目が同じであるような組の数は、1,3,5文字目だけを取り出してソートすることでO(N log N)で求められる。同様にして、すべての位置…
3159 Candies キャンディーを幼稚園の子供たちで分配する。いくつかの子供の間に、「BはAよりc個以上多くのキャンディーをもらわなかった」という関係がある。子供Nは子供1より最大何個のキャンディーを多くもらえたか。（キャンディーは無限にあるものとす…
2949 Word Rings word ringを、「いくつかの文字列で、i番目の文字列の終わりの2文字がi+1番目の文字列の最初の2文字に一致する（また、最後の文字列の終わりの2文字が最初の文字列の最初の2文字に一致する）ような文字列の列」と定義する。文字列の集まりが…
