土下座しながら探索中

主に競技プログラミング

UVa

LiveArchive 6582 : UVa 1642 : Magical GCD

問題リンク:https://icpcarchive.ecs.baylor.edu/external/65/6582.pdf問題概要: 長さn(1 数列の各要素a[i]は1以上10^12以下 数列の連続した部分列を取り出し、(部分列全体のgcd) * (部分列の長さ) を値とする 値の最大値を出力せよ解法: 部分列の最も右と…

UVa 12923 : The Island

問題リンク : https://uva.onlinejudge.org/external/129/12923.pdf問題概要 : n * n のマトリックスが与えられる マトリックスの(i,j)はi番目の人が武器jを使った時に得られる力を表す n人の人がそれぞれ1つ武器を持った際に得られる力の総和の最大値を求…

Live Archive 6889 : City Park

問題リンク : https://icpcarchive.ecs.baylor.edu/external/68/6889.pdf問題概要 : 2次元平面上に1つ以上の長方形がそれぞれオーバーラップせずに置いてある 長方形の縦と横はそれぞれy軸とx軸に平行である 2つの長方形が辺または角で接しているとき、そ…

UVa 12484 : Cards

問題リンク : https://uva.onlinejudge.org/external/124/p12484.pdf問題概要 : 整数の書かれたN枚のカードが一直線上に並んでいる AさんとBさんは交互にカードを取っていく ただし、カードを取る際は両端のうちどちらかでないといけない 最初にAさんがカー…

UVa 11401 : Triangle Counting

問題リンク : http://uva.onlinejudge.org/external/114/11401.pdf問題概要 : 3以上の整数 n が与えられたとき、 長さが1からnまでの棒がそれぞれ1本ずつあるものとして それらのうち3本を選んで作れる三角形の個数を出力せよ n が3未満ならばプログラムを終…

UVa 12729 : Squares Game

問題リング : [uva.onlinejudge.org/external/127/12729.pdf:title]問題概要 : H * W のグリッドがあり、初期状態では各マスに色はついていない AnaとBobがゲームをする 最初のターンはAnaが行う Anaは色が付いていない2*2のマスを選び赤で塗りつぶす Bobは…

UVa 12755 : Easy Puzzle

問題リンク : http://uva.onlinejudge.org/external/127/12755.pdf問題概要 : N*Nのマスに0からN*N-1までそれぞれ1つずつかかれている これを0から昇順になるように並び替えたい 2つのマスの値を入れ替えるためには、片方のマスが0でなければならない 昇…

UVa 12627 : Erratic Expansion

問題リンク : http://uva.onlinejudge.org/external/126/12627.html問題概要 : 赤い風船を1つだけ持っている 次の日になると赤い風船が3つ、青い風船が1つになった 次の日になると赤い風船は前日と同様に分裂し、青い風船は4つの青い風船になった 詳しく…

UVa 12640 : Largest Sum Game

UVa

問題リンク : http://uva.onlinejudge.org/external/126/p12640.pdf問題概要 : 長さNの数列が与えられる この中から連続するいくつかの数字を選び、それらの和をとる この値の最大値を求めよ解法 : 数列を a とし、各要素は a[i] ( 0 a[0]から順番に見ていく…

UVa 12856 : Counting substhreengs

問題リンク : http://uva.onlinejudge.org/external/128/12856.pdf問題概要 : 長さ10^6以下の文字列が与えられる 文字列の部分文字列のうち、数字のみを含み、それを10進数の数として見たときにその値が3の倍数であるようなものを数えよ リーディング0も許…

UVa 10593 : Kites

問題リンク : http://uva.onlinejudge.org/external/105/10593.pdf問題概要 : n * n の char のシートが与えられる それに含まれる要素は 'x' か '.' のいずれか この中に含まれる大きさが1より大きい正方形とダイアモンドの数を数えよ解法 : 動的計画法 正…

UVa 1674 : Lightning Energy Report

問題リンク : http://uva.onlinejudge.org/external/16/1674.pdf問題概要: N個のノードからなる木が与えられる 各ノードは0からN-1まで番号が付けられている Q個のクエリーが与えられる クエリは次の形式で与えられる a b c これは、aからbまでの経路に属す…

UVa 12708 : GCD The Largest

問題リンク : http://uva.onlinejudge.org/external/127/12708.pdf問題概要 : 正の整数Nが与えられる。 N以下の任意の異なる2つの正の整数を選び、その最大公約数を求める こうして得られる最大公約数のうち、最大のものを出力せよ解法 : Nが偶数のとき、N/…

UVa 11908 : Skyscrapper

