さっきこの問題を解きました。agc006.contest.atcoder.jpn段のピラミッドの最も下の段のブロックに1~2 * n - 1の数字が一回ずつ書かれています。そこから上の段のブロックについては、自分のブロックの真下、左下、右下の中央値が書かれます。今、頂点の値x…

arc064.contest.atcoder.jp2,3分遅れてスタート→C問題で3回WA、その後AC→D考えてるうちに寝落ち→Eを提出するもWA って感じでした。これはひどい。C問題: 左側から順に求めていくのと右側から順に求めていくの2通りやりましたがその必要はなかったっぽい。非…

今回はこの問題です。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番目の駐車場所に駐車しま…

今回はこの問題です。abc008.contest.atcoder.jp問題文はめどいので省略します…単純な話ですが文章で説明するのは大変です。この問題のやっかいなところは、wやhが10^6まで大きくなることです。メモ化するにも工夫が要ります。 今回はmapを使いました。キー…

今回はこの問題です。abc022.contest.atcoder.jp頂点n個、辺m本からなる重みつきグラフが与えられます。頂点1を通る閉路(おなじ道を2回以上通らない)のうち、重みの和の最小値を求めましょうという問題です。ダイクストラ法やワーシャルフロイド法ではおなじ…

今回はこの問題です。abc035.contest.atcoder.jpn箇所の町をつなぐ道がm本あります。それぞれの道について、町aから町bへc分をかけて移動することができます(反対方向には移動できません)。またそれぞれの町について、1分滞在するごとにお金をA[i]だけ手に入…

arc060.contest.atcoder.jp爆死しました。C問題部分点(しかも解いたのかなり遅い)のみでした。 しかもコンテスト終了後10分後にこの問題がACしたのでとてもつらい。メモっておきます。arc060.contest.atcoder.jp数字が書かれたn枚のカードがあります。このう…

今回はこの問題です。agc001.contest.atcoder.jpn頂点からなる木があります。直径がK以下の木にするために削る必要のある頂点数の最小値を求めてください、という問題です。 解説を見て解きました。 #include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #inc</sstream></cstring></cmath></iostream></cstdio>…

本日最後の問題はこれです。abc012.contest.atcoder.jpn地点とm本のバスの情報が与えられます。バスはa地点とb地点を時間tかけて移動します。バスはそれぞれその区間を往復し、行きも帰りも同じ時間かかり、好きな時間に乗ることができる(=バス同士ののりつ…

今回はこの問題です。abc011.contest.atcoder.jp高橋君は上下左右に距離dだけ移動できます。それぞれ1/4の確率で移動します。初期値が(0, 0)で目標地点が(x, y)であるとき、ちょうどn回の移動で目的地点に辿り着ける確率はどれだけでしょうか、という問題で…

今日は3問ときました。順にメモ。 まずはこの問題。abc013.contest.atcoder.jp縦線n本、横線m本からなるあみだくじを、d個縦につなげたあみだくじを考えます。 左から1~n本目それぞれについて、あみだくじの結果左から何番目にたどり着くかを求めましょう、…

今回はこの問題を解きました。abc010.contest.atcoder.jpあるSNSにおいて、0からn-1のn人の友人関係が与えられます。このSNSにおいては直接友達ではない人でも、自分の友達を介することでその人からのメッセージをみることができます。このうち、指定されたp…

今回はこの問題です。abc016.contest.atcoder.jp 多角形の各頂点と、線分の２端点があたえられます。線分で多角形を切断した時、多角形はいくつに分割されるでしょう、という問題です。(多角形の辺と直線の交点 / 2) + 1が答えとなります。 辺と直線の交点と…

今日はこの問題を解きました。abc018.contest.atcoder.jp 女子がn人、男子がm人います。またチョコレートがr個あり、それぞれどの女子からどの男子へ渡されるものか、そのチョコレートが渡された場合どのくらい幸福度が増えるかが決まっています。女子p人、…

昨日ABCの問題を解きました(バイトがあったので時間には間に合いませんでしたが…)abc043.contest.atcoder.jpA、B、Cは省略。Cはnが小さいので全探索で行けました。D問題だけメモ。 アンバランスな文字列(過半数が同じ文字となる文字列)は、少なくとも1カ所で…

今日はこの問題を解きました。abc002.contest.atcoder.jpn人の知り合い関係が与えられます。全員が互いに知り合いのグループを作るとき、最大何人のグループができるでしょうか、という問題です。今回nの最大値が12ということで、bitDPを用いました。また知…

昨日この問題を解きました。abc034.contest.atcoder.jp wとhの値が与えられます。(w+h)Cw % (10^9+7)の値を求めよ、という問題です。 wとhの値が小さければ動的計画法が使えるのですが、今回はwとhのどちらもmax10^5ということで使えません。 今回は(w+h)Cw …

ABCの3完53位でした。Cは一回WAしました。 Aは文字列の連結、Bは基本的な動的計画法だったのではしょります。C問題だけメモ。tkppc2.contest.atcoder.jpn個の0と1からなる数列があります。このうちk個の0を1にかえて、できるだけ1が連続するような部分列をつ…