問題 問題概要 手持ちのモンスターから、レベルの一番低くくて、その中でも、一番先頭回数が少ないモンスターから使う。モンスターは戦わせるとレベルが上がる。敵は円に並んでいる。どこから始めてもよいが、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)となり、…

問題 問題概要 1辺の長さ与えられる。その辺を1辺とする、3辺が整数となる正三角形をを作れるなら、ほかの2辺の値をもとめよ。 解法 なんか数学的にあるんだろうなーと思ってググったら、ピタゴラス数の一般組があるみたい。 nが奇数のときと偶数のときで異…

問題 問題概要 小麦屋さん以外の頂点でパン屋を開こうとする場合に、もっとも小麦屋さんから近くでパン屋を開ける頂点までの距離をもとめよ。開けないなら-1。 解法 ダイクストラで解いた。スタートをすべての小麦屋さんにして、それらの頂点からほかの頂点…

問題 問題概要 文字列sの中に文字列cがいくつ含まれているかを求める問題。 解法 ローリングハッシュを使いました。ほぼ理解していないので、応用はきかないので要練習。文字列を比較するとき、1文字ずつ見比べいると、文字列の長さがmだとそこで、Ｏ(m)なっ…

問題 問題概要 数列をswapしていく。k回swapするが、k-1回文のswapの処理は与えられるが、どこか一か所のswapの処理がわからないようになっている。一番初めの数列の状態と、最後の数列の状態が与えられるので、途中一か所わからないswapの処理がどのような…

問題 問題概要 0.(190桁)のような少数が与えらえる。これをn倍した値を求める。 解法 小数点以下が多くある状態で扱ってるとまずいので、全体を整数で扱うことにした。Dを整数としてあつかい、それに与えられたnをかける。あとは、これをDを整数にするために…

問題 問題概要 与えられた数字が3:4なのか4:3なのかを判別する問題。 解法 最大公約数で割って、考えた。 ミス 4:3か3:4しかないから、大小だけみれば十分なのか。 コード #include <iostream> #include <algorithm> #include <vector> #include <cstdio> using namespace std; typedef long long </cstdio></vector></algorithm></iostream>…

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

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

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

問題 問題概要 有向グラフが与えられる。1からnまで距離T以下で行く中で、辿る頂点の数を最大にする経路を求める。 解法 dpの解法は、dp[i][j] := i個の名所を回って、j番目の名所にいるときの、移動時間の最小値 として更新していけば解くことができた。今…

問題 問題概要 パスワードがいくつか与えれる。正解のpwも与えらる。パスワードを長さが短いものから順に試していく。このようにパスワードを試していったときに、最短なんか秒で答えのパスワードを入力することになるか、また、最大の場合も求める。ただし…

問題 問題概要 連続する黒のマスの数。 解法 Bが始まった位置をl、Bが終わった位置をrを記録しながら、やる。 ミス サンプルから推測 コード #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; #def</cmath></cstdio></queue></vector></algorithm></iostream>…