問題 問題概要 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>…

問題 問題概要 省略 解法 この問題のポイントは、数字に対して、割り当てられる文字の長さが3文字までであるから、1~9の数字を何文字にするかきめれば、その長さが矛盾しないものか確かめられる。 実装で困った点は、kが決まっていないので、単純にループで…

問題 問題概要 省略 解法 メモ化再帰で解いた。サンプルで与えられている図のように辺を張り、dp[i] := i番目の商品が必要な数 とおき、自分の子で必要なものの数から、i番目に必要な個数を計算する形にした。商品nが必要な個数は1個なので、dp[n - 1] = 1と…

問題 問題概要 省略 解法 それぞれの箱にいれる数を決めると、作業の回数が決まる。求めるものは作業回数の最小値。すこし考えると、仮にそれぞれの箱にx個入れた時が答えとなるとすると、x個以下でそろえようとしたときは、作業回数は増え、またx個以上でそ…

問題 問題概要 省略 解法 与えられた関数は、下に凸の関数となるので、最小値は3分探索で探すことができる。 ミス よくわからんけど、rの大きさが大きすぎて、バグらした、3分探索を練習したい。 コード #include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> </algorithm></vector></set></cstdio></iostream>…

問題 問題概要 トーナメントで勝ち進んでいく確率。 解法 dpで解いた。 dp[i][j] := i回回目の試合にj番目のひとが勝つ確率 として、漸化式にそって、ループで値を埋めていく。漸化式は簡単で、 dp[i + 1][x] += dp[i][x] * dp[i][y] * memo[x][y] のように…

問題 問題概要 省略 解法 dpで解いた。 dp1[i][j] := 太郎君がサイコロをi回振って、合計がjの時の確率 dp2[i][j] := 次郎君がサイコロをi回振って、合計がjの時の確率 とおいて、漸化式でi=1からi=nまでループを回して埋めていった。 漸化式は単純で、いか…

問題 問題概要 省略 解法 bfsで解いた。よくある、2次元座標上での迷路問題などで、ゴールまで行けるかの問題と同じようにやる。ただし、4方向への移動が高さの条件で制限されるので、それを確認すればよい。また、dyとdxを2倍して、2倍の距離の移動も同様に…

問題 問題概要 省略 解法 2進数で表したときに、2倍すると、1桁左に移動するので、末尾に0をつければよい。すなわち、hamをつければいい。 ex1) 101(5) 1010(10) ex2) 111(7) 1110(14) 注意しなければならないのは、n=hamの時0なので、2倍しても0のまま。 ミ…

問題 問題概要 省略 解法 いわれたとおりにシミュレーションを行う問題。高橋君の位置を固定して、その時に青木君が丸を付ける場所を探し、その時高橋君の得点を記録しておく。これを高橋君が選べるすべての場所について調べ、高橋君の得点が最大となるとき…

問題 問題概要 省略 解法 貪欲に選んでいけばいい。なぜなら、飛行時間はxとyで決まっているので、乗れるだけ早い時間にのり、もう一方の空港に行っているほうが得。(損はない) 実装方法だが、今どちらの空港にいるのかが判断できるものと、いまの時刻がわか…

問題 問題概要 省略 解法 時計を1周分を360度と考えて、それぞれの針が何度回ったかを計算する。最後に注意しなければならないことがあり、針の角度の差を取ると、180度を超えることがあるが、それは角度の大きいほうを図ってしまったいるので、小さいほうを…

問題 問題概要 省略 解法 場合分けする。 3つの数字が異なるとき、1つは、kで決まり、残りの２つは、kより小さいものから1つ、kより大きいものから1つ選べばよいので、その時の3つの数字の組み合わせを考える、(k - 1)*(n - k)となり、さらに、引く順番を考…

問題 問題概要 省略 解法 abcdeは重複を許さずに選ばなければならない。あとは、できるすべての作り、それをソートして、3番目答えとなる。a<b<c<d<eのため、1番目と２番目が等しいということはないので、単純にソートして3番目を選ぶだけで十分かな。 ミス 今回のセットはabc27と比べるとレベルが違いすぎる。 コード #include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #d…</algorithm></vector></set></cstdio></b<c<d<eのため、1番目と２番目が等しいということはないので、単純にソートして3番目を選ぶだけで十分かな。>

問題 問題概要 省略 解法 まず、すべての住人の数を求めて、それを島の数で割り切れなければ、-1を出力すればいい。また、住民の合計と、島の数から、1つの島に住んでいなければならない人数もわかる。橋を架けなければならない場所の判定は、橋の左側と、右…

問題 問題概要 省略 解法 ２分探索でとく。関数はだいたい増加しているような関数であるので、解をもつ範囲の左端をL、右端をR、真ん中をM とすると、t=Mの時に、関数の値が100を超えるなら、中間地の定理より(あたりまえ)、左側の部分に解を必ず一つはもつ…

問題 問題概要 省略 解法 上司から直属の部下に対して辺を張り、有向グラフを作成する。それを利用して、dfsを行う。部下がいないとき、つまり、グラフ上で葉の部分に該当する部下の給料は1なので、1を返す。部下が存在するとき、つまり、葉以外の頂点では、…

問題 問題概要 省略 解法 aは昇順に並んでいるので、時系列に沿った形で見ていく。ドアが開き始めた時間をl、閉じる予定の時間をrおき、aiがrより小さいなら、なら、時間がtよりすくないが延長され、rより大きいなら、一度ドアが閉じ、そのあと、時間がtだけ…