AOJ
問題ページ Aizu Online Judge Arena 概要 N個の自然数a[i]が与えられる abs(a[i]-a[j]) = 0 (mod n-1) を満たすような組(i!=j)を一つ示せ 解法 N <= 1000 でO(N^2)が間に合うので全てのペアについて探索すればよい ソースコード #include <bits/stdc++.h> using namespace </bits/stdc++.h>…
問題ページ Aizu Online Judge Arena 解法 まず、クエリを先読みして時間についてソートしておく。これでクエリについて順番に答えていくことができる。昼と夜の区別に注意。以下の実装では2d+1, 2eとして区別している。 ある区間について高速に値の更新を行…
問題ページ Restore Calculation | Aizu Online Judge 考えたこと 桁ごとに考えていけばよさそう 下の桁から繰り上がりがいるかとか考えればいける気持ちになる 場合分けが多すぎるので桁DPしたほうがよさそう dp[i][j] = (i桁目までで次の桁に繰り上がりが…
問題ページ Infinity Maze | Aizu Online Judge 考えたこと Lがめっちゃでかい 周期性がありそう x,y,向き について考えると40000通りしかないので鳩ノ巣原理から周期は高々40000 一回ループに入るまでシミュレーションをしてあとは周期性から求める mp[{x,y…
問題ページ Line Gimmick | Aizu Online Judge 解法 ある矢印の並びでi番目の矢印からスタートするとする i番目より左にある'>'とi番目より右にある'<'でのみ移動する方向を反転させる sample1で考えてみる 2からスタートすると1で反転→4で反転→0で反転→5で…
問題ページ Shopping | Aizu Online Judge 概要 n個の店が並んだ商店街がありi番目の店は位置iにある。ある店dを訪れてからある店cを訪れなければならないというm個の制約の元で位置0から位置n+1まで歩くときの最小距離を求めろ。 n <= 10000, m <= 500 考え…
問題ページ Tiles are Colorful | Aizu Online Judge 考えたこと Aを消すために消さないといけない色から有向辺を貼ってトポソを考える 2パターンあるのをトポソでわけて判断するの無理そう 各色のタイルの位置を求めておいて消せるタイルを消すを繰り返せば…
問題ページ Restrictive Filesystem | Aizu Online Judge 考えたこと 10^9の配列確保して1つずつ記録していくのはメモリ的にも計算量的にも不可能なので座圧は必須そう dp[i] = (j, k) (位置iからjまでkが記録されている)としてunordered_mapを使ってメモリ…
問題ページ Median Tree | Aizu Online Judge 考えたこと コストが小さい辺をなるべく使っていきたい 最小全域木を思い浮かべるけどコストが1の辺を使わずに2と3の辺を繋いだほうがいい場合があるのではみたいな気持ちになって捨てる（は？） 謎の貪欲を投げ…
問題ページ ICPC Calculator | Aizu Online Judge 解法 +か*が来たらその演算子で計算する範囲の数式を全部計算して返すような関数をつくってその関数を再帰的に呼び出していくことで計算する。ある演算子で計算する対象はその演算子より高さが1段高いものな…
問題ページ 6/2(1+2) | Aizu Online Judge 解法 構文解析をする。取りうる数字が一意には定まらないので候補全部をsetで持っておき、next_permutationで全通りを試す。括弧ごとに演算子と数字を全部列挙したあと、演算子の取りうる順番を全通り試してその括…
問題ページ Broken Cipher Generator | Aizu Online Judge 考えたこと 明らかに構文解析でBNFまで書いてあるので実装をしようとする。 BNFをよく見るとが左再帰なのでそのままは書けない。 ググって左再帰の除去を調べると = | empty とすればよさそう。 emp…
問題ページ marukaite | Aizu Online Judge 考えたこと 解説を見た。 最小費用流を流すところは書けたが操作の復元に手間取った…最小費用流を行ったあと、容量が0の辺が存在すればその辺には流れたといえる。つまりR_iからC_jへの辺の容量が0であれば(i, j)…
問題ページ Plush Toys | Aizu Online Judge 解法 bitDPをする。dp[S] = (集合Sの要素に含まれる種類を左から並べたときの最小の並べ替え回数) とする。dp[S|1<<i] = dp[S] + (並び替えに必要な回数) と遷移できる。並べ替えに必要な回数は並べる区間に含まれていない種類iの個数なので、種類別に累積和を取っておけばO(1)で求めることができる。したがってO(M2^M)で解ける。 //#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; t…</i]>
問題ページ http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day2_21.pdf 考えたこと 最大の最小化と言われたので二分探索をする。幅Xで実現することができるかの判定について考える。x方向、y方向についてそれぞれ貪欲に決めていくと幅Xで必要な…
問題ページ http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf 考えたこと 色iが色jの上に乗っていることをjからiへの有向辺が張られている状態と考えるとトポロジカルソートをすればよい。O(HWN)で辺を張ればよく、トポロジカルソート…
問題ページ http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf 考えたこと N頂点の木で値の総和が最大になるような連結成分を求めればいい。dp[i] = (頂点iの部分木で最大の値の総和) とするとdp[i] = sum(dp[j], 頂点jが頂点iの子でdp…
問題ページ JOI 公園 | Aizu Online Judge 考えたこと とりあえず広場1から各広場への最短距離はdijkstraで求まる。Xを決めれば各辺について両端の頂点への最短距離がX以下かどうかでその辺が撤去される辺か判断できるのでO(M)でできる。max(X) = 10^10 でま…
問題ページ バームクーヘン | Aizu Online Judge 考えたこと 最小値の最大化と言われたので二分探索。判定がO(f(n))であればO(f(n)log(max(A_i)))となる。始点を一箇所固定すればmid以上の最小となるように2箇所切っていくのが最善になる。全パターン確認す…
問題ページ JOI 国の買い物事情 | Aizu Online Judge 解法 最短経路問題で始点が複数あるパターンなので始点をまとめる架空の頂点をつくってやればdijkstra一回で各頂点への最短距離がわかる。各頂点への最短距離がわかっていれば各辺のどの位置が最短距離が…
問題ページ お菓子の分割 | Aizu Online Judge 解法 いかにもDPの雰囲気があるのでDPを考える。AくんとBくんでお菓子を分け合うとして dp[k][i][j] = (k番目まででAくんがi個取って最後に取ったのがAくんならj=0、Bくんならj=1) とおいてDPをする。遷移に必…
問題ページ ぴょんぴょん川渡り | Aizu Online Judge 考えたこと 制約が色々小さくて最小コストを求めるので拡張dijkstraやDPを考える。 dp[i][j][k] = (i行目j列目まででk回一行飛ばしをしたときの最小滑りやすさ) としてDPを考えるとO(NMmax(k)^2)で計算量…
問題ページ タクシー | Aizu Online Judge 考えたこと 最短距離と言われたのでdijkstraを考える。遷移先が距離r[i]以下の頂点であるdijkstraをすればよさそう。全頂点からそれぞれdijkstraをしてある頂点から距離がr[i]以下の点を全列挙しておけば、あとはdi…
問題ページ 魚の生息範囲 | Aizu Online Judge 考えたこと 3次元imosすればよさそうだけど制約的に無理。領域木とかを考えてもわからないので解説を見たらただの座圧ではい。O(N4)で解ける これくらいは思いつきたかった… //#define __USE_MINGW_ANSI_STDIO …
問題ページ ビンゴ | Aizu Online Judge 考えたこと N2要素で要素の値は1以上M以下、要素の合計がSの狭義単調増加な数列が何通りあるか求めればいい。 dp[i][j][k] = (i番目までで最大の要素がjで合計がkの数列の通り数) としてDPしようとしたが遷移のうまい…
Daruma Otoshi | Aizu Online Judgedp[l][r] = {lからrまでの区間の状態}と持ってDPする、区間DPの問題。 この問題ではdp[l][r] = {lからrまでの区間で叩ける最大のブロック数}とする。 dp[l+1][r-1]の区間が全てのブロックを叩き出すことができ、l番目とr番…
Fastest Route | Aizu Online JudgeまずNdp[S] = （集合Sをクリアするのにかかる最短時間）とする。 dp[S]は集合Sから要素を一つ取り除いた集合をクリアするのにかかる最短時間 + 集合から取り除いたステージをクリアするのにかかる最短時間と考えられるので…
パズル | Aizu Online JudgeDFSで面子と雀頭の取り方を全て試す。
Coin Combination Problem II | Aizu Online JudgeN
dp[i][j] = (s1のi文字目まででs2のj文字目までを作る最小コスト) としてDPします。 各文字列に対する操作についてDPの遷移を考えると 挿入 dp[i][j] = dp[i][j-1] + 1 削除 dp[i][j] = dp[i-1][j] + 1 置換 dp[i][j] = dp[i-1][j-1] + 1 となります。さらに…
