無事終了。大学構内を少し迷ったけどなんとか時間通り到着。 内容は「劣モジュラ関数の最大化」だった。 午前の部はかなり余裕があったのだが、午後はいっぱいいっぱいだった。 先生の説明が、かなりわかりやすかったので何とかついて行けた。 今から一人演…

今日は早めに京都入りして観光。 京都の暑さは、今の関東に比べても暑い。 あと外国から観光にきてる人が多いね。

平面グラフにおいて、subgraph isomorphism problem(平面グラフGと固定したグラフHにおいて, GはHと同型な部分グラフを(いくつ)含むか?)は線形時間で解ける。 これは、Hのサイズをパラメータとして、FPTになるという寸法だ。 アルゴリズムの中で、tree decom…

こたつを片付けた。 と言っても、こたつ布団を片付けただけ

どうかAcceptしますように...

いまさらだが、500問突破

なぜこうも忙しい時に熱がでるのだ

京都はやっぱり遠い

京都は意外と近い

とりあえず良い結果になったようなので良かった。 明らかに私の貢献度が低いので、何とかしなくては...

・英語 ・ジャーナル用 ・いろいろな分野に触れる ・新しいテーマを見つける2日1冊ペースで論文を読む。 挫折するかもしれないが...

とりあえず提出。

1580 String Matching 愚直にマッチ 1581 A Contesting Decision 愚直にスコア計算

1026 Cipher 置換をk回適用して、文字列を暗号化する。TLEが多いのでそのままやってはおそらくダメ。 置換の巡回の長さを求めておいて、kを巡回の長さで割った余りだけ置換を適用する。 1059 Chutes and Ladders すごろくのシミュレーション。 そのままやる…

3349 Snowflake Snow Snowflakes hash。java.util.ScannerではTLEだったので、 自分で書いたら通った 3318 Matrix Multiplication 行列検算。乱択アルゴリズムでよくある問題。 AB=Cにおいて各要素をランダムに選んで作ったベクトルxを右からかけると、 ABx=…

Bidimensionality Theoryを勉強中。 ものすごく大まかには理解した(?)ので、これから少し細かく勉強していく。

3130 How I Mathematician Wonder What You Are! 凸包を作って、もとの多角形の直線で切り取っていき、多角形が残るかどうか答える 3278 Catch That Cow BFSで通った 3224 Go for Lab Cup! 3のが一番多い行を求めるだけ

論文もあとちょいだけど、英語をちゃんと見直さないとなぁ

今日はPKUが昼ごろまでしんでた。 2704 Pascal's Travels DP。左上から右下に斜めに表を更新していく。 board[i][j] = kならtable[i+k][j]とtable[i][j+k]にtable[i][j]の値を足す 2756 Autumn is a Genius BigInteger 2894 Ancient Keyboard カウントするだ…

2626 Chess DP。table[i][j][k]にi人目までで白にj人、黒にk人割り振った時の 最大値を記憶していくと考えると、 table[i][j][k]=max(table[i-1][j][k], table[i-1][j-1][k] + white[i-1], table[i-1][j][k-1] + black[i-1])となる 2607 Fire Station 消防署…

2507 Crossed ladders 幅が決まると交点の高さが決まり、かつ単調なので二分探索。 2572 Hard to Believe, but True! ひっくり返して足すだけ 2576 Tug of War DP。table[i][j]にi人で重さjが作れるか格納する。

簡単な問題しかやってないけど、今日から解いた問題でも書いていこうかな。 2487 Stamps ソートしてたくさん持っている人から借りてくる 2413 How many Fibs? BigIntegerで実際に数える 2436 Disease Management 許容するような病気の部分集合を実際に作って…

ボロボロでしたね