2012年の情報オリンピック予選の6問目。当時解けなかったのは当然としても、今見ても結構つらい問題で、5年越しにようやくACしたのでなんとなくブログに書いておく。 問題文 まあ日本語なので読みましょう お土産購入計画 | Aizu Online Judge 解法 流石にbi…

TL;DR的にはタイトルまんまです。 CodeForcesでまあこんな感じで激冷えしてしまったんですが、 原因の一端に、自分がコンパイラオプションを正しく認識していなかった事もあった上、ほとんど日本語でも英語でも、似たような現象に悩まされてそうな人がいなか…

大学生なのでデータ構造とアルゴリズムという授業を取っているんですが、今まで自分がKMP法だと思い込んでいたものがMP法だった上、ネット上の記事が無限にバラバラなのでメモしておく。 MP法 MP法はMorris-Pratt algorithmと呼ばれるもので、Knuthが登場し…

dpの遷移が複雑すぎるだろ。 問題概要 縦109, 横109の合計1018個のマス目があり、上からi番目, 左からj番目のマス目を(i, j)と表す。マス目に以下のルールで数を書き込んでいく: マス(i, j)には、マス{(x, j) | 1 ≦ x < i}とマス{(i, y) | 1 ≦ y < j}に書か…

みんなになれなかった。 問題概要 読んで: D: 工場 - 「みんなのプロコン」 | AtCoder 解法 正攻法はそのままこのクエリを実現しようとすれば結合則成り立つので値を2,3個持ってくださいというやつみたいです(たしかにね。)。 クエリの時系列と日数の時系列…