srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

2016-10-02から1日間の記事一覧

SRM 694 div2 medium DistinguishableSetDiv2

問題 問題概要 n人の人に対して、m個の質問をした。n人の人がそれぞれの問題に対してどのように答えたが与えられている。m個の問題の中から、問題の部分集合を考え、その時の問題に対するn人の解答のみから、n人全員を区別できるか判定する。これをm個の問題…

SRM 694 div2 easy MakingPairs

SRM

問題 問題概要 それぞれのカードが何枚あるかが与えられる。同じ数字通しはペアにすることができる。最大ペアは何組できるか、同じカートを二度使うことはできない。 解法 同じカードの枚数をそれぞれ2で割れば、ペアの数がわかるので、それらの合計を出すだ…

SRM 695 div1 easy BearPasswordLexic

問題 問題概要 x = {4, 2, 1, 0}のとき、長さ4の文字列で、その中に、1文字の連続文字列が4つ(b, a, a, a)、2文字の連続文字列が2つ(aa, aa)、3文字の連続文字列が1つ(aaa)、4文字の連続文字列が0つである文字列を出力すればいい。文字列が作れないなら、空…

SRM 695 div2 medium BearPasswordAny

問題 問題概要 x = {4, 2, 1, 0}のとき、長さ4の文字列で、その中に、1文字の連続文字列が4つ(b, a, a, a)、2文字の連続文字列が2つ(aa, aa)、3文字の連続文字列が1つ(aaa)、4文字の連続文字列が0つである文字列を出力すればいい。文字列が作れないなら、空…

SRM 695 div2 easy BearNSWE

SRM

問題 問題概要 (0, 0)から方角と距離を指定された通り、ある点まで動く。ある点までの移動距離と、ある点から(0, 0)までの距離の合計を求める。 解法 スタート地点を(0, 0)として、ゴールの座標を計算する。(0, 0)とゴールの座標がわかったので、その間の距…

codeforces 374 div2 D. Maxim and Array

問題 問題概要 数列aが与えられる。この数列の積を最小に知るために、k回数列の数字を+xまたは、-xすることができる。どのように数列を変えるかを求めよ。 解法 重要な考察が、数列のすべての数字の積を大きくするには、一番小さい数字を大きくしていけばい…

aoj 1156 - Twirling Robot

問題 問題概要 盤面に命令が書いてある。命令通りに行動すればコストは0。命令以外の行動をすれば、コストは指定された通りのコストがかかる。スタートからゴールまで行くのにかかる最短コストを求めよ。 解法 拡張ダイクストラで解いた。頂点の状態に番号だ…

aoj 2021 - Princess in Danger

問題 問題概要 スタートからゴールまで冷凍されたものを溶かさずにもっていけるかを求める問題。冷凍されたものは最大でm時間保存することができ、時間がたつと解ける。与えらた条件にある頂点で氷を冷凍することができる。溶かさずにゴールまで行く最短時間…