問題 n頂点m辺からなる連結な無向グラフが与えられる。そのグラフに含まれる単純閉路（同じ頂点を二度通らないような閉路）の個数を求めよ。 制約条件 n≦10万 m≦n+15

問題 長さnの文字列がありその一部の情報が以下のどれかの形式で与えられる。 x文字目がcである l文字目からr文字目がh文字目からと等しい このときq個のクエリ、x文字目が何の文字であるか、あるいは与えられた情報からではわからないかを答えよ。 制約条件…

Hは解説みて通しはしたけど解法の意味がわからない。 問題 n人の乗客がいてそれぞれ駅s[i]からt[i]まで電車に乗る。 全員が座るためには各人が席を指定できないとき、最小でいくつの座席が必要であるか、 また各人が自由に席を指定できるとき最小でいくつの…

問題 全ての辺の長さが1の正四面体ABCDの頂点Aから二つの点p, qが与えられた向きに与えられた長さだけ進む。 点は正四面体の辺を通過するとき、辺と進む向きの角度が変化しないように進む。 移動後に二つの点が同じ面の中にいるかを判定せよ。 制約条件 移動…

問題 重み付きの有向グラフが与えられる。i番目の辺の向きを反転させたとき、1番から2番の頂点への最短路が 短くなる 変化しない 長くなる のいずれであるかをそれぞれ出力せよ。 制約条件 グラフの辺と頂点≦10万 辺の重みは正整数で10万以下

Dむずくて通せてないですごめんなさい。 問題 n個のセルが黒または白で塗られている。 セルの初期状態およびゴールの状態が与えられる。 セルは一度の操作で連続する1〜k個を好きな色に塗ることができる。 最小で何回の操作で全てのセルをゴールの状態にでき…

問題 とても読みにくい問題文。 n人の人がt秒以内に機械(m1, m2, m3, ...)を使う。 同時に一人一個の機械しか使えず、一つの機械は同時に一人でしか使えない 各人はm1から順にとばさずに機械を使う必要がある 各機械は、1番目の人から順に使用する。i番目の…

問題 平面上にm個の点が与えられる。その中から相違なる2n点を選び、n本の線分を作る。（nは自由） n本の線分のうち、平行であるペアの個数を最大化したい。 そのようなペアの個数の最大値はいくつか。 制約条件 m≦16 座標は絶対値1000以下の整数

問題 黒と白の円盤を積み上げてタワーを作る。タワーは以下の条件を満たす必要がある 一枚以上の円盤がある 円盤の厚さの合計はl以下 最も外側の円盤は黒 同じ色同士の円盤が隣り合ってはいけない 黒の円盤は厚さ1またはkのどちらかを選ぶことができて、白の…

問題 面積の等しい三角形A, Bが与えられる。 三角形Aに対し等積変形（二頂点を固定し、残り一頂点を三角形の面積が変わらないように動かす操作）を繰り返し三角形Aを三角形Bに重ねたい。 必要な操作の最低回数（あるいは4回以内にはできない）を求めよ。

問題 日本語なので略 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1622&lang=jp

問題 日本語なので略 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1621&lang=jp

問題 与えられた論理式と常に同じ出力を返すような論理式のうち長さが最小のものを求めよ。 論理式の変数は4つまで、長さは16まで。

問題 各成分が0, 1であらわされる行列Aが与えられる。 Aの行の部分集合A[i]で、任意の列jに対してΣi_s[i][j]が偶数になるものを考える。 このようなA[i]のうち最大のサイズはいくつか。 例）Aが 010 011 110 101 だったら、2, 3, 4行目を選ぶと全ての列の和…

問題 日本語なので略 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1618&lang=jp

問題 日本語なので略 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1617&lang=jp

問題 日本語なので略 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1616&lang=jp

