[JOI合宿]2011-Day1:Banner

問題文 : こちら

思ったとおりに実装してAC.

実装 15 分 + Debug 1 分 (string.hの宣言を忘れている & 答えのオーバーフロー修正.)

愚直解として, 辺を4つ決めるO((WH)^2)の解が考えられる. これは40 %解法となる.

ここで, 長方形の縦の辺を全て決めると (O(H^2)), 横の辺を全て走査し(O(W)), 横の辺に含まれている色を分類することで, 数学的に旗の組み合わせを求めることができる. (O(1))
故に, O(W^2H)で, 100 % の得点を得ることができる.

続きを読む

集合と行列

中々面白い問題でした. 発想力を高めたいのです.
問題文を載せるので, 皆さんも是非挑戦してくださいー.

続きを読む

[JOI合宿]2007-Day1:Mall

二次元の累積和を取る問題でした.
-1の土地は10^8で初期化しておきました.

実装 10 分 + Debug 0 分 (1発AC)

続きを読む

合成写像と恒等写像

むむむ, 受験数学に近い問題でした.
うまく証明できていると良いのですが...

続きを読む

[JOI合宿]2010-Day1:Stairs

尺取り法＋DPの問題でした.
O(N)の解法です～.

眠いので詳しい解法は後日... (最近こればっかり言っていて辛い...)

続きを読む

[未]AOJ 0553: Dungeon

JOIボリューム, この問題が終わればチェックメイトなのですが, 中々オーダーが改善できません...

30点解法です. 満点解法ではないので詳しい解法は述べませんが, 泉の最小使用回数をminAとすると, O(N + minA* (NlogN))くらいです.
minAが10^4くらいになると死にます. (最大ケースでは, minA >= 10^9なのでこの解法自体ダメなのかもしれない.)

もう少し頑張ると O(N + minA * (log^2N))にできる可能性が存在しますが, 現時点では厳しそうです (そもそも満点は得れ無さそうなオーダーでかなしい).

想定解はO(NlogN)くらいなのでしょうか...

続きを読む

2006年JOI予選模擬問5

昔のJOIは多倍長好きだったんですかね...

問題文を読むと, 求める答えが n H (r - mn) = (n + r - mn - 1) C (r - mn)であることはあきらか.
あとは, nCk = n! / k!(n - k)!　を実直に計算します. (バグたくさんで悲しみに包まれました.)

頭の悪い多倍長なのでAOJでは当然間に合いません. ((n, m, r) = (10000, 0, 10000)ケースで20秒くらいかかります)

続きを読む

空間の図形と空間ベクトル

テスト勉強がてら、去年の線形代数の中間試験の最後の問題を解いてみました.
空間ベクトルと図形が絡んだ問題には物凄く苦手意識があったのですが、この問題を解くことによって自信が付きました. 割と基礎的な問題かもしれませんが.

僕の解答を記すので, 皆さんも以下の問題にチャレンジしてみてくださいー！ (確認した所, 解答は全て合っているようです.)

続きを読む

AOJ 0575: Festivals in JOI Kingdom

Dijkstra(O(M log N)して、Maximum Spanning Treeを作ってO(M log N), Q個のクエリにLCAを使って応答をします(O(QlogN)).

全体のオーダーはO((M+Q)logN)くらいです. 詳しい解説はiwi先生のスライドなどを参考にしてください (多分想定解法そのままなので).

続きを読む

AOJ 0552: Exposition

難しすぎる... かなり時間かけました.
前回の記事の通り, 点対を実際にグループ分けします.
素朴な方法では, グループ分けがO(N^2)になってしまいますが, このグループ分けをO (N)に横着しています.
具体的には, 今日書いた

|x1 - x2| + |y1 - y2| = max(|x1 + y1 - (x2 + y2)|, |x1 - y1 - (x1 - y2)|) という式を使って計算をしています.

グループ分けの基準とする距離をKと仮定します.
グループ分けが前者で出来たと仮定してグループ分けしたものと, グループ分けが後者で出来たと仮定してグループ分けしたものについて、矛盾がなければ距離Kでグループ分けが出来ます.
Kでグループ分けできれば, K + 1でもグループ分けができるので、二分探索を行えます.

続きを読む