2013-12-01から1ヶ月間の記事一覧
問題リンク；String Distance and Transform Process問題概要： ２つの文字列が与えられる 最初の文字列に以下の３つの動作だけを使用して目的の文字列に変更するためにかかる 動作の最小の使用回数とその動作を出力せよ １：文字列の任意の場所にアルファベ…
問題リンク : http://uva.onlinejudge.org/external/114/11475.html問題概要： 大文字か小文字のアルファベットからなる空ではない文字列が与えられる この文字列に０以上のアルファベットを追加して長さが最小の回文を作れ解法： 与えられた文字列の後ろか…
問題リンク：http://uva.onlinejudge.org/external/106/10616.html問題概要： n個の要素からなる配列A[i](0 配列A[i]からM個の要素を選んだ時、その和がDで割りきれるような選び方は何通り存在するかクエリーは以下の形式からなる D M D,Mは上の説明に登場す…
問題リンク：http://uva.onlinejudge.org/external/125/p12532.pdf問題概要： n個の要素をもつ配列A[i](0 クエリーは以下の形式からなる 1. C I J 2. P I J 1.の時、配列Aの要素Iを値Jに変更する 2.の時、要素A[I-1]からA[J-1]までの積(つまり、A[I-1] * A[I…
問題リンク：Search of Concatenated Strings | Aizu Online Judge問題概要： n個(1 n個の文字列を任意の順で全てつなげた文字列がtのなかにどのくらい存在するか？ ただし、n個の文字列をつなげた際に同じものが複数できた場合はそれらを１つとみなす解法：…
問題リンク：Weather Forecast | Aizu Online Judge問題概要： 略解法： メモ化再帰をした 今何日かと今どこかと1,3,9,11を最後に雨を降らしてから何日訪れていないかを記録した初期化で毎回365*9*7*7*7*7してたらTLEをくらってしまったコード： #define REP…
問題リンク：http://uva.onlinejudge.org/external/104/10445.html問題概要： 多角形が与えられる その多角形の連続する3点からなる角度の最大と最小を求めよ解法： 全ての角度をみてその中の最大と最小を求める 入力は時計回りで与えられるのか反時計回りで…
問題リンク：http://uva.onlinejudge.org/external/115/11505.html問題概要： 略解法： その通りにシュミレーションする 出力する際に(int)round(sqrt(x*x+y*y))のように (int)でキャストしないとWAになる もしくはepsをつけるコード： #include<iostream> #include<cmath> #d</cmath></iostream>…
問題リンク：http://uva.onlinejudge.org/external/117/11792.html問題概要： N個の駅が1からNまでで番号付けされている 路線の情報がS行以下の形式で与えられる a b c d ... g 0 0は路線の終了を意味する a b c d gは駅の番号を表す 各駅は路線の1つ前と１…
問題概要：Elevator | Aizu Online Judge問題概要： 日本語なので略解法： 動的計画法を行う 荷物があるフロアの中で最も上にあるフロアから１フロアずつ全ての荷物をもっていきながらおりていく そのフロアにある荷物を全て１つ下のフロアに持っていくため…
問題リンク：Twin book report | Aizu Online Judge問題概要： 日本語なので略・自分が読み落としていた文 > 加えて，本の返却期限が近いため，まずはなるべく早くすべての本を読み終えるようにしてもらう事にした つまり、読める本があるなら感想文よりもそ…
問題リンク：http://uva.onlinejudge.org/external/106/10637.html問題概要： 整数Sをt個のco-primeな値に分割したものを全て出力せよ解法： dfsで枝刈りしながら探索した brute forceな感じが。。。（正しくは素数使ってなんたらららしい） 全探索する過程…
問題リンク：Stopped Watches | Aizu Online Judge問題概要： n個の時計の情報が与えられる ただ、どれが秒針でどれが分針、時針なのかはわからないし どこを基準に数えているのかも分からない 全ての時計がとりうる時間の間隔のうちもっとも短いものを出力…
問題リンク：http://uva.onlinejudge.org/external/103/10382.html問題概要： 略解法： 円と長方形が交差する場所のx座標を計算で求める 円の中心点の座標を(x,y)、円の半径をrとすると 円と長方形が交差する場所のx座標(以下 nx)は以下の通り nx = +sqrt(r*…
問題リンク：http://uva.onlinejudge.org/external/101/10136.html問題概要： 複数の点が与えられる 好きな場所に直径５cmの円を置いたときにその円の内部に入る点の数を最大化せよ解法： AOJ1132やAOJ0090と同じ問題 円の半径が2.5になっただけある2点を決…
問題リンク:Eight問題概要： ８パズルを完成させるために必要な最小の手数の経路を復元せよ解法： IDA*で解いた ヒューリスティック関数では現在のパズルの状態から目的の状態（パズルが解けた状態）へのマンハッタン距離の総和を求めた 例えば、次の状態に…
問題リンク：http://uva.onlinejudge.org/external/101/10181.html問題概要： １５パズルを完成させるために必要な最小の手数の経路を復元せよ解法： IDA* IDA*自体は UVa 652 : Eightとまったく同じ そのパズルが解けるかどうかの判定は異なる これはグーグ…
問題リンク：http://uva.onlinejudge.org/external/105/10520.html問題概要： 短いので略解法： 式に従って頑張ってノートでシュミレーションして見た結果左したのあたりから戻るように埋めていくとよさそう・・・だがしかし今回nが20しかないので、 最大20*…
問題リンク：http://uva.onlinejudge.org/external/110/11054.html問題概要： n人の人がワインを売買する 人iの情報はa[i](0= 0 ならその人はa[i]個のワインを買う a[i] a[i]の総和は０となる a[i]のうち任意の数を任意の場所に移動できる その際に、abs(j-i…
問題リンク：http://uva.onlinejudge.org/external/113/11326.html問題概要： H*Wの部屋がある 壁は全て鏡である 部屋の左下からレーザービームを角度thetaで打つ そのレーザービームは部屋の右の壁のある一点にぶつかる その時のレーザービームの長さAと直…
問題リンク：問題概要： n個の要素 a[i]( 0 a[i]を以下の条件に従ってソートする ・a[i] % M の値が小さい順にソートする ・a[i] % M の値が同じ場合 ・a[i]とa[j]の片方が偶数で片方が奇数ならば奇数を先にする ・a[i]とa[j]の両方が偶数なら小さい順にする…
問題リンク：Equation問題概要： Infixで式が与えられる Postfixに変換せよ制約： 数字は１文字解法： スタックを用意する 式を左から右に向かって見ていく 以下の方法にしたがって変換する・アルファベットが'('の場合、スタックにプッシュ・アルファベット…
問題リンク：http://uva.onlinejudge.org/external/102/10296.html問題概要： n個のノードとm個のエッジが与えられる 任意のノードからスタートして全ての辺を少なくとも１回は通った後に再度 スタートしたノードに戻ってくるのに必要な最小のコストを求めよ…
問題リンク：http://uva.onlinejudge.org/external/10/1099.html問題概要： n人の人とh*wのチョコレートが存在する n人がそれぞれa[i]個(1 チョコレートを縦または横に割る動作だけでn人の全ての要求するピースをつくる亊ができるかどうか判定せよ制約： ・ …
問題リンク：Live Schedule | Aizu Online Judge解法： 動的計画法dp[何日目か][負担][連続してライブをした日数] := 最大利益 とする遷移の状態としては、 ・何もしない ・その場所だけでライブ ・連続してライブ の３つがあるEが0の時はそこでライブを行え…
問題リンク：Bingo | Aizu Online Judge解法： 動的計画法を行う 問題の制約より、N*Nのマスを全て異なる数で総和がSになるような状態の数を求めれば良い亊がわかるコード： #define REP(i,s,n) for(int i=s;i
