昨日の問題が簡単に見えるレベル 問題の内容は省略します。

多分 JOI 史上最難問セット。 満点取りに行こうとしましたが、90+100+100だったので（かつ他の人より高い点が得られたので）よしとします。

これだけはテストできないので、思いついた解法を書きます。 解法 木に対して「辺を取り除く」「頂点とそれにつながる辺を取り除く」という操作は、元の木を分解していくつかの新しい木を生み出す操作である。よって、木の Grundy 数を求めればよい。 N >= 1…

Contest はやっぱり結構難しいと思う… 解法 hogloid がO(N log N) で解いたらしいが知らない。 下のコードは O(N^2)。 まず、各チームを「2人とも点数分かってる」「1人しか分かってない」「2人とも分かってない」という基準で、A群、B群、C群に分類する。 …

Belt はかなり面倒な幾何に見えますが、実は実装は比較的楽に書けます。 解法 動く歩道から距離D以下の範囲にある家を最大化したい。「動く歩道」を考えるのは面倒なので、幅2Dの帯を考え、その帯を動かして考える。すると、帯を平行移動することにより、帯…

93位。 A 兵士がN人いて、兵士のための服がM枚ある。それぞれ大きさが決まっていて、大きさがAの兵士は大きさが [A-X, A+Y] の範囲の服を着ることができる。兵士-服の最適な割り当て（最も多くの兵士が服を得ることができる）を求めよ。greedy やるだけで通…

問題 係数が mod 2 の世界で、N (高々 49)次の多項式の M (高々 1016) 乗の K 乗の係数を求めよ。 解法 まず、多項式の M 乗は結構大変なことになりうるので、大変なことにならない状態を考える。 多項式の 2 乗を考えると、mod 2 の世界では各項の指数が 2 …

受験おわったらしたいこと。でもまだまだ先。少なくとも１年。１年で終わらせたい。終わらせないといけない。 回路で遊ぶ。特に AVR でもっと遊ぶ。 プログラミング。もっと強力な箱詰めソルバーとか面白そう。あとは、スリザーリンクをもっと改良するとか。…

問題はJMOのページにあります。 試験中2時間ぐらい考える時間あったのに解けなかったが、よく考えるとすごい簡単に記述できる解答があった…

便乗。凡例 ●は本番で解いた(満点を取った)問題 ▲は本番で部分点しか取れなかった問題 ★は本番で部分点しか取れなかった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 などで頻出の英単語です。 単語の意味は、競技プログラミングをするのに十分な程度しか載せていません。