今回はこの問題です。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が連続するような部分列をつ…

この問題を解きました。tenka1-2016-quala.contest.atcoder.jp問題設定がややこい感じもしますが、解法を思いつくのはそんなに難しくない気がします、ただ実装が大変だった。答えはこちら #include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #inc</iostream></sstream></cstring></cmath></iostream></cstdio>…