問題リンク：Optimal Array Multiplication Sequence問題概要： N個の行列が与えられる それらの行列を最適に計算するための括弧付けを行え解法： 連鎖行列積 アルゴリズムイントロダクションを読んで勉強コード： #define REP(i,s,n) for(int i=s;i

問題リンク：TeX Quotes問題概要： 複数の行からなる文字列が与えられる その文字列中に含まれる最初の " は `` に、2回めの " は '' に変換し出力せよ解法： その通りにやる int cnt = 0 みたいな変数を用意しておいて ”をみつける度に１加えていく cnt が…

問題リンク：Power of Cryptography問題概要： n,p (p k^n = p となるような k を求めよ(k 解法： pがかなり大きいが、doubleでなんとかなるみたいk^n = p より k = n√p (つまり、p^(1/n)) または k^n = p より log(k)p = n log p/log k = n log p = n log k…

問題リンク：http://uva.onlinejudge.org/external/9/991.html問題概要： 円周上にn*2の人が等間隔で立っている 人と人を結ぶときにその線分が交差しない様な結び方は何通り存在するか？ （1 解法： カタラン数を利用する wikipediaのカタラン数のページより…

問題リンク：Exponentiation問題概要； とても大きい値rとinteger n が与えられる r^nを計算せよ 出力する際には、先頭の０と末尾に連続する０は削除すること解法： java で BigDecimalを使って計算する BigDecimalからStringに変換する際には指数フィールド…

問題リンク：Adding Reversed Numbers問題概要： ２つのとても大きい値が与えられる それらを反転した値を加え、その結果を反転して出力せよ 先頭の０は消えることに注意解法： BigIntegerを使って計算する StringBufferのreverse()を使って文字列を反転する…

問題リンク；Fermat vs. Pythagoras問題概要： あるpositive integer Nが与えられる x,y,zをN以下のpositive integersとする x*x + y*y = z*z を満たす様なx,y,zの組の内、x,y,zのそれぞれが互いに素なものの数と、x*x+y*y = z*z を満たすようなx,y,zでないN…

問題リンク：Overflow問題概要： a + b または a * b が与えられる（a,bはとても大きい値） 入力をそのまま出力した後に a が 2^31-1 より大きいなら first number too big と、 b が 2^31-1 より大きいなら second number too big と、 a + b または a * b …

問題リンク：Tree Summing問題概要： integer I と２分木がLISP S-expressionでtreeとして与えられる treeのルートから葉までの値の和がIとなるならyes,ならないならnoと出力せよ解法： 構文解析を行う treeの値がマイナスである事があるので注意すること つ…

問題リンク : History Grading問題概要： 歴史のテストをした n個の年代順のイベント１...nがどの順番で行われるかの答えと生徒の解答があたえられる 生徒が得たスコアを計算せよ スコアの計算方法は以下の通り 1 2 3 4 が答えだとする 生徒が 1 3 2 4と解答…

問題リンク：Maximum Sum問題概要： N*Nの2次元配列が与えられる この中から作れる長方形のうちその要素の和が最大のものをみつけよ解法： よくあるDP memo[y][x] := memo[y-1][x] + memo[y][x-1] - memo[y+1][x+1] + array[y][x]という配列を用意する array…

問題リンク：Stacking Boxes問題概要： n個のk次元の箱がある 以下の条件を満たす時、箱aを箱bに入れることができる ・箱aの各辺の長さが箱bの対応する辺の長さ未満であるような順列が存在する （例: 5次元とする 箱 a : 5 1 3 7 6 箱 b : 4 2 7 8 6分かりに…

問題リンク：Three-way Branch | Aizu Online Judge問題概要； H*Wのセルからなるグリッドが存在する 自分は最初セル(1,1)にいて、セル(W,H)に移動する 今いるセルの左下、下、右下に移動できる いくつかのセル上には障害物が存在しており、そのセルに移動す…

問題リンク : Hotel | Aizu Online Judge解法： 動的計画法を行う D日間にかかるホテルの費用の最小は各日にちでもっとも安いホテルを選んだときの費用の和だが、 移動回数の最小化や複数あったときに辞書順で最小のものを選びたいのでDPする配列は dp[何日…

問題リンク : Ice Maze | Aizu Online Judge問題概要： 日本語なので略解法： 反復深化で解いた氷の塊の情報をvectorで管理した 入力をとった後に氷の塊に番号を付けていき、氷の塊の分だけvectorの要素を確保する 氷の塊の番号とvectorのインデックスが対応…

問題リンク : Life Game | Aizu Online Judge問題概要： 六角のセルにウィルスが存在する １ターン毎にウィルスが存在するセルに隣接する全てのセルに今いるセルに存在するウィルスの数と同じ数のウィルスが発生する １つのセルにM以上のウィルスが存在する…

問題リンク：Swimming Jam | Aizu Online Judge問題概要： n人の人が２つのレーンを使って水泳をする 入力として人の数nとそれぞれの人が１レーンを泳ぐのにかかる時間と往復する回数が与えられる ある人が泳いでる途中で前の人に追いついてしまった場合はレ…

問題リンク：The Morning after Halloween | Aizu Online Judge問題概要： h*wのグリッドが与えられる グリッドは壁と何もないマスからなり、その中に幽霊が１以上３以下存在する 幽霊はそれぞれ対応した目的地をもっており、すべての幽霊はその対応した目的…

問題リンク : Enegy Transporter | Aizu Online Judge問題概要： n個のノードが一直線上につながれている ノードはそれぞれ値を持つ 両端のノードと値が０のノード以外のノードは自分の値をマイナス１することで 右のノードの値に左のノードの値を加えること…

問題リンク : 2907 -- Collecting Beepers問題概要： H*Wのグリッドが存在する そのグリッド上のある点から指定された複数の点を全て任意の順番で訪れ、最終的にまた最初の点に戻ってくるまでの最小移動回数を求めよ 点は最大１０まで指定される解法： 巡回…

問題リンク:http://uva.onlinejudge.org/external/101/10178.html問題概要： 平面グラフが与えられる 平面グラフによってできる領域の数＋１を求めよ(国と海の数を求めよ)解法： 平面グラフの国の数 s は辺の数をe,ノードの数をvとすると s = e - v + 1 とな…

問題リンク : Geometric Map | Aizu Online Judge問題概要： n本の線分が与えられる （n 線分は必ず１本以上の他の線分と端点で交差している 線分の両端が別の線分の端点と交差しているならばそれは道である 線分の片方だけが別の線分の端点と交差しているな…

問題リンク : Laser Beam Reflections | Aizu Online Judge解法： レーザービームを打つ方向を３６０度ちょっとずつずらしながらシュミレーションした レーザービームを打つ方向さえ決めてしまえばそこからゴールまで到達できるかどうかは一意に定まるので判…

問題概要： 木とクエリーが与えられる クエリーは以下の形式で与えられる a b a,bはそれぞれ木のノード番号を表す それらのノードにはノミが存在し、以下の条件を満たしながらお互い引き合うように移動する 1回の移動で以下の条件を満たした上で隣接するノー…

問題リンク：Nails | Aizu Online Judge解法： いもす法のサイトの解説参照以下手順だけ 輪ゴムの頂点を(x,y),三角形のサイズをdとする ２次元配列gを用意する（vectorで動的にサイズを確保した） gの(x,y),(x+1,y+d+2),(x+d+2,y+d+1)の値をプラス１ (x+1,y)…

問題リンク : Substring | Aizu Online Judge 解法： ローリングハッシュを使う 文字列をハッシュ値に変えてsetで管理した 適当に基数選んで逆元を手元で計算して使った本番解けなくて解説聞いたまま放置してたけどついにやったったコード： #define REP(i,s…

問題リンク : Angel Stairs | Aizu Online Judge解法： 天使が奏でたい曲を最初からみていくのではなく最後からみていく 最初から見ていくと移動先が複数考えられるが、後ろから見ていくと移動先は１つに定まる文字列だと扱いにくいのでCからBまでの音を数字…

問題概要： N個の要素をもつ配列が与えられる その配列の各要素の初期値は０である あなたは次の２つのオペレーションを行う事ができる 1. 配列の１つの要素を選び、その要素に１加える 2. 配列内の各要素を２倍する N個の要素を含むもうひとつの配列が与え…