鬱度高いの書きます. それぞれの問題について, 解けたか解けなかったのか書いても結局本番で出来なかったので書くつもりありません. (どの日の問題もおもしろかったです.)↓↓↓↓ 1 日目であまり思うような点数がとれず, 翌日からは頑張ろう, と最初は思ってい…

問題文 : Josephus Permutation解法 :アルゴリズムイントロダクションに乗っていた問題を実際にコードに起こしたもの. ヨセフスの芋の軌跡をたどったものを出力する問題. 愚直にm % n 個先までたどる線形リストなどではO(n^2) となり. TLE するだろう. そこ…

問題文 : 山の遊園地問題概要 (問題文読みづらいので) : 長さ N の数列が与えられる. 次のクエリに答えよ. 区間 [l, r] の値を v に更新する. [I l r v] [1, x] の値がはじめてv を越えるようなx を求める. [Q v] 解法 :遅延評価をするセグメント木を用いる.…

問題文 : 色紙解法 :各矩形のとりうる領域の最大値を計算し, その上にある別の色紙から自分に向かった辺をはったグラフを考える. このトポロジカル順序が答えとなる. 計算量は, 矩形の操作にO(NWH) 時間, トポロジカルソートにO(N) 時間で, 全体としてO(NWH)…

問題文 : 最古の遺跡2解法 :dp[i][j] : 辺ij を最後に使った時の頂点数の最大値, とする. このとき, 以下のような図を考える.ここで, 現在赤の辺から水色の辺に遷移しようと考えていたとすると, 赤の辺と水色の辺のなす角θが180 度以下であれば, dp[水色の辺…

kyuri さんや tozan さんに便乗です.○…ジャッジで満点を確認した. △(点数)… ジャッジで(点数)点を確認した. ×…ジャッジで0 点だった. ー…未着手. 思考中. 2007 問題名 解いたか 記事 Score ○ Factorial △(80) Mall ○ Building ○ Fermat △(40) Salt ○ Anagram…

問題文 : One解法 :放物線の長さは, で求まる. (ここで, とおいた.)交点を列挙してこの関数を適用していけば良い. 誤差に気をつけて計算すべし...コード : #include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <algorithm> using namespace std; const long double EPS =</algorithm></vector></cmath></cstring></cstdio>…

問題文 : Little Elephants and Broken Sorting解法 :dp[i][j] : 場所i, j の数をA[i], A[j] として, A[i] > A[j] となる確率, とすると,この配列の初期値はA[i] > A[j] なら 1, A[i] k 回目において,1 / 2 の確率でa[k] 番めの数とb[k] 番目の数が交換され…

問題文 : バブルソート解法 :与えられた配列Aを, (添字, 値) を座標として座標平面にプロットする. すると, この問題は長方形の中にできるだけ多くの数を含むようにするにはどうすれば良いかを考える問題となる.愚直に数え上げを行えばこれはO(N^2) 時間で最…

問題文 : コンテスト解法 : まずは, 国C の得点を最大化する. これは, 得点が不明なチームの降順に点数を2 つ(若しくは足りない分)取れば良い.次に, 国C の順位を最大化する. これは, 二分探索を行なって位置を定めてやれば良い. (X 位になれる -> X + 1 位…

問題文 : 倉庫番解法 : 「倉庫番の逆」を考える. すなわち, 目標地点から箱を引っ張りまわすBFS を考える. 箱の置き方がO(MN) 個, 隣接する頂点がたかだか4 個であるため, 状態数はO(MN) である.各状態に遷移したら, 答えには連結成分の大きさを足してやれば…

問題文 : POLICIJA問題概要 :無向連結グラフが与えられる. 以下のようなクエリに答えよ. 頂点 $u, v$ と辺 $e$ に対し, $e$ を取り除いたとき $u$ から $v$ へ辿り着けるか？ 頂点 $u,\ v,\ w$ に対し, $w$ を取り除いたとき $u$ から $v$ へ辿り着けるか？ …

問題文 : 活字印刷機解法 : Trie 木上の探索を行う. 最も長い文字を最後にたどれば, その文字の文の型を回収しなくていいため最短ですべての文字を打ち終えることが出来る. (他の文字はどのみち回収しないといけないため). コード : #include <cstdio> #include <cstdlib> #in</cstdlib></cstdio>…

問題文 : しょうじききつね と うそつきにんげん解法 : はじめに"正直者の人数" をもととしたグループを作ると, それが正しい可能性のあるグループは高々O(√N) 個しかできない. 明らかに嘘を付いている人物がいれば, その人を使って正直者かどうかの判定を行…