問題リンク:2661 -- Factstone Benchmark問題概要： とある会社が1960年に4-bitコンピュータをリリースした 1970年には8-bit,1980年には16-bit,.... といった感じで、10年毎にbit数が2倍になっていく ある年y( 1960 その年のコンピュータがunsigned intで表…

問題概要： 長さNの配列Aがある この配列は要素として０からN-1までの値がちょうど１つずつ入っている 配列Bを以下のように定義し、これを配列Aの子と呼ぶ 1. B[0] = 0 2. B[i] = A[B[i-1]] ( 1 配列Bの要素が0からN-1までをちょうど１つずつ持つ時、AとBはp…

・川渡り問題 ・ POJ 1700 1700 -- Crossing River・市松模様においてく系の貪欲 ・ UVa 12520 http://uva.onlinejudge.org/external/125/12520.html・よくあるタイプのソートしてからの問題 ・ AOJ 2236 Rabbit Plays Games! | Aizu Online Judge・１行覚え…

問題リンク：2676 -- Sudoku問題概要： 数独解法： DFSで全探索 各行、列、3x3のセルでどの数字を使ったかをビットでもっておくコード： #include<cstdio> #include<algorithm> #include<cmath> #define REP(i,s,n) for(int i=s;i</cmath></algorithm></cstdio>

問題リンク:1001 -- Exponentiation問題概要 Rとnが与えられるのでRのn乗を計算せよ解法 BigDecimal 正規表現使い慣れていないので良い練習になったコード import java.math.*; import java.io.*; import java.util.*; class Main{ public static void main(…

問題リンク:Connect | Aizu Online Judge問題概要: 略解法: １行覚えるタイプの動的計画法 dp[r][c][bit] := (c,r)までで使用する文字列の状態がbitの時の最大値 としてDPする bitの数を数えてその行の文字列よりも多く使用する場合などはcontinueする ２重…

問題リンク:Farey Sequence | Aizu Online Judge問題概要： 略解法： オイラーのΦ関数を使う i == 0 のとき、F_0 = 2 その他のとき、F_i = F_i-1 + (iと互いに素なものの数) となる iと互いに素なものの数はオイラーのΦ関数で求める 前処理でFを作っておいて…

問題リンク:Anipero | Aizu Online Judge問題概要: 略解法： 動的計画法 pre[使用した金額][選んだシークレットアーティストの数(0,1,2人のみ)] := この時得られる最大の満足度 pre2[使用した金額][選んだスタンダードアーティストの数] := この時得られる最…

問題リンク:http://uva.onlinejudge.org/external/118/11865.html問題概要： N個のノードとM本の有向な辺の情報が与えられる。 初期状態ではどのノードも辺でつながれていない。 ノードは０から順にN-1まで番号付けられている。 ノード０からその他の全ての…

問題概要： S個の歌がある その音楽を３人のボーカロイドGumi, Ia, Mayuが歌う Gumi は gumi回、 Ia は ia回、 Mayu は mayu回だけ歌う S個の歌は少なくとも３人のうち1人に歌われなければならない そのような歌に対するボーカロイドの割り当て方は何通り存…

問題リンク：Problem - 377A - Codeforces問題概要： n*mの迷路があたえられる 迷路は'.'または'#'からなる '.'はそのセルが空であることを示す '#'はそのセルが壁であることを示す 自分は空のセルにk個だけ壁を追加する 壁を追加したあと、空のセルのエリア…

問題リンク：Problem - 387A - Codeforces問題概要： ある人が目覚めた時間とベッドにはいった時間が与えられる。 その人はどのくらいの間寝ていたか？解法： 目が覚めた時間とベッドにはいった時間を分単位に直しておく （目が覚めた時間）ー（ベッドに入っ…

問題リンク：France '98問題概要： 16個の国と 各国間での勝率があたえられる これらの国が図のようなトーナメントを行った時、各国が優勝する確率を求めよ解法： 状態が少ないので再帰ですべて数えた実装時間： 1時間４分 たった一つのバグを50分近く見つけ…

問題リンク:http://uva.onlinejudge.org/external/100/10056.html問題概要： N人のプレイヤーがいる プレイヤーは１から順にNまで番号付けされており、 プレイヤー１から順にサイコロらしきものをふる サイコロらしきものは確率pで目的の目を出す 目的の目が…

問題リンク：Futon | Aizu Online Judge問題概要： n枚の布団の位置情報が与えられる それらの布団に人が寝るわけだが、 人の頭のに隣接する部分に他の人の足があってはならない そのような寝方があるかどうか判定せよ解法： グラフを構築して2色でそれらの…

問題リンク：Map of Ninja House | Aizu Online Judge問題概要： 無向グラフが存在する 自分は最初そのグラフのノード番号０のノードにいる 入力が正のとき、それは今いるノードの次数を表す 入力が負のとき、それは（今いるノードの深さ）ー（１つ前にいた…

問題リンク : Petoris | Aizu Online Judge問題概要： h * w のピースと H * W のボードがある ピースとボードは'.'または'#'からなる '.'はそこが空であることを意味し、'#'はそこが埋まっている亊を意味する ピースをボード上に置きたい 置く際には、ピー…

問題リンク：Repeated Subsequences | Aizu Online Judge問題概要： 長さが300以下の文字列があたえられる この文字列を空でない２つの文字列に分ける こうしてできる２つの文字列のLCSの中で最も長いものを出力せよ 複数ある場合はどれを出力しても良い解法…

問題リンク：Triangles | Aizu Online Judge問題概要： 1辺の長さが１の正三角形をn個、任意の点を中心として 360/n 度間隔で置いていく この時n個の正三角形が覆う面積はどのくらいか？解法： 正多角形から余計な部分を引いて面積を出した上の図の黒い矢印…

問題リンク : http://uva.onlinejudge.org/external/112/11240.html問題概要: n個の要素からなる配列が与えられる この部分列のなかで以下の条件を満たすもののうち最長のものの長さを求めよ A > B D 解法 : 貪欲に決めていく（考え方的にはDP？） n個の配列…

問題リンク：Color the Map | Aizu Online Judge問題概要： 10個以下の国の情報が多角形として与えられる それらの国に色を塗っていきたいのだが、隣接する国同士は異なる色で塗りたい 同じ国であるならば同じ色で塗らなければならない 最低何色必要か解法：…

問題リンク : 8 Queens Chess Problem問題概要 : 8*8のグリッド上に８個のQueenを置きたい ただしQueenが攻撃できる場所に別のQueenを置く亊はできない そのようなQueenの配置の仕方を全て辞書順で出力せよ 入力で与えられた列には入力で与えられた行にしか…

問題リンク : http://uva.onlinejudge.org/external/105/10577.html問題概要 : 正多角形のうち３点だけが与えられる その３点から本来の正多角形を復元し、その正多角形を囲むようなx軸とy軸に平行な長方形の面積の最少値を求めよ解法 : 正n角形の中心点が分…

問題リンク : http://uva.onlinejudge.org/external/111/11195.html問題概要 : n*nのグリッド上にn個のQueenを置きたい ただし、Queenを置く際にそのQueenは別のQueenから攻撃されないような場所にしなければならない グリッド上にはいくつかの'*'が存在する…

問題リンク : http://uva.onlinejudge.org/external/2/202.html問題概要 : 2つの整数 numerator, denominator があたえられる numerator / denominator の結果とその小数点以下に含まれる最小のサイクルを見つけ、指定された形式で出力せよ解法： Cycle dete…

問題リンク : Hexerpents of Hexwamp | Aizu Online Judge問題概要 : 略解法：A*(移動した回数) + (大蛇の頭からゴールまでの距離) > 20 なら枝刈りをしたこの問題での２つの6角座標の距離は以下のように計算する (x1,y1) から (x2,y2) への距離distを求める…

問題リンク : http://uva.onlinejudge.org/external/111/11163.html問題概要： N匹のジャガーがいる 最初N匹のジャガーは１からNまで昇順に並んでいる １番のジャガーは王様で問題文中にかかれている様に移動する事ができる 初期の状態から入力で与えられる…