問題リンク : http://uva.onlinejudge.org/external/119/11908.pdf問題概要 : いくつかの重み付きの線分が与えられる それらの内いくつかを選択し、その重みの総和を最大化せよ ただし、ある点が複数の線分におおわれてはならない解法 : 重み付き区間スケジ…

UVa 12086 : Potentiometers

問題リンク : http://uva.onlinejudge.org/external/120/12086.pdf問題概要 : 長さNの数列とクエリーが与えられる クエリーの種類と効果は次の通り 1. S x y 数列のx番目の要素 ( 1-indexed ) を y に変更する2. M x y 数列のx番目の要素からy番目の要素まで…

UVa 12509 : Tin Cutter II

問題リンク : http://uva.onlinejudge.org/external/125/12509.html問題概要: n本の線分が与えられる 線分はx軸かy軸に平行である 外側から到達可能な線分の部分の長さの総和を求めたい解法 : 線分アレンジメント + 座標圧縮 + DFS 線分をアレンジメントし…

UVa 12294 : RPG battles

問題リンク : http://uva.onlinejudge.org/external/122/12294.html問題概要 : ゲームの主人公の初期の力はpであり、これからn個のステージを全て入力で与えられた順番でクリアしなければならない ( できない場合は"Impossible"と出力 ) 各ステージは p1, p2…

UVa 12295 : Optimal Symmetric Paths

問題リンク : http://uva.onlinejudge.org/external/122/12295.html問題概要 : n * n のセルがあり、セルの中には1以上9以下の数字がかかれている 左上を(0,0), 右下を(n-1,n-1)としたとき、左上から右下へ移動する経路のうち、通ったセルの数字の和が最小と…

ICPC 2014 WF ( UVa 1707 ) Surveillance

問題リンク : http://uva.onlinejudge.org/external/17/1707.pdf問題概要 : 凸多角形の建物がある それはn枚の壁からなり、壁は1からnまで番号がつけられている k個のカメラがその建物のまわりに設置してあり、i番目のカメラはs[i]からt[i]までの壁を撮影で…

UVa 10328 : Coin Toss

UVa演習 2014/7/14 (月) 問3問題リンク : http://uva.onlinejudge.org/external/103/10328.html問題概要: n回コインをなげたとき、2^nだけコインの状態がある そのうち連続でk回以上表がでているようなものはいくつあるか?解法: 動的計画法 dp[何桁までみ…

UVa 11500 : Vampires

UVa演習 2014/7/14 (月) 問2問題リンク : http://uva.onlinejudge.org/external/115/11500.html問題概要: 2人のプレイヤーでゲームを行う プレイヤー1の体力はEV1,プレイヤー2の体力はEV2である ゲームがはじまるとプレイヤーが交互にサイコロをふってい…

UVa 11181 : Probability|Given

UVa演習 2014/7/14 (月) 問1問題リンク : http://uva.onlinejudge.org/external/111/11181.html問題概要: N人の人がショッピングにいく 人i ( 1 N人中ちょうどr人が何かを購入する時、人iが何かを購入する確率を求めよ制約: 1 0 0.1 解法: Nが20人しかい…

UVa 10453 : Make Palindrome

UVa演習 2014/6/24 (火) 問3問題リンク : http://uva.onlinejudge.org/external/104/10453.html問題概要 : 文字列が与えられる その文字列の任意の場所に任意の文字を任意の数だけ追加できる 追加の回数を最小にして回文を作成せよ そのときの最小の追加回数…

UVa 11151 : Longest Palindrome

UVa演習 2014/6/24 (火) 問2問題リンク : http://uva.onlinejudge.org/external/111/11151.html問題概要 : 文字列が与えられる 文字列から余計な文字を削除して良いのでそこから得られる最長の回文の長さをもとめよ解法: メモ化再帰 両端を決めてどちらを削…

UVa 10739 : String to Palindrome

UVa演習 2014/6/24 (火) 問1問題リンク : http://uva.onlinejudge.org/external/107/10739.html問題概要: 長さ1000以下の文字列が与えられる この文字列のアルファベットに対して以下の3つの操作を自由に使うことができる ・任意の場所に任意のアルフ…

UVa 11753 : Creating Palindrome

問題リンク:http://uva.onlinejudge.org/external/117/11753.html問題概要: 文字列に文字をいくつか追加して回文にしたい K回以下の追加で回文にできるか?解法: 実際に再帰で試してみて最小の追加回数を求めるコード: #include<bits/stdc++.h> #define REP(i,s,n) for(</bits/stdc++.h>…

UVa 11611 : Colored Tiles

