AOJ2741 Invisible

問題 インビジブル | Aizu Online Judge 2人でカードゲームをする。各々デッキを持つ。カードには数字がかかれている。-1は妨害カードで、それ以外は正の得点となるカードである。2人は交互にプレイする。プレイヤーは、カードを場のスタック上に置くか、パ…

AOJ2035 It Prefokery Pio

問題 文字列から部分列を取り出し、最長の回文を作れ。複数ある場合はそのうち1つを出力せよ。

AGC 006: B Median Pyramid Easy

問題 B: Median Pyramid Easy - AtCoder Grand Contest 006 | AtCoder 段目に個のブロックがあり、ピラミッド型に積まれている。 ブロックには数字がかかれていて、あるブロックの数字はその左下と真下と右下のブロックに書かれた数字の中央値である。 ブロ…

LiveArchive 5874 Social Holidaying

問題 一般グラフにおいて辺数最大マッチングのサイズを求めよ。 解法 蟻本P198や組合せ最適化P271 系10.9 に載っているTutte行列を用いて最大マッチングを求めるLovaszのランダム化アルゴリズムを使う。 別の解法としては、Edmondsの辺数最大マッチングアル…

LiveArchive 5875 Orienteering

問題 巡回コースの通過点のリストが与えられる。個の通過点と人のプレイヤーがいる。各通過点は座標に存在し、得られる得点がである。各プレイヤーは名前と移動できる最大距離を持つ。各プレイヤーは原点から移動を始め、入力の通過点のうち幾つかの通過点の…

AOJ2397 Three-way Branch

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2397 縦に長いグリッドが与えられる。の位置からの位置に移動したい。移動の方法は、左下に、真下、右下のいずれかである。途中、個の障害物が有り、その場所は移動できない。移動の方法は何…

CODE FESTIVAL 2016 qual C - C: 二人のアルピニスト

問題 山脈の高さの列が与えられる。山を登るときは高さの最大値を記録して登る。左から登った人と右から登った人の記録が与えられる。このとき、本当の高さの列としてありうるパターン数をで求めよ。記録に矛盾がある場合もあるので、そのときは0と出力せよ。

CODE FESTIVAL 2016 qual C - B: K個のケーキ

問題 個のケーキが種類ある。各種類個ずつ存在する。毎日1個ずつ食べるとして、全てのケーキを食べ終えたとき、前日と同じケーキを食べる回数の最小値を出力せよ。

CODE FESTIVAL 2016 qual C - D: Friction

問題 D: Friction - CODE FESTIVAL 2016 qual C | AtCoder のブロックがある。各ブロックは赤、緑、青のいずれかである。1度の操作で、一番下の行あるブロックのうち1つを消すことができる。消すときにかかるコストは、消した列の各ブロックの横に隣り合うブ…

ICPCOOC2016 E: Infallibly Crack Perplexing Cryptarithm

問題 http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2016/E.pdf 以下のような文脈自由文法()が与えられる。 これに沿って書かれた1つの等式を表す文字列 がある。各文字は '0', '1', '(', ')', '+', '-', '*', '=' で構成される。等式の一部または…

ICPCOOC2016 D: Hidden Anagrams

問題 http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2016/D.pdf 2つの文字列 がある。一つの部分文字列のアナグラムが、他方の部分文字列に一致するような文字列の最長の長さを求めよ。

ICPCOOC2016 C: Distribution Center

問題 長いレーンのベルトコンベアが 列ある。はじめ各ベルトコンベアにはその番号の種類の品物のみが乗っている。隣接するベルトコンベアの間の位置に、 個のアームが存在する。これらは上下に隣接するレール間で品物を動かすことができる。レーンを抜けたと…

AOJ2679 Decoding Ancient Messages

問題 Decoding Ancient Messages | Aizu Online Judge のグリッドの各マスに文字が書かれている。ここから 文字抽出する。抽出する文字は同一行または同一列に存在してはいけない。任意の順番で抽出して並べたとき、作ることのできる辞書順最小の文字列を求…

ABC041 D: 徒競走

問題 D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder の順列を考える。数 は、数 の前にあるという情報が 個与えられる。条件を満たす順列の総数を求めよ。 のペアはすべて相異なる。 全ての情報に合致する並びが少なくとも1つ存在する。

AOJ1079 Cosmic Market

問題 Cosmic Market | Aizu Online Judge のグリッドがある。各マスには人がいて、はじめ全員が座っている。指定された行、または列に対して「立つ」または「座る」というクエリが回与えられる。最後に立っている人の数を答えよ。

D - アンバランス / Unbalanced

