土下座しながら探索中

主に競技プログラミング

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分近く見つけ…