問題 グリッドを左上から右下まで移動した。移動したマスは'#'であり、そうでないマスは'.'である。何度も同じ場所を行き来することもある。右または下にだけ移動した可能性のある場合は"Possible"、そうでない場合は"Impossible"を出力せよ。
問題 の順列がある。数列は単調増加、数列は単調減少するような数列で、 $$ A_{P_i}\ +\ B_{P_i} \lt A_{P_{i+1}}\ +\ B_{P_{i+1}} $$ を満たすような数列のペアを1つ出力せよ。 は集合 の要素を並び替えた順列
問題文 個の箱が一直線上にあり、各々に個の玉が入っている。隣接する箱の玉の数の和を個以下にするために、取り出す必要のある玉の数を答えよ。
この記事は Aizu Advent Calendar 2016 2日目の記事です。 前の人は、@___deraさん、次の人は @hnjk さんです。 C++でよく使われる動的配列に、std::vectorがあります。std::vectorはで配列の要素へのアクセス、push_backなどの操作が可能なデータ構造です。…
問題 の2次元グリッドがあり、各マスにはワープする先のマスの座標が与えられる。ループの数を数え上げよ。
問題 Road Construction | Aizu Online Judge 頂点、辺の連結グラフが与えられる。各辺には距離と建設コストが与えられる。0番目が首都であり、各ノードから首都までの距離を与えられたグラフと同じにするものとして、一から連結グラフを生成するための最小…
問題 9枚のカードがある。そのうち3枚が、同じ色で、かつ同じ数字または連番のとき、3枚を1セットとみなす。3セット揃っているかどうか調べよ。数字は1〜9までの値で、連番とは3,4,5のようなものを指す。9,1,2は連番ではないことに注意せよ。
問題 Country Road | Aizu Online Judge 限界集落には一直線上の道があり、電気の通らない家々が立ち並ぶ。 個の家が数直線状に並び、個の発電機が与えられる。全ての家に発電機から出る電気を行き渡らせたい。 発電機から出る電気は家同士を電線で結ぶこと…
問題 インビジブル | Aizu Online Judge 2人でカードゲームをする。各々デッキを持つ。カードには数字がかかれている。-1は妨害カードで、それ以外は正の得点となるカードである。2人は交互にプレイする。プレイヤーは、カードを場のスタック上に置くか、パ…
問題 文字列から部分列を取り出し、最長の回文を作れ。複数ある場合はそのうち1つを出力せよ。
問題 B: Median Pyramid Easy - AtCoder Grand Contest 006 | AtCoder 段目に個のブロックがあり、ピラミッド型に積まれている。 ブロックには数字がかかれていて、あるブロックの数字はその左下と真下と右下のブロックに書かれた数字の中央値である。 ブロ…
問題 一般グラフにおいて辺数最大マッチングのサイズを求めよ。 解法 蟻本P198や組合せ最適化P271 系10.9 に載っているTutte行列を用いて最大マッチングを求めるLovaszのランダム化アルゴリズムを使う。 別の解法としては、Edmondsの辺数最大マッチングアル…
問題 巡回コースの通過点のリストが与えられる。個の通過点と人のプレイヤーがいる。各通過点は座標に存在し、得られる得点がである。各プレイヤーは名前と移動できる最大距離を持つ。各プレイヤーは原点から移動を始め、入力の通過点のうち幾つかの通過点の…
問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2397 縦に長いグリッドが与えられる。の位置からの位置に移動したい。移動の方法は、左下に、真下、右下のいずれかである。途中、個の障害物が有り、その場所は移動できない。移動の方法は何…
問題 山脈の高さの列が与えられる。山を登るときは高さの最大値を記録して登る。左から登った人と右から登った人の記録が与えられる。このとき、本当の高さの列としてありうるパターン数をで求めよ。記録に矛盾がある場合もあるので、そのときは0と出力せよ。
問題 個のケーキが種類ある。各種類個ずつ存在する。毎日1個ずつ食べるとして、全てのケーキを食べ終えたとき、前日と同じケーキを食べる回数の最小値を出力せよ。
問題 D: Friction - CODE FESTIVAL 2016 qual C | AtCoder のブロックがある。各ブロックは赤、緑、青のいずれかである。1度の操作で、一番下の行あるブロックのうち1つを消すことができる。消すときにかかるコストは、消した列の各ブロックの横に隣り合うブ…
問題 http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2016/E.pdf 以下のような文脈自由文法()が与えられる。 これに沿って書かれた1つの等式を表す文字列 がある。各文字は '0', '1', '(', ')', '+', '-', '*', '=' で構成される。等式の一部または…
問題 http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2016/D.pdf 2つの文字列 がある。一つの部分文字列のアナグラムが、他方の部分文字列に一致するような文字列の最長の長さを求めよ。
問題 長いレーンのベルトコンベアが 列ある。はじめ各ベルトコンベアにはその番号の種類の品物のみが乗っている。隣接するベルトコンベアの間の位置に、 個のアームが存在する。これらは上下に隣接するレール間で品物を動かすことができる。レーンを抜けたと…
問題 Decoding Ancient Messages | Aizu Online Judge のグリッドの各マスに文字が書かれている。ここから 文字抽出する。抽出する文字は同一行または同一列に存在してはいけない。任意の順番で抽出して並べたとき、作ることのできる辞書順最小の文字列を求…
問題 D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder の順列を考える。数 は、数 の前にあるという情報が 個与えられる。条件を満たす順列の総数を求めよ。 のペアはすべて相異なる。 全ての情報に合致する並びが少なくとも1つ存在する。
問題 Cosmic Market | Aizu Online Judge のグリッドがある。各マスには人がいて、はじめ全員が座っている。指定された行、または列に対して「立つ」または「座る」というクエリが回与えられる。最後に立っている人の数を答えよ。
問題 D: アンバランス / Unbalanced - AtCoder Beginner Contest 043 | AtCoder文字列について、過半数を超えている文字があれば、その文字列はアンバランスであるという。 文字列が与えられる。の部分文字列について、アンバランスなものがあれば、その始点…
問題 Repeated Subsequences | Aizu Online Judge文字列が与えられる。適当な位置で分割したとき、最長共通部分列をとる。 最適な位置で分割したときの最長共通部分列となる文字列を出力せよ。
問題 https://icpcarchive.ecs.baylor.edu/external/69/6905.pdf2隻の船がある。また、(船の運用期間, 得られる金額) のペアで表された企画が個与えられる。 2隻の船だけを用いて運用できるようなスケジューリングをして、得られる金額の総和を最大化せよ。 …
問題 何日目に対して、バスに乗る回数と電車に乗る回数が与えられる。 バス、電車それぞれに1回乗る券の他に、 1日バス乗り放題券、1日バス・電車乗り放題券 7日バス乗り放題券、7日バス・電車乗り放題券 30日バス乗り放題券、30日バス・電車乗り放題券 が存…
解いたことあるような気がする問題 d.hatena.ne.jp No.274 The Wall - yukicoder 説明 codeforces.com
まずは蟻本から Intervals (POJ No.3680) 個の重み付き閉区間がある。i番目の区間はをカバーし、重みを持つ。この中から個より多くの区間で覆われている点が存在しないように幾つかの区間を選び、重みの和を最大化せよ。 の場合、個の区間から互いに交差しな…
増加パスの概念は、より一般的なネットワークフローの問題に拡張できる。 Gを各辺[u, w]が容量とフローの1ユニットごとのコストcost(v, w)を持つグラフとする。 簡単のため、コストを歪対称的(skew symmetric)とする。すなわち (1) フローfのコストは、(2) …
