問題 問題概要 省略 解法 数を大きくするには、桁数を増やせばよい。そのように考えて数を作るためのマッチの本数を見ると、1が２本で作れるので、一番少なくてすむので、基本1をたくさん作ればよいということになる。ただし、nが奇数の場合もあるので、その…
問題 問題概要 省略 解法 奇数列のピラミッドに対して全探索を行う。i列のピラミッドを作るときに、足りないブロックの数と、余ったブロックの数それぞれの列に対してカウントする。答えは、足りないところに余りから追加するためのコストが、tarinaiで、 余…
問題 問題概要 省略 解法 まず、ワーシャルフロイドで、任意の２点間の最短距離を計算しておく。そのあとは、辺が一つ追加されるだけなので、追加される辺が、x-yであれば、任意の２点間の最短距離は、i -> j = i -> x -> y -> j = i -> y -> x -> j のなか…
問題 問題概要 省略 解法 解く時間が小さい順にといていけば、ペナルティーが最小になる。何通りあるかは、同じもののなかで並び替えてもペナルティーが最小であることに違いはないので、同じ数字がx個あれば、x!通り存在することになるので、それらをかけ合…
問題 問題概要 巡回セールスマン問題に辺のコストを加えたもの。 解法 巡回セールスマン問題ですね。bitDPで解きました。ただ今回の問題は、荷物をどれだけ持っているかで、1単位を移動するのにかかる時間が異なるので、それを前計算で、weight[mask] := mas…
問題 問題概要 マスの状態を一致させるために、必要な最小コストを求める問題。 解法 はじめは、貪欲に、左上から見ていき、交換して変えて、一致するところを優先的にやればいけると思い書いたが、WA。原因は単純で、左上から貪欲にやるだけではだめで、ど…
問題 問題概要 硬貨の枚数を最小枚数に変更する。 解法 まず、合計金額を求める。それを1000円、100円、25円、1円の順に優先的に変換していけばいい。 ミス なし。 コード #include <iostream> #include <queue> #include <vector> #include <cstdio> #include <algorithm> using namespace std; typedef </algorithm></cstdio></vector></queue></iostream>…
問題 問題概要 優先順位のつけ方が与えられる。どの順番に選ばえばいいか。 解法 priority_queueで解いた。大学ごとに何人選ばれたかが優先順位をつける要因となるので、はじめの状態でそれぞれの大学が何人ずつ選ばれるかがわからないので、いきなりすべて…
問題 問題概要 隣りあったの数字をたす。足した値が2桁になるときは10の位と1の位の数字をたす。1桁ならそのまま。この操作を続けていき、さいご1桁になった時、どのような数字になるかを求める。 解法 与えられう数字Sの桁は大きいので文字列として受け取る…
問題 問題概要 死亡フラグと生存フラグが与えられる。死亡フラグが2本以上立っていれば、死亡。しかし、生存フラグが立っていれば、死亡フラグによらず生存している。どのような状態か求めよ。 解法 死亡フラグが何本立っているかをd1+d2+d3で求められる。あ…
問題 問題概要 Oは宝を含んでいる場所。?は宝を含んでいるかどうかがわからない場所。?の場所を宝が含んでいるか含んでいないかのすべての場合について、宝が含まれる可能性のある面積を求め、その合計を求める。 解法 今回は単純にbit全探索をすればいい。?…
問題 問題概要 1がA、2がB、、7がGと対応している。そして、8から順にまたそれが続く。この時、何種類のアルファベットを含んでいるか。 解法 周期7で繰り返すので、mod7をとって、その値をsetにいれて重複をなくせばいい。 ミス 特になし。 コード #include <iostream></iostream>…
問題 問題概要 カッコの文字列が与えられる。カッコが対応する形に変更する。ただし変更できる文字の数は、((文字数)/2)+1まで。 解法 動的計画法で解いた。変更できる文字の数に制限があるので、最小の数で対応づけができるものを求めた。dp[i][j] := i番目…
問題 問題概要 数式を計算する。 解法 参考サイト とてもわかりやすい。 構文解析 Howto · GitHub ミス しっかりとした構文解析は初めて。 コード #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cctype> #include <cstdio> using namespace std; typedef long long ll;</cstdio></cctype></algorithm></vector></string></iostream>…
問題 問題概要 カッコの階層が最大どこまで行くか。どこまで深くいくか。 解法 '('の時は+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 := 最後尾に戻る である。先に並んでいたのに、前に横入りされると、不満がたまる。それぞれの人に対…
問題 問題概要 椅子に隣同士に座ることはできない。一つに机に椅子がいくつある椅子が、何個あるかが与えられるので、最大で何人座ることができるかを求める。 解法 2人掛けなら1人、3人掛けなら2人、4人掛けなら2人、5人掛けなら3人が最大で座れる数となる…
問題 問題概要 手持ちのモンスターから、レベルの一番低くくて、その中でも、一番先頭回数が少ないモンスターから使う。モンスターは戦わせるとレベルが上がる。敵は円に並んでいる。どこから始めてもよいが、1回ずつ順番に戦う。このときに、最も先頭回数が…
問題 問題概要 省略 解法 bfsで書いた。やることはシンプルで、色を変えた場所から隣接している同じ色だった部分の色も同時に変わるので、そのようなマスをbfsで探索して色を変えていけばいい。これを実装すると、Ｏ(HWQ)となり、TLEしてしまう。ここをどう…
問題 問題概要 N個の寿司が並んでいる。順番に食べていくが、連続して食べることはできない。寿司にはおいしさがそれぞれ決まっている。食べた寿司のおいしさの合計の最大値を求めよ。またどの寿司を食べたかも求める。経路復元。 解法 動的計画法で解く。dp…
問題 問題概要 SをTにするときの編集距離の最小を求める問題。編集距離のdpの漸化式については以下のサイトが参考になる。 解法 dpで解くことができる。 dp[i][j] := 文字列Sのi番目までで、文字列Tのj番目までを作ることを考えた時の操作回数の最小値として…
問題 問題概要 a,b,cのどれかの倍数になる数字の個数を求める。 解法 包徐原理で解く。高１のどっかでやる3つの場合の公式を使えば解くことができる。 wikipediaの3つの有限集合に対して書かれている公式をそのまま使えばいい。 包除原理 - Wikipedia 集合a,…
問題 問題概要 グラフはi - i+1 と i - i+2 を結ぶ２つ辺が貼られている。 二重連結グラフの状態を保ったまま辺を取り除き、辺のコストを最小にしたときの辺のコストの合計を求める。 解法 biconnected graph(2重連結グラフ)とは、任意の頂点を1つ取り除いて…
問題 問題概要 グラフが与えられる。そのグラフの中に三角形を作る。最小でいくつの辺を加えればできるか。 解法 まず、辺が1つもなければ、必要な最小の辺の数は3となる。次に辺がある場合を考える。u - v の辺がある場合を考える。このとき、u - x(xはvで…
問題 問題概要 円の中心座標が与えられる。円の半径は10cm。いくつの円をかなさならないようにおけるか。 解法 まず、Nが105なので、円の中心が与えられてるたびに、過去に置いた円すべての中心間の距離を計算しておけるかどうかを確かめるとＯ(N*N)となり、…
