問題は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 迷路上に人がいる。人は自分の位置を知らない。うまく動作の列を定めてやることにより、人がどこにいても脱出できるようにせよ。人は外周のマスに達した時に脱出でき、一度脱出してしまったら後の動作は無視してよい。また移動先に壁がある場合は…