今年は Algorithm タグがつきました（後述）。 競技について 今年は分業をしました。1, 2, 3 を kitayuta が解いて、4 以降を semiexp が解くようにしました。最初のうちは 1, 2, 3 と 4 以降を交代で実装して、途中で冷えたら交代して紙デバッグするように…

かきかけです 9/22 直前合宿 バスに乗って空港へ出発 結局集合の 1 時間くらい前に着く。1 時間後のバスでよかった気がする 合宿では、いくつかの問題の解説があった りんごさんによる Sails の解説がぱなかった 9/23 Arrival Day 成田→フランクフルト→ミラ…

引退

ひさしぶりに SRM した 250 一瞬「えっ＞＜」ってなるもちょっと書きだしてみたら（根拠もなしに）N≡0,2 mod 3 のときは全色同じずつ、N≡1 のときは 1 色だけ多くなるだろーって思って二分探索した 500 長方形 2 個選ぶ典型問題。 長方形 O(N^4) 通り全部調…

（この記事は書きかけです）銀（Plata）でした。 7/7 成田→（オクラホマシティ）→ダラス/フォートワース→ 横浜で、関東の JPN 2 人と合流 NEX に乗り、品川で JPN 全員が集まる 空港に着いて、直前学習会のあと出発。JPN らは席が近くだった DFW で乗り継ぎ…

writer やってました。 Div2 Easy(250) AkariDaisukiDiv2 f(X) = Waai + X + Akari + X + Daisuki なる string -> string の関数を考える時、S = f(X) なる (Waai, Akari, Daisuki, X) の組の数を求めよ。問題名とかいろいろおかしいですが(ivan さんに「"Wa…

今更解けた。悲しい

想定解法は「永続平衡二分木」を使うものですが、そんなもの一般人には書けません。そこで、一般人にも使える道具だけを使って点数を取りに行く試みをしました。

Copy and Paste むずすぎ・・・ 2完ゲーッ

昨日よりましになった。リス（3完）

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

多分 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 ある街にはいくつかのランドマークがあり、ランドマーク同士を結ぶ道がいくつかある。道は一方通行で、それぞれ通過するのにかかる時間が決まっている。ランドマークごとに、それを見た時の「うれしさ」が決まっている。今、牛がある…