問題 問題概要 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>…
問題 問題概要 aとbの数字が与えられる。aをfの数字で変えることができる。この操作を行って、aiとbiが異なる組数の最小値を求めよ。ただし、異なる数が増えてしまうような場合であっても、fはすべて使わないといけない。 解法 貪欲法で解いた。まず、一番最…
問題 問題概要 -と.を含んだ文字列sが与えられる。この文字列を並び替える。-の連続した部分をひもとして考える。ひもの長さが偶数で大きいものから左へ、つぎ、奇数のもので、大きいものをつなげていく。ひもとひもの間には.をつけなければならない。.が余…
問題 問題概要 省略 解法 2次元imos法を使えば楽なんですね。 imos法 いもす法 - いもす研 (imos laboratory) BITとかsegtree使うのかな、て感じだった。 2次元BIT http://hos.ac/slides/20140319_bit.pdf ミス imos!! コード 2次元imos法 #include <iostream> #includ</iostream>…
問題 問題概要 組み合わせの数え上げ 解法 まず、すべてソートしてく。全探索をして、それぞれの家族がどのマットを使うかを決める。それが条件を満たしたものであれば、ほかのものは選ぶ選ばないの選択がある。 dpのほうがわかりやすいな。状態数は2つで、1…
問題 問題概要 LからRの範囲の中の素数が与えら数の数字(0~9)のみを使い(必ず使わないといけない)、R - Lの最大値を求めよ。 解法 素数判定はエラトステネスを利用、区間の最大値を求めるには、1~5000000までの素数でも、10000以上あるので、すべての区間を…
問題 問題概要 盤面上での陸地の繋がりを調べえる問題。ただし、1マス分だけ陸地にすることができる。 解法 10x10の盤面で小さいので、100個あるマスを1つ変えた時に、どうなるかを調べる。全探索するということ。 回りの4方向で陸どおしでつながっている部…
問題 問題概要 省略 解法 union findは辺を削除することができない。問題は、クエリを与えられた順にみると、辺を削除するような形だが、クエリを逆からみれば、辺をつなげていく形になる。このようになると、union findで管理できる。 また今回学んだunion …
問題概要 codingameの中のClash of Codeで書いたもの。2進数を16進数に変換せよて問題だった。c++だとどう書くのが早いのか。0b0110のようなクエリが与えらるので、0x6 と答えるような問題。1度10進数に変換したほうがいいか。 競プロとかで出てもおかしくな…
問題 問題概要 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の制約も小さい…
問題 問題概要 省略 解法 bitDPで解いた。 dp[mask][lim] := 集合maskのモンスターと戦った時に最大体力が lim * 100 の時に、残りの体力の最大値 として、ループで回していった。 limは100から100とばしに1600までしか使わないので、簡単な座圧的な感じで、…
問題 問題概要 省略 解法 しゃくとり法をやるだけなんだけど、すぐにうまくできない。 ミス 尺取り法バグらしまくってうまくできない。 コード 尺取り法 #include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #de</algorithm></vector></set></cstdio></iostream>…
