今回はこの問題です。arc037.contest.atcoder.jpn個の頂点とm本の辺からなる無向グラフがあります。このグラフの連結部分のうち、木になっているものはいくつあるか答えなさい、という問題です。union findを利用しました。解答はこんな感じ。 #include <cstdio> #in</cstdio>…

今回はこの問題です。arc024.contest.atcoder.jp赤または黒色の木が円周上にn本生えています。この木は１日ごとに、隣の2本の木と自分の色が同じであるとき、異なる色に変化します。隣の木が次にどうなるかは関係なく、その日の状態のみをみて変化します。何…

今回はこの問題。arc038.contest.atcoder.jph * wのマスがあります。このマス上には障害物があることがあり、「#」で表されます。 (1, 1)のマスに駒をおきます。駒が(i, j)にあるとき、プレイヤーは交互にこのマスを(i + 1, j), (i, j + 1), (i + 1, j + 1)…

今回はこの問題。arc028.contest.atcoder.jpプログラミングコンテストにn人が参加しました。順位はすでにわかっています。「上位i人のうちk番目に若い人」をそれぞれのi(k 回答はこんな感じ。 #include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <algorithm> </algorithm></sstream></cstring></cmath></iostream></cstdio>…

今回はこの問題です。arc031.contest.atcoder.jp10*10マスがあります。それぞれのマスにはoかxになっています。このうちxのマスをひとつだけoに変更することによって、すべてのoマスが連結するようにできるかどうかを判断しなさい、という問題です。ただし連…

今回はこの問題です。arc032.contest.atcoder.jpn個の町とm本の道路があります。それぞれの道路はa[i]とb[i]の町をつないでいます。 現在の状況に対して新たに道路を加えることで任意の町同士を行き来できるようにしたいです。 このとき新たに作らないといけ…

今回はこの問題。arc052.contest.atcoder.jpxyz空間上にn個の円錐が互いに重なり合わないように浮いています。どの円錐も底面がyz平面と平行で、x軸の正の方向にとがっています。i番目の円錐の底面の中心のx座標の値はx[i]、半径はr[i]、高さはh[i]です。2つ…

今回はこの問題。arc054.contest.atcoder.jp現在のコンピュータで解くとP年かかる問題があります。ムーアの法則により、いまからx年後のコンピュータの能力は2^(x/1.5)になり、解く時間もP/(2^(x/1.5))になります。計算時間は(今から計算を始めるまでの時間)…

解いたもののここに載せてないぶんがたまってきました。 今回はこの問題。arc044.contest.atcoder.jp頂点数n個のグラフがあります。それぞれ1~nまで番号が振られており、頂点1からの距離が与えられます。 条件を満たすようなグラフは何通りあるでしょうか、…

今回はこの問題です。arc043.contest.atcoder.jpn個の問題があります。i番目の問題の難易度はd[i]です。 n個のうち、次の条件を満たすように問題を4つ選びます。 i + 1番目の問題の難易度はi問目の問題の難易度の2倍以上になる。(i = 1, 2, 3) このとき、問…

昨日の夜AGCに参加していました。 AのみACと惨敗でした。しかもAはlong long つけ忘れて一回WAしました。 B問題についてメモしておきます。解説見たらスッとわかりました。agc004.contest.atcoder.jpn色のスライムがいます。高橋君は全色のスライムを飼いた…

今回はこの問題を解きました。arc022.contest.atcoder.jpNcmの細長いお菓子があります。このお菓子は1cmごとにブロックで分けられていて、i番目のブロックはAi番目の味がします。同じ味のブロックを二つ以上含まないひとつながりになった部分のうち、最も長…

今回はこの問題です。arc056.contest.atcoder.jpn箇所の駐車場所があります。お互いにm本の道によってつながっています。s番目の駐車場所が駐車場の入り口になっています。1番からn番目の人が順番に駐車していきます。i番目の人はi番目の駐車場所に駐車しま…