keyword BIT 木 定数倍最適化 C++ Java 問題概要 ノード数N( 解法 根から行きがけ順に番号を降ると、子孫のノードには連続する範囲の整数が割り振られる。したがって、後はBITで区間和を取り出してやれば良い。計算量O(N + M*log N)。 付記 TLEがアホみたい…

keyword 空間幾何 球座標 C 問題概要 球面上に点がN( 解法 全探索で間に合う。球面上での距離の求め方は、内積とacos使ってなす角を求めてやればよい。 感想 度数法と弧度法間違えるという典型的な間違いにずっと気がつかなかった。

keyword 全探索 C++ 問題概要 1辺1の立方体がS個あり、1辺L( 解法 全部の体積をVとすると答えの範囲は下限がV, 上限がV+L*L-1。この上限はBを一列に並べたものから分かる。区間の幅がL*Lしかないので答えに関して全探索する。答えを決め打ちしてやると、直方…

問題概要 色を示す文字列が複数与えられる。それらを使って隣り合う色が異なるようにサイコロの面を塗れるか判定する問題。 解法 場合分けして手で解ける。 感想 手で解くのは遅いし、抜けもよく起こるのであまり好ましくない。でもこの問題は結局綺麗な解法…

問題概要 フラクタルな図形を書く問題。 解法 実装するだけ。ただし、もとのサイズが1の場合は、深さが大きい値の可能性を考慮するべき。 感想 入力の読み込みとか改行コードとかでミスを大量に重ねた。いもす先生に教わったけど、scanf("[^\n]",buf);とかを…

keyword 動的計画法 経路復元 C++ 問題概要 よくある携帯電話の入力方式の問題。打ち込んだ数字列と辞書が与えられるのでマッチングする文章を全て出力する問題。 解法 前からDPしていく。経路復元は定石どおりDPテーブルにどこから来たのか情報を付記してお…

解法 P_DやP_Gが0や100の場合は別に考慮してやる。それ以外のとき、Gに制限が無いので通算勝率の方はいくらでも調整できる。なので今日の勝率だけ考えてやればよい。N>=100のときはD=100とすればいつでも達成可能だし、それ以外のときは全探索してやればよい…

keyword 動的計画法 C++ 問題概要 問題がN( 解法 解く問題が決まっているならB[i]の小さい順に解くのが最善だと分かる。従ってB[i]をkeyにしてsortしてDPで解ける。dp[i][j] = {index i以下の問題で解いたのがj問であるときの最小時刻}。気分的にはSRM 502 5…

解法 座標、メモリの値、向きの組を状態としてflood fill。余計なローカル変数が無ければ再帰で書いても大丈夫。Gの盤面上での振る舞いとdy[]の中の値を書き間違えていてWA連発。

解法 愚直にDFSで書く。以下の実装では計算量O(2^k * n)となっているが、もちろんO(2^k)に落とせる。

解法 やるだけ。もちろん計算量は落とせるけど、間に合うときは一番分かりやすく書くのがベスト。

keyword メモ化再帰 確率 C++ 問題概要 N( 解法 確率と言えば解法は 高校数学っぽい場合の数 二分探索 動的計画法 （連立）方程式 だけど、今回は状態数が1000^2しか無いしDPでいけそう。ただし状態がループする可能性があるので方程式っぽくもある。これま…

問題概要 J( メンバーの所持金の平均をaとする。 所持金が最小の者を一人選んで、所持金が平均より多くなるように金を渡す。足りなければ全額渡す。 解法 適当にシミュレーションしたら最大値と最小値の差が1以下になるので、そうなったら等分配すればよい。…

問題概要 n( 解法 mod 10で考えれば良さそう。10通り場合分けすればO(1)で通る。 感想 手で解くのは不安材料が多すぎる。nが大きい場合は適当にmodをとったりして全探索をかける方が好ましかった。後コーディングも「反復は避けよ」に反するものとなってしま…

解法 全探索すればよい。計算量O(n*2^n)。括弧の対応と出力の条件(iwiを含む)をチェックし忘れてWA連発。

解法 数えるだけ。書き換えながらやる方が偶奇の場合分けが減って安全だったかもしれない。大差ないか。

解法 やるだけ。O(N+M)。

keyword 動的計画法 C++ 問題概要 正整数列X(長さN 解法 dp[i] = {iが端点になっている確率}とすれば、これはO(T*N)で求められる。その後、i+X[i]>=Tとなる確率を足し上げていけばよい。全体の計算量はO(T*N)。 感想 dp[i][k] = {iが棒kの右端になっている確…

解法 答えに関して全探索すればよい。計算量O(N^2)。

解法 既に正しい数字は動かさない、という仮定(これは正しいらしい)を置くと、完全順列などの知識を用いてO(N^3+T*N)のメモ化解法がすぐに思いつく。これで小さいテストケースをいくつか試すと法則性が見えてくる。以下はメモ化解法のほう(本番で提出したの…

問題概要 長さN( 解法 2つの集合のxorが等しいので、元の数列のxorは0になる。これが可能である条件。またこのとき、どのような分割でもxorは等しくなる。したがって、和の最大値は全体の和から最小値を引いたものとなる。

解法 ただのシミュレーション。vectorをstack代わりに使って書いた。

解法 やるだけ。イベントドリブンでも余裕で間に合う。