問題 D: アンバランス / Unbalanced - AtCoder Beginner Contest 043 | AtCoder文字列について、過半数を超えている文字があれば、その文字列はアンバランスであるという。 文字列が与えられる。の部分文字列について、アンバランスなものがあれば、その始点…

AOJ2090 Repeated Subsequences

問題 Repeated Subsequences | Aizu Online Judge文字列が与えられる。適当な位置で分割したとき、最長共通部分列をとる。 最適な位置で分割したときの最長共通部分列となる文字列を出力せよ。

LiveArchive 6905 Two Yachts

問題 https://icpcarchive.ecs.baylor.edu/external/69/6905.pdf2隻の船がある。また、(船の運用期間, 得られる金額) のペアで表された企画が個与えられる。 2隻の船だけを用いて運用できるようなスケジューリングをして、得られる金額の総和を最大化せよ。 …

LiveArchive 6904 Travel Card

問題 何日目に対して、バスに乗る回数と電車に乗る回数が与えられる。 バス、電車それぞれに1回乗る券の他に、 1日バス乗り放題券、1日バス・電車乗り放題券 7日バス乗り放題券、7日バス・電車乗り放題券 30日バス乗り放題券、30日バス・電車乗り放題券 が存…

2-SAT

解いたことあるような気がする問題 d.hatena.ne.jp No.274 The Wall - yukicoder 説明 codeforces.com

重み付き区間スケジューリング

まずは蟻本から Intervals (POJ No.3680) 個の重み付き閉区間がある。i番目の区間はをカバーし、重みを持つ。この中から個より多くの区間で覆われている点が存在しないように幾つかの区間を選び、重みの和を最大化せよ。 の場合、個の区間から互いに交差しな…

Data Structures and Network Algorithms: 8.4 最小費用流

増加パスの概念は、より一般的なネットワークフローの問題に拡張できる。 Gを各辺[u, w]が容量とフローの1ユニットごとのコストcost(v, w)を持つグラフとする。 簡単のため、コストを歪対称的(skew symmetric)とする。すなわち (1) フローfのコストは、(2) …

UoA練習会 2016 VC 035 メモ

Regionals 2014 :: Asia - Daejeon B - 6895 Deduction BruteForceっぽい I - 6902 Three Squares 似た問題がTopCoderであったな…TopCoder SRM614 DIV1 EASY - MinimumSquare - ゲームにっき(仮)別館(仮) K - 6904 Travel Card 状態はバスと電車それぞれ…

UVa1229 Sub-dictionary

問題 https://uva.onlinejudge.org/external/12/1229.pdf 個の単語が載っている辞書がある。すべての単語を理解したい。 サンプルの場合、 5 aue oizer piqoi oizer doy oizer hweqlo hweqlo hweqlo piqoi aue oizer piqoi piqoi aue aue 0 となっていて、「…

UVa410 Station Balance

問題 https://uva.onlinejudge.org/external/4/410.html Given chambers which can store 0, 1 or 2 specimens, specimens and a list of the masses of the specimens, determine which chamber should store each specimen in order to minimize imbalance.

AOJ0091 Blur

問題 にじみ | Aizu Online Judge 布に染料を垂らす。染料は小中大の三種類あり、それぞれ広がる幅が異なる。 N滴落とした布の状態が与えられるので、染料を落とした座標を復元せよ。 染料は同じ場所に何度も落とすことが出来る。 N

AOJ2328 Mobile Network

問題 Mobile Network | Aizu Online Judgeネットワークが与えられる。帯域幅として各辺にxの多項式が重みづけられている。 1番目のノードからN番目のノードまでトラフィックを流したとき、流れる量を最大化せよ。

LiveArchive 7230 Log Jumping

問題 https://icpcarchive.ecs.baylor.edu/external/72/7230.pdfN個の丸太を円形に並べる。それぞれ高さH[i]を持つ。隣接する丸太の高さの最大値を最小化せよ。

LiveArchive 7227 Equilibrium State

問題 https://icpcarchive.ecs.baylor.edu/external/72/7230.pdfXY平面に、M個のばねとN個の物体が釣り合って、K個の定点で固定されている。物体の重さはなく、バネのたるみもない。 ばね定数と、定点の座標が与えられるので、物体の座標を順に求めよ。 バネ…

LiveArchive 7226 Coin Swap

問題 https://icpcarchive.ecs.baylor.edu/external/72/7226.pdf白または黒の何れかが塗られたノードを持つグラフがある。 はじめ、白または黒のコインが、ノードの色の数と同じ数だけバラバラのノードの1つずつ置かれている。 コインを隣接するノードのコイ…