Algorithm
便乗。凡例 ●は本番で解いた(満点を取った)問題 ▲は本番で部分点しか取れなかった問題 ★は本番で部分点しか取れなかったoutput only ○は本番以外で解いたもの △は本番以外で部分点しか取れなかった問題 ☆は本番以外で部分点しか取れなかったoutput only 無印…
1778 All Discs Considered 2枚のDVDにインストールすべきソフトウェアが入っているが、依存関係があり、ある部分をインストールする前に他の部分をインストールしなければならない、などが定まっている。DVDドライブが空の状態から始めて、すべての部分をイ…
3261 Milk Patterns N個の整数からなる数列がある。数列にK回以上現れる連続したパターンのうち最長のものの長さを求めよ。suffix array と lcp を求めると、lcp中において「K-1個の連続した部分の最小値」の最大値が答えになる。 1743 Musical Theme ある音…
2774 Long Long Message 2つの文字列の最長共通部分文字列の長さを求めよ。2つの文字列をa, bとして、a $ b に対してsuffix arrayとlcpを求める。 suffix arrayの中で、aからの部分列とbからの部分列が隣り合っている場所があったとき、そのlcpを記録し、そ…
JMO 他の予選免除者が軒並み4完している中3完しかできず死亡 1: 適当に中線を取ると平行が示せて平行と垂直を使うと垂直が示せる 2: 適当にやるとf(x)の形がすぐに限定できて、適当に条件に代入してf(x)を一意に限定できる。多分「これはみたす」ぐらいは書…
2886 Who Gets the Most Candies? N人の子供が円状に並んでいる。K番目の子供から始めて、「その子供が自分の数を言い、その子供は円から抜けて、言った数に応じて次の子供を決めてその子供から同じ事を繰り返す」という行為を1人になるまで行う。i番目に抜…
こんな言語があったらいいなーっていう妄想です C++並の速度が出る 1からコンパイラを書いてこれを実現するのはかなり大変でしょうが、C++に変換するトランスレータを作成すれば不可能ではありません。 Union Findが標準ライブラリに含まれる Union Findは簡…
3667 Hotel N部屋があるホテルがあり、各部屋1〜Nの番号がついている。最初ホテルは全部屋空室である。「D人の客を泊める」クエリと、「ある範囲の部屋をすべて空室にする」クエリを処理せよ。客を泊めるときは、D人が連続する番号の部屋に泊まるようにし、…
2433 Landscaping ある地面の地形が与えられる。今、地面の極大部分の数が高々K個になるように、地面を削りとりたい。削りとるべき最小の土の量を求めよ。up[i][j][k] : i番目まで見ていて、現在の高さj、山の右端はk回出てきて、絶賛上昇中 dw[i][j][k] : i…
3204 Ikki's Story I - Road Reconstruction N個の街とそれらを結ぶM本の一方通行の道がある。それぞれの道には容量が決まっている。街0から街N-1まで移動する容量を考え、道を再建したときに容量が増加するような道は何本あるか。最大流で解を求めた後、残…
3621 Sightseeing Cows ある街にはいくつかのランドマークがあり、ランドマーク同士を結ぶ道がいくつかある。道は一方通行で、それぞれ通過するのにかかる時間が決まっている。ランドマークごとに、それを見た時の「うれしさ」が決まっている。今、牛がある…
1991 Turning in Homework C個の宿題を提出しないといけない。それぞれの宿題について、提出する位置と、提出できる時間が決まっている。最初は位置0にいて、最後は位置Bにいたい。時間を最小化せよ。まだ訪れていない左端と右端をキーにDP 2983 Is the Info…
2644 Maze 迷路上に人がいる。人は自分の位置を知らない。うまく動作の列を定めてやることにより、人がどこにいても脱出できるようにせよ。人は外周のマスに達した時に脱出でき、一度脱出してしまったら後の動作は無視してよい。また移動先に壁がある場合は…
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を用いて遷移行列を作り、バイナリ法で累乗する。
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文字に一致する）ような文字列の列」と定義する。文字列の集まりが…
2964 Tourist たぶん某国のぱないアルゴリズマーは関係ない。マップ上で、左上の点から右下の点まで行ってまた帰ってくる。いくつかのマスは通れない。いくつかのマスには面白いものがある。上下左右に動けるが、経路は最短でないといけない。面白いマスをで…
3327 Cut the Cake ケーキの切断手順が与えられるからシミュレートせよ。やるだけ。vector > を使うと簡単。 1408 Fishnet 網の線が与えられるので、最も大きい網の目の大きさを求めよ。やるだけ。面倒なので魔法少女ライブラリで適当にほげほげした。 1466 …
