問題文 : Lucky Array解法 : いつぞや誰かから「"Lucky Array"はセグメント木で解けるよ」 と聞いて, 問題を見つけたので挑戦したらそのLucky Array は別の問題だったらしい. セグメント木じゃ解けなさそうなんだよなあと思いつつ, 解法をみて勉強しようとし…

問題文 : More Queries to Array問題概要: 配列 $ \normalsize a$ が与えられるので, 区間 $ \normalsize [l,\ r] $ の値を $ \normalsize x$ に変更する. $ \normalsize \displaystyle \sum_{i = l}^{r} a_{i} \cdot (i - l + 1)^k$ (ただし $\normalsize 0…

問題文 : 中華料理解法 : 委員 a が 料理 b を食べるとき, 理事長の前にある料理はb - a となる. このような料理たちを通る最小手順を, すべてのありうる開始地点について考える問題である. これを考えるにあたって, 折り返しはたかだか1 回で良いことに注意…

問題文 : 住み心地解法 : もし, ランク X がある区画Aの住み心地の中央値になれば, ランクX + 1 が他のどの地点にあったとしても, 区画A での中央値はX となる. そこで, ランクについて二分探索を行い, 中央値になりうるかを確かめる. ランクの地点が影響を…

問題文 : 庭園解法 : O(n^3) で長方形列挙を行い, 上下左右から周長の最大値を記録してやれば良い. 長方形列挙は, y 軸の2 点はO(H^2) で決め打ち, x 軸については尺取り法でO(W) で求めれば良い.計算量はO(WH^2) だが, 制限時間ギリギリなので結構大変.コー…

問題文 : 平均数列解法 : 数列の初項を決めると, 残りの数列の値も一意に定まる. 更に, 初項k の平均数列が作れなければ, 初項をk + 1 とする平均数列(またはk - 1 とする平均数列, あるいは両方) が作れないことが分かる. ゆえに, この数列の初項の値は連続…

問題文 : SALT TREE XV解法 : (qnighy さんのものをチラッと見てしまったので, 考えながら書いた所をまとめる.)まず, ある状態から, 辺の数が0 で頂点の数が0 に出来れば自分の勝利であることを確認する. また, 辺の数が0 の状態への遷移は, 頂点が1 個の時…

問題文 : しりとり解法 : 各辺を1 度だけ通るような探索をしてしまうと, 辺の数が多すぎるためうまく探索ができない. そこで, 00 ~ 99を頂点としたグラフを考え, その間に辺を貼ることを考える.このグラフがオイラーグラフであればしりとりをすることが可能…

問題文 : リンゴの出荷解法 : 濃さD のリンゴを, 区間[D, D + B + 1)に対応させて,・ある区間に値x を足す ・ある区間の和を求めることが出来れば, 出荷依頼に高速に答えることができる. これは, Starry Sky 木を改造することで実現することが可能である.た…

問題文 : 魚解法 : 初めに, 尺取り法で, 起こりうる魚の組み合わせ(赤a 匹, 緑b 匹, 青c 匹 以下の組み合わせなら全て作成可能である) というものを列挙する. これをa * b * c の直方体として扱う. その後に, セグメント木で体積を, 以下の要領で求めていく.…

問題文 : 直線解法 :オイラーの多面体定理です."V(頂点数) - E(辺数) + F(面数) = D(次元) - 1"が成立するので, D=2から, F = E + 1 - V が求まります. EだったりV だったりは入力から簡単にもとまるので, 愚直に計算しても O(N^2 log N) で解を得ることが出…

問題文 : 最悪の記者解法 : トポロジカルソートをすればよい. トポロジカル順序が複数あるかどうかは, 隣り合う2 つの順位について, 互いへ直接たどり着けるかどうかを判定すれば良い. (隣り合う順位へ直接辿りつけないのであれば, その2 つを仲介する順位が…

問題文 : 報告解法 :まず, 問題文の例を解析する. 報告先でサイクルになっている頂点達について, サイクル内の頂点v に仕事の報告が来れば, 必ず他の頂点でも仕事の報告が来ることがわかるので, 閉路を潰す.次に, 閉路を潰して出来たグラフの逆辺からなるグ…

記載されている数値は, (日付を除いて) すべて常用対数値です. 試験日 科目名 目標点 予想点 実際の点数 2/ 8(金) 生物 2.000 2.000 1.98227123304 実用英語 2.000 2.000 2.000 2/12(火) 国語Ⅰ 2.000 2.000 2.000 線形代数 2.000 2.000 2.000 スポーツ実技Ⅰ …

2 / 9 (Sat.) から 2 / 10 (Sun.) にわたって開催されたJOI (日本情報オリンピック) の参加記を書きます. 2 / 8 (Fri.), Okinawa ・本選開催前日だというのに25 時まで起床する. ・8 時30 分からある生物の試験に恐れ慄きながら就寝する.・生物の試験で(たぶ…

問題文 : 忍者の派遣解法 : 各頂点でpriority queueを持ち, dfs を行い, 給料のコストが大きい頂点から予算を超える分だけqueueから取り除く.これだけではO(N * NlogN) = O(N^2 log N) の計算量となってしまうが, 頂点を併合する際に, 短い方のqueueを併合す…

問題文 : Query on a tree II解法 :複数テストケースなので初期化する位置に気をつけないと死んでしまう問題 (ぼく死んでしまいました).距離を求めるところはeuler-tourっぽくやるのも, doubling でやるのもよしです. k 番目の頂点は, 根からの深さとlca(u, …

問題文 : Distance Queries解法 : Highwayの, 渋滞情報変更が無いだけのSimple LCAの問題.(その前に最小全域木化しなければならないが) Euler-Tour をしたが, これはDoubling でも普通に解けそう.全体でO((N+K)logN) くらいの計算量となる. 何も見ないで書け…

問題文 : 夜警解法 :登場する点のうち,・警備員のいる点 ・建物の点を頂点としたグラフを作る. この際に, 建物の辺または対角線と交わっている時は辺を貼らないようにする.これが出来れば, あとはダイクストラ法を各点に行うだけである.コード : #include <cstdio> #</cstdio>…

問題文 : オリエンテーリング解法 : 同じ高さの点が無いので, 前もって標高順で, チェックポイントについてトポロジカルソートを行う. その後は全点対の最短経路をO(N^2logN)程度で求め, dp[i][j] : 1人目がチェックポイントi, 2人目がチェックポイントj に…

友達に勉強を教えながら, ゆったり2007を解いてみました. 4 -> 3 -> 2 -> 1 -> 5 の順で解きました. 4 が一番簡単なんだよなあ... 1時間半くらい余らせて終了.1. 碁石並べシミュレーションを行う. オセロっぽい操作を行う. #include <cstdio> #include <cstring> #include <algorithm> #i</algorithm></cstring></cstdio>…