SRM
問題 問題概要 はじめはX=0でそこからnumbersとして与えられた数字の中の任意のものとORをとり, Xを更新して再びnumbersの中の任意のものとのORを繰り返していく. この処理をどのように繰り返してもgoalに行けなくなるようにするには, numbersからいくつの数…
問題 問題概要 xが偶数のとき x / 2 xが奇数のとき x -= 1 ができる. [A, B]の数で上の操作を繰り返してKになるものの総数を求めよ. 解法 まず, 問題では小さくなる操作が与えられているが, 求めたいのはKになるかなので, Kから[A, B]の区間にいけるかを求め…
問題 問題概要 lmc(1..M)=lcm(N+1,M)となる最小のMを求める. 解法 まず, 1,..,N,N+1,…,M N+1,…,M のlcmが一致することから,1…Nの中にlcmを作るのに寄与したものがいないので, 1…Nのなかに含まれる最大の素数の2倍の数がすくなくともMまでに含まれていなけれ…
問題 問題概要 きつねの身長があたえられる. 円形に並べらた時, 隣あうきつねの身長差の絶対値の最大値Dとして, Dの最小値を求める. 解法 貪欲法でとけるみたい. 偶数番目を左側, 奇数番目を右側にして, 左側を昇順, 右側を降順にしてやればいいみたい. なん…
問題 問題概要 木構造の情報が与えられる. すべての辺のコストを1として, コストLいないで通ることができる頂点の種類数の最大値を求める問題. ただしstart地点を0として, start,goal も通った頂点としてカウントする. 解法 一番の方針として, 頂点を巡った…
問題 問題概要 Oは宝を含んでいる場所。?は宝を含んでいるかどうかがわからない場所。?の場所を宝が含んでいるか含んでいないかのすべての場合について、宝が含まれる可能性のある面積を求め、その合計を求める。 解法 今回は単純にbit全探索をすればいい。?…
問題 問題概要 1がA、2がB、、7がGと対応している。そして、8から順にまたそれが続く。この時、何種類のアルファベットを含んでいるか。 解法 周期7で繰り返すので、mod7をとって、その値をsetにいれて重複をなくせばいい。 ミス 特になし。 コード #include <iostream></iostream>…
問題 問題概要 カッコの文字列が与えられる。カッコが対応する形に変更する。ただし変更できる文字の数は、((文字数)/2)+1まで。 解法 動的計画法で解いた。変更できる文字の数に制限があるので、最小の数で対応づけができるものを求めた。dp[i][j] := i番目…
問題 問題概要 カッコの階層が最大どこまで行くか。どこまで深くいくか。 解法 '('の時は+1、')'の時は-1していくなかでの最大値が答えとなる。 ミス 特になし。 コード #include <iostream> #include <string> #include <vector> #include <cstdio> #include <algorithm> using namespace std; typedef lo</algorithm></cstdio></vector></string></iostream>…
問題 問題概要 LとRが与えられる。LとRの間に、2桁以上で、最後の２桁の数字が同じで数がいくつあるか。 解法 桁dpで解いた。dp[i][j][k] := 整数p(L, R)を考えた時に、i番目の桁まで考えて、j=1の時は考えている数がp未満であることが決定していて、j=0の時…
問題 問題概要 文字列AとBが与えられる。Bの文字の中には?が含まれていて、それを1または0に変換したものが、文字列Cとなる。文字列Aの連続部分列と文字列Bが一致いしている文字列Cの数を求める。(重複しているものは数えない) 解法 一番初めに思いついた解…
問題 問題概要 文字列がいくつか与えられる。その文字列のなかに同じものが2つ以上あるかを判別する。ただし、0(ゼロ)とO(オー)は同じもの、1（いち)とl(Lの小文字)とI(iの大文字)は同じものとして考える。 解法 方針としては、文字列を変換して、重複を確認…
問題 問題概要 AとBが与えられる。そのなかから、連続するK以上の部分のAの合計と、Bの合計をそれぞれ出して、(Bの合計)/(Aの合計) の最大値を求める。 解法 全探索で通る。単純にすべての区間について、(Bの合計)/(Aの合計)を出していけばいい。これだとn=1…
問題 問題概要 文字列Sが与えられる。その文字列がS = T + T となる文字列Tが存在するか。 解法 Tが2回続くので、TはSの文字列の長さの1/2なので、Sを前後で二等分した文字列どおしが同じものであるかを見ればよい。 ミス なし。 コード #include <iostream> #include <string></string></iostream>…
問題 問題概要 食堂にならんでいる。並んでいる順番で前から順に、その人がどんな行動をするかが与えられる。行動は2通りで、 b := 一番前に横入りする e := 最後尾に戻る である。先に並んでいたのに、前に横入りされると、不満がたまる。それぞれの人に対…
問題 問題概要 グラフはi - i+1 と i - i+2 を結ぶ２つ辺が貼られている。 二重連結グラフの状態を保ったまま辺を取り除き、辺のコストを最小にしたときの辺のコストの合計を求める。 解法 biconnected graph(2重連結グラフ)とは、任意の頂点を1つ取り除いて…
問題 問題概要 グラフが与えられる。そのグラフの中に三角形を作る。最小でいくつの辺を加えればできるか。 解法 まず、辺が1つもなければ、必要な最小の辺の数は3となる。次に辺がある場合を考える。u - v の辺がある場合を考える。このとき、u - x(xはvで…
問題 問題概要 n人の人に対して、m個の質問をした。n人の人がそれぞれの問題に対してどのように答えたが与えられている。m個の問題の中から、問題の部分集合を考え、その時の問題に対するn人の解答のみから、n人全員を区別できるか判定する。これをm個の問題…
問題 問題概要 それぞれのカードが何枚あるかが与えられる。同じ数字通しはペアにすることができる。最大ペアは何組できるか、同じカートを二度使うことはできない。 解法 同じカードの枚数をそれぞれ2で割れば、ペアの数がわかるので、それらの合計を出すだ…
問題 問題概要 x = {4, 2, 1, 0}のとき、長さ4の文字列で、その中に、1文字の連続文字列が4つ(b, a, a, a)、2文字の連続文字列が2つ(aa, aa)、3文字の連続文字列が1つ(aaa)、4文字の連続文字列が0つである文字列を出力すればいい。文字列が作れないなら、空…
問題 問題概要 x = {4, 2, 1, 0}のとき、長さ4の文字列で、その中に、1文字の連続文字列が4つ(b, a, a, a)、2文字の連続文字列が2つ(aa, aa)、3文字の連続文字列が1つ(aaa)、4文字の連続文字列が0つである文字列を出力すればいい。文字列が作れないなら、空…
問題 問題概要 (0, 0)から方角と距離を指定された通り、ある点まで動く。ある点までの移動距離と、ある点から(0, 0)までの距離の合計を求める。 解法 スタート地点を(0, 0)として、ゴールの座標を計算する。(0, 0)とゴールの座標がわかったので、その間の距…
問題 問題概要 aとbの数字が与えられる。aをfの数字で変えることができる。この操作を行って、aiとbiが異なる組数の最小値を求めよ。ただし、異なる数が増えてしまうような場合であっても、fはすべて使わないといけない。 解法 貪欲法で解いた。まず、一番最…
問題 問題概要 -と.を含んだ文字列sが与えられる。この文字列を並び替える。-の連続した部分をひもとして考える。ひもの長さが偶数で大きいものから左へ、つぎ、奇数のもので、大きいものをつなげていく。ひもとひもの間には.をつけなければならない。.が余…
問題 問題概要 a[i]の倍数の頂点番号からb[i]の頂点番号へ有向グラフを張ることができる。SからTに行く最小コストを求める問題。 解法 愚直に、(a[i]の倍数) -> (b[i]の倍数) の有向グラフをすべてはり、bfsで、到達した点までの距離を更新しながら、最短距…
問題 問題概要 564が与えられた場合は答えは、509となる。これは、564=509+50+5となるからである。このように、下１桁を消していって、その合計が、与えられた数と同じになる数字があるかを調べる。同じものがなければ、-1を返す。 解法 二分探索でやった。…
問題 問題概要 n日間で山を登ります。1日で最大登れる高度はA、1日で最大下れる高度はBである。このときに、N日間で山を登り、元の場所に戻ってくる場合で、最大高度はいくつまでいけるか。 解法 全探索ぽいことしました。nの制約は小さく、Aの制約も小さい…
問題 問題概要 与えられた文字列から、部分文字列として、共通のもの(T)を取り出し、S = T + TのSの長さを求める問題。 解法 まず、与えられた文字列を2つに分ける。その後、その2つの文字列の最長共通部分列(LCS)の長さを求めて、2倍したものが答えの候補と…
問題 問題概要 スペース入りのアルファベットンの文が与えられるので、単語ごとの頭文字をとり、それをつなげたものを表示する問題。 解法 まず、name[0]は必ず、頭文字になる。そのあとは、スペースのあとの文字が必ず頭文字になるので、スペースのあとの文…
問題 問題概要 ３つの辺の長さが与えられる。それを使って、最も辺の長さの合計が長い三角形の辺の長さを求めさい。 解法 三角形の成立条件を使えばいい。成立条件を満たすのなら３辺の和そのものが答えとなり、条件を満たさないなら、最大辺を短くして、ギ…
