AtCoder

ARC061 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

問題 arc061.contest.atcoder.jp 考察 こういう1つのノードが複数の状態を持つグラフは、状態ごとにノードを分割してあげると上手くいくことが多いかと思います。 今回もご多分にもれず、駅と会社の2つをペアで考えてみます。 各行では駅2つと会社が与えられ…

AGC004 D - Teleporter

問題 agc004.contest.atcoder.jp 考察 K回の移動を行った際に全ての点が首都(1)にいないといけないという条件があります。 これにより、必ず1は1自身に戻るループにしないといけないことが分かります。 1以外の行き先だと、「全ての点が同着で1にいないと…

AGC004 C - AND Grid

問題 agc004.contest.atcoder.jp 考察 「解は必ず存在することが示せます。」というアヤシイ一文があります。 何となく簡単な解法がありそうです。 赤と青はそれぞれが連結で、紫のマス以外は両方塗られていてはいけません。 そこで、まずは各マスがいずれか…

AGC004 B - Colorful Slimes

問題 agc004.contest.atcoder.jp 考察 まず、魔法を使う回数はN回未満で事足ります。 N回以上だと2週目に入ってしまい、それであればちょうど1週したタイミングで飼えば良いからです。 また、飼うタイミングを調整することにより、魔法を何回掛けるかを調整…

ARC060 E - 高橋君とホテル / Tak and Hotels

問題 arc060.contest.atcoder.jp 考察 やることはとてもシンプルで、いかに高速化するかという問題のようです。 部分点解法 クエリ毎にaからbへ実際に移動してみれば、で間に合います。 満点解法 まず、距離の短い点が多くてもTLEしないようにしてみましょう…

ARC060 D - 桁和 / Digit Sum

問題 arc060.contest.atcoder.jp 考察 まず、nをb進数で表した際、各桁の合計がsになるかどうかは簡単に求まります。 一番時間がかかる2進数ですら、64回ループするだけで[tex: 1018]程度までカバーできるので。 (問題分の定義では再帰で書かれていますが、…

ARC060 C - 高橋君とカード / Tak and Cards

問題 arc060.contest.atcoder.jp 考察 まず、「平均がA」というのは「j枚取り出した時、合計がj*A」と言い換えられます。 これにより、各種状態を覚えやすくなりました。 制約が小さいので、必要な要素を覚える以下のようなDPをすれば良さそうです。 dp[i][j…