問題ページ Concert Hall Scheduling | Aizu Online Judge 考えたこと 区間が飛んでくるのでとりあえず終端でソートする 区間が3つ以上かぶるような日があるとだめ 今までに選んだ区間ですでに2つかぶっているような日が存在 その日よりも始点が前の区間を使…

問題ページ Rabbit Party | Aizu Online Judge 考えたこと 入力がグラフっぽい グラフとしてサンプルを書いてみるけどグラフの知ってるもの(最大安定集合とか)に帰着できない DPを考える dp[i匹目まで][j匹選んだ] みたいなの 今までに選んだうさぎの部分集…

問題ページ Deadlock Detection | Aizu Online Judge 考えたこと とりあえずサンプルを読む あるスレッドで{1,2}が獲得されてて3を取りたい、別のスレッドで{3}を獲得してて1を取りたい→デッドロック あるuから次のuまでに同じ数字が2回以上出てくる→デッド…

問題ページ 1 Day Passport | Aizu Online Judge 考えたこと とりあえず入力で何がくるのかちゃんと読む 会社の数の制約が小さい dp[S] = (会社の集合Sを乗り放題にするために必要な最小コスト) を求めておく これは簡単なbitDPでできてO(2^KP) 会社の集合S…

問題ページ No.685 Logical Operations - yukicoder 考えたこと bitだし2進数で考える x AND y, x XOR y, x OR y を書いてみる X 01001 Y 11101 & 01001 ^ 10100 | 11101 x,yのi桁目を(x_i,y_i)と表す AND < XOR を満たすためには1が出てくる最初の桁が(0,1)…

問題ページ Never Wait for Weights | Aizu Online Judge 考えたこと bがaよりwグラム重いことを頂点bから頂点aへ重みがwの辺を張ることで表す すると重さの差の質問クエリがある頂点からある頂点までの距離を求めるクエリに帰着できる 重さの差を測るクエリ…

問題ページ Mr. Rito Post Office | Aizu Online Judge 考えたこと 人がx、船がyにある状態を(x,y)と書くことにする ある頂点aにいるとき考えられる状態は (a,1)(a,2)(a,3)…(a,n) のN通り 頂点aから頂点bに移動するとき(a,1)→(b,1)(b,2)…(b,n)、(a,2)→(b,1)(…

問題ページ Google Code Jam 考えたこと 全ての可能な単語パターンは何通りか i文字目の文字種をc[i]とするとc[i]の総積になる nがこれに等しければ何をつくっても一致するので不可能 とりあえず適当にケースをつくってみる j文字目が全て同じ文字→j文字目を…

問題ページ Dinner | Aizu Online Judge 考えたこと すべての日で自炊するとする このときの幸福度は簡単に求まる ある日を自炊から外食に変えると変化する幸福度は(外食の幸福度)-(その日の自炊の分)-(その日以降で自炊する日数)*(定数) i日目以降で自炊をj…

問題ページ Rose Garden Witch | Aizu Online Judge 考えたこと 左下からの線分の偏角を微小量dtごとに変化させて全部試すみたいな解法を考える 判定部分でdfsでO(HW)かかるのでとてもじゃないけど精度がたりなさそう 線分を引く位置はどうせ少ないとかがな…