問題リンク:http://uva.onlinejudge.org/external/116/11611.html問題概要: H*Wのマスに図にあるようなピースを置いていく マスは3種類あり、 空のマスにはピースを置ける 壊れているマスにはピースを置けない 色の指定があるマスにはその色のピースしかお…

UVa 12520 : Square Garden

問題リンク:http://uva.onlinejudge.org/external/125/12520.html問題概要: L*Lの1*1のセルからなる正方形がある 自分はそのセルの中からN個選んで色をつける 色がついたセルの周囲の長さの最大値を求めよ解法: ※画像が死んで見えない場合はクリック 市松…

UVa 11865 : Stream My Contest

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

UVa 542 : France '98

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

UVa 10056 : What is the Probability?

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

UVa 11240 : Antimonotonicity

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

UVa 750 : 8 Queens Chess Problem

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

UVa 10577 : Bounding box

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

UVa 11195 : Another n-Queen Problem

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

UVa 202 : Repeating Decimals

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

UVa 11163 : Jaguar King

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

UVa 526 : String Distance and Transform Process

問題リンク;String Distance and Transform Process問題概要: 2つの文字列が与えられる 最初の文字列に以下の3つの動作だけを使用して目的の文字列に変更するためにかかる 動作の最小の使用回数とその動作を出力せよ 1:文字列の任意の場所にアルファベ…

UVa 11475 : Extend to Palindromes

問題リンク : http://uva.onlinejudge.org/external/114/11475.html問題概要: 大文字か小文字のアルファベットからなる空ではない文字列が与えられる この文字列に0以上のアルファベットを追加して長さが最小の回文を作れ解法: 与えられた文字列の後ろか…

UVa 10616 : Divisible Group Sums

問題リンク:http://uva.onlinejudge.org/external/106/10616.html問題概要: n個の要素からなる配列A[i](0 配列A[i]からM個の要素を選んだ時、その和がDで割りきれるような選び方は何通り存在するかクエリーは以下の形式からなる D M D,Mは上の説明に登場す…

UVa 12532 : Interval Product

問題リンク: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…

UVa 10445 : Make Polygon

問題リンク:http://uva.onlinejudge.org/external/104/10445.html問題概要: 多角形が与えられる その多角形の連続する3点からなる角度の最大と最小を求めよ解法: 全ての角度をみてその中の最大と最小を求める 入力は時計回りで与えられるのか反時計回りで…

UVa 11505 : Logo

問題リンク: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>…

UVa 11792 : Krochanska is Here!

問題リンク: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つ前と1…

UVa 10637 : Coprimes

問題リンク:http://uva.onlinejudge.org/external/106/10637.html問題概要: 整数Sをt個のco-primeな値に分割したものを全て出力せよ解法: dfsで枝刈りしながら探索した brute forceな感じが。。。(正しくは素数使ってなんたらららしい) 全探索する過程…

AOJ 1287 : Stopped Watches

問題リンク:Stopped Watches | Aizu Online Judge問題概要: n個の時計の情報が与えられる ただ、どれが秒針でどれが分針、時針なのかはわからないし どこを基準に数えているのかも分からない 全ての時計がとりうる時間の間隔のうちもっとも短いものを出力…

UVa 10382 : Watering Grass

問題リンク:http://uva.onlinejudge.org/external/103/10382.html問題概要: 略解法: 円と長方形が交差する場所のx座標を計算で求める 円の中心点の座標を(x,y)、円の半径をrとすると 円と長方形が交差する場所のx座標(以下 nx)は以下の通り nx = +sqrt(r*…

UVa 10136 : Chocolate Chip Cookies

問題リンク:http://uva.onlinejudge.org/external/101/10136.html問題概要: 複数の点が与えられる 好きな場所に直径5cmの円を置いたときにその円の内部に入る点の数を最大化せよ解法: AOJ1132やAOJ0090と同じ問題 円の半径が2.5になっただけある2点を決…

652 : Eight

問題リンク:Eight問題概要: 8パズルを完成させるために必要な最小の手数の経路を復元せよ解法: IDA*で解いた ヒューリスティック関数では現在のパズルの状態から目的の状態(パズルが解けた状態)へのマンハッタン距離の総和を求めた 例えば、次の状態に…

UVa 10181 : 15-Puzzle Problem

問題リンク:http://uva.onlinejudge.org/external/101/10181.html問題概要: 15パズルを完成させるために必要な最小の手数の経路を復元せよ解法: IDA* IDA*自体は UVa 652 : Eightとまったく同じ そのパズルが解けるかどうかの判定は異なる これはグーグ…