D - Menagerie どこか連続する2つの位置について羊狼の割り当てを決めると, 片側の決まった動物から, すべての場所の配置を決定することができます. よって, 1番目と2番目の羊狼の割り当て(2*2=4通り)を決め, それが条件を満たしているかどうかを確認し, 4つ…

D - Walk and Teleport 見た瞬間グラフを作って最小全域木を求めたくなりますが, どの頂点からどの頂点へもテレポートが可能であるため, 辺の数が最悪$10^{10}$以上に膨れることになるため, 最小全域木の構成は辛いです. そのため, 別の解法を考える必要があ…

D - Big Bang なかなか問題分が複雑で, 読解に苦労します. Pを求めるために, 以下の3つ ①平行移動のベクトル ②回転角度 ③相似拡大の大きさ を求める必要があります. A,Bの点のそれぞれの重心に着目すると, ①のみがその変化に関与していることがわかります. …

D - Good Grid 各マスが(p+q)%3 = 1 or 2 or 0 の3つのグループに分割できるため, それぞれのグループについてC通りの色を塗りつぶしたときの違和感をあらかじめ計算しておき, C^3通りの組み合わせを検証して最小値を出力して答えです. Submission #2910715 …

B - Colorful Slimes 高橋君は ・ xのコストを払って今飼っている各モンスターの色をi → (i+1+N) % N にする(操作1) ・ A[i]のコストを払って色iのモンスターを新たに飼う(操作2) の2つの行動ができます. 操作1をk回行うと決めると, A[i-0],A[i-1]..A[i-k]の…

B - Colorful Creatures 良問だと思います. まず, N個の入力のクリーチャそれぞれに対してそれぞれ固有の色が割り当てられますが, それぞれ固有の色であり, 色の数値の大小に対して優劣をつける操作がないため, 色を無視して大きさ順にソートをしても問題な…

Farey Sequence | Aizu Online Judge問題名から察せるとおり, n群目のファレイ数列の要素数を数える問題です. $n-1$群目のファレイ数列までわかっていると仮定したとき, $n$番目のファレイ数列の要素数は($n-1$群目の要素数+nと互いに素なn未満の自然数の数)…

D - 高橋君と見えざる手 / An Invisible Hand 問題文の情報量が多く, 情報を整理するのに時間がかかります. 高橋君が最適に行動したときの利益を1以上下げるために, りんごの価格を操作するというのが趣旨となります. まず高橋君の戦略を考えると, りんごが…

D - Score Attack グラフの問題としては少し特殊で, ゴールまでのコストを最大化する問題です. これは, すべてのコストを負にした最短経路問題を解くことで解を出せます. しかし, コストに負を含んでいるとダイクストラ法が使えません. そのため, ベルマンフ…

D - Fennec VS. Snuke ゲームの最善手問題です. 与えられるグラフが木構造であるというのが最大のポイントで, 閉路が存在しません. はじめに相手の色がある方へ向かって色を塗っていって相手の塗れる頂点を減らすのが最適解となります(木構造なので親を取っ…

ずっと放置してたABC101-D - Snuke Numbersを解きました. D - Snuke NumbersK番目のすぬけ数は$10^{15}$以下とありますが, $1$から$10^{15}$まで調べていると時間が足りないので, 解の候補を絞ってから解を探索する必要があります. 絞り方として, 末尾に9が…

ABC 095をセルフコンテスト. C問題までさくさく解けたがやはりD問題で詰まりました. D - Static Sushi 試行錯誤しながら実装し, なんとかサンプルと答えを合わせられたので提出するとぽつぽつとWA. あきらめて解説をちらちら見ると方針はあっていたので, 実…

昨日参加したSoundHound Inc. Programming Contest 2018 -Masters Tournament-のC,D問題の復習をしました. soundhound2018-summer-qual.contest.atcoder.jpC問題 C: Ordinary Beauty - SoundHound Inc. Programming Contest 2018 -Masters Tournament- | AtC…