問題 K日間にわたって写真を撮る。カメラの記憶容量はLであり、写真一枚が消費する記憶容量は非圧縮の場合Dである。 i日目にはti枚の写真を撮り、j番目の写真のできばえはQijである。 写真は好きなものを好きなだけ削除することができる。 また、同じ日の写…

問題 無限に広いグリッドがある。 N個の長方形があり、(xi, yi)を左下, (Xi, Yi)を右上としていて、範囲のマスにそれぞれ一人ずつ人間がいる。 長方形は重ならない。 M個の爆弾があり、(bxi, byi)に置かれていて、p1iの確率で、y = byiの直線にいる人が全員…

問題 無向木で表されるような島と橋が与えられる。 辺の重みが、橋を渡る時間であり、その橋を壊す時間である。（両者は等しい） 好きな島から出発し、橋を渡るか、今いる島につながっている橋を壊すかすることができる。 終了時には好きな島にいてよい。 全…

問題 n頂点からなる無向木が与えられる。 各頂点には重みwiがついている。重みの初期値が与えられる。 この木に対して次のようなクエリがq個来るので、答えよ。 t a b c t = 1のとき、木の頂点aから頂点bへのパス上にある頂点全ての重みをcに変更する。 t = …

問題 n組の封筒のペア(p[i], q[i])がある。 p[i], q[i]の封筒にはそれぞれ、コインが2枚ずつ入っている。 それぞれのコインは整数で表される種類がある。 n組のペアについて、高々片方の封筒を取っていく。（どちらも取らないことができる） こうして取り終…

年齢制限のため、今年が僕の最後のICPCでした。 東京大学、チームwakabaで参加しました。 結果は4位でした。 元々僕は、プロコンの界隈にICPCから入ったので、 ICPCは原点であり、ICPCで世界大会に行くことが最終目標でもありました。 その最終目標こそ達成…

問題 根付き木が与えられる。 それぞれの頂点には重みがついている。 今、この木からちょうどk個の頂点{a1, a2, ..., ak}を選ぶ。 ここで、i != jなる任意の1≦i, j≦kについて、aiがajの先祖であってはならない。 このとき、選んだ頂点の重みの和の最大値を求…

問題 n人の人が平面上にいて、それぞれの座標が与えられる。 これらの人が、合計でm個、次のような目撃証言をした。 「私は、a[i]がb[i]よりも先に銃を撃つのを聞いた」 音の進む速さは有限であるので、 先に銃を撃つ音が聞こえた者が、先に発砲したとは限ら…

問題 道が碁盤の目状の街において、 家(0,0)から学校(N,M)まで、←または↓への移動をちょうどK回だけして辿り着く方法は何通りあるか。 X座標またはY座標が負になるような点には入ることはできないが、 X座標がNを超える、またはY座標がMを超えるような点に入…

問題 nxmマスの各マスが0または1のグリッドimageが与えられる。 pxpマスの各マスが0または1のグリッドpatternが与えられる。 imageの中にpatternはいくつ含まれるか求めよ。 patternが別の箇所に現れた場合、それらは別々にカウントする。 patternは上下左右…

問題 n桁の整数が与えられる。 この整数の長さ1以上の連続する部分文字列となる整数で、Qの倍数であるようなものはいくつあるか。 ただし、部分文字列の先頭は0であってはいけない。 Qは素数である。 制約条件 n≦10^5 Q≦10^8

問題 折れ線がつながってジグザグな一本の線になっている山道がある。 線の左端は(0,0)で、右端のy座標も0である。 二人の登山家が左端の頂点と、右端の頂点を同時に出発して出会いたい。 二人は、常に等しい高さに居るという制約を満たしながら動かなければ…

問題概要 nxmマスのパネルがある。 それぞれのパネルはONかOFFのいずれかである。 一つのパネルを押すと、そのパネルに加えてマンハッタン距離がちょうどdのパネルも全てON,OFFが反転する。 このとき、全てのパネルをOFFの状態にできるか答えよ。 制約条件 n…