解法 ワーシャルフロイドした後、１つ中継点を決めてソースから２つのシンクまでのコストの和を最小化する。 中継点を k とすると、 cost[S][k] + cost[k][g1] + cost[k][g2] とすればコストの和が求まるので、forループで和が最小となる k を決める。反省 …

解法 ２円の交点を全て求めて、交点の集合を得る。その交点それぞれがどの円に含まれるかを全て調べ、含む円の数をカウントし最大値を求めれば良い。 ２円の交点を求める際、complex の polar が便利。polar(r, θ) で、対応する複素平面における座標が求まる…

問題概要 数直線上にいる複数の猫が、それぞれの与えられた初期位置から絶対値Xだけ移動する。猫が最適な動き方をしたとき、猫のいる区間の中で最も端にいる２匹の距離を最小化せよ。解法 どの２匹が区間の端になるかを二重ループで決める。このときすべての…

問題概要 与えられた文字列から同種の文字を全てを削除することを任意回数繰り返す。残った文字列から "CAT" を作れるなら "Possible" 作れないなら "Impossible" を出力せよ。解法 与えらた文字列Sの中の文字を初めから見ていき、'C', 'A', 'T' のときだけ…

問題概要 トーナメント戦で自分とライバルが当たるのは何ラウンド目か求めよ。ライバルと当たるまでの試合は互いに全て勝つものとする。解法 自分とライバルの位置だけtrueにしたvectorを用意し、vectorの隣同士で比較し、論理和を取りながらtrue同士が衝突…