問題 問題概要 探索問題。２分探索で値の前後を求める。 解法 まず、storeに店の位置を入れる。この時、少しsample1を使って、考察してみる。本店の位置を0にしてしまうと、宅配先1からの距離は4-0=4で正確に求まるが、宅配先2からの距離は6-0=6で正確なもの…

問題 問題概要 探索問題。単純に全探索してしまうと、TLE。 解法 まず、単純に考える。全てのパターンを考えれば良いので、以下のコードのように単純に4つの矢が刺さるマスを全探索すればいい。 int main(void){ while(1){ int n, m; cin >> n >> m; if(n ==…

問題 問題概要 場合分けが必要な６方向の幅優先探索。イルミネーションが必要なところが色塗りの感覚でわかる。 解法 まず、イルミネーションが必要なのは、外側のみであり、内側の部分は必要ない。よって、その外側の部分(周りが完全に囲まれている中の部分…

問題 問題概要 ２次元にあるビット(0, 1)を任意の縦列、横列を選び任意の回数反転させることができる。最終的に最も0が多くなる時の0の数を求めよ。 解法 この問題には「R の上限 10 は C の上限 10000 に比べて小さいことに注意せよ」と書かれていて、解法…

問題 問題概要 強連結成分の分解を利用する問題。強連結成分を１つの頂点に置き換えて、DAGにして、トポロジカルソートをする。 解法 N個のステージを頂点と考える。(先に指定しておくと良いステージ) -> (ステージ)の向きに有向辺をはっていき、有向グラフ…

問題 問題概要 強連結成分分解する問題。 解法 強連結成分を分解するアルゴリズムとして、Kosarajuというものがある。今回はそれを使って、実装した。アルゴリズム自体は下のサイトを見てもらえれば、分かりやすい。 mathtrain.jp ミス アルゴリズム自体の理…

問題 問題概要 省略 解法 アンバランスとなる文字のどんなものでも良いから、一つ出力すればいい。だから、余計な文字を含まない(最短でアンバランスな文字)ものを考えればいい。そのように考えると aa aa(:任意の文字) の2パターンがある。この２パターン以…

問題 問題概要 省略 解法 はじめは、中央値や平均値などを求めて、その値の前後の値を調べようかと思った。しかし、aの値は-100 <= a <= 100であるので、求める解もこの範囲にあることがわかる。数が少ないので、201個全部調べれば答えが出る。 ミス なし コ…

問題 問題概要 省略 解法 条件通りにの文字列を作る。 0の時は、文字列の末尾に0を付け加え、1の時は文字列の末尾に1を付け加え、Bの時は、文字列の末尾を取ればよい。 ミス ClangだとACだけど、GCCだとREでよく分からない。 [追記] @mmxsrup 空の文字列に対…

問題 問題概要 桁dpの問題 類題の私のメモ mmxsrup.hatenablog.com 解法 dp[i][j][k][l][m]という配列を作り埋めていく。 整数pを考えた時に、i番目の桁まで考えて、j=1の時は考えている数がp未満であることが決定していて、j=0の時はp以下である。 k=1の時…

問題 問題概要 桁dpの問題 解法 dp[i][j][k][l]という配列を作りdpで埋めていく感じ。 整数pを考えた時に、i番目の桁まで考えて、j=1の時は考えている数がp未満であることが決定していて、j=0の時はp以下である。 k=1の時はすでにi番目までに数字3を含んでい…

問題 問題概要 漸化式で表されている数列の第n項を求める問題。 解法 3項間漸化式を解いて、一般項を求めた。一般項は a(k) = 4*(3/4)k (k >= 0) となるので、これを利用した。 ミス 高校数学忘れるね。 コード #include <iostream> #include <cstdio> #include <cmath> using namespa</cmath></cstdio></iostream>…

問題 問題概要 門松行列の判定を複数回行う問題。 解法 7つの数字が与えられる。それを並び替えることによって、左から順に3つずつの数字を見て、それが門松列になっているかを調べる。それを左から右へ一つずつずらして、すべて調べ、すべての場合において…

問題 問題概要 数字を並び替えた時に、条件を満たし、もっとも得点を獲得できる時の得点を求める。 解法 数字の数の最大値が14である。数字をすべて並び替える解法だと、計算量が(n!)になるので、TLE。そのためには計算量を(2n)にしなければならない。そこで…

問題 問題概要 数列の隣合う数字の間隔が素数で表されるとき、すべてでいくつの数列が構成できるか求める問題。 解法 入力が5 12の時を考える。 素数2の時 0 2 4 6 8 1 3 5 7 9 2 4 5 8 10 3 5 7 9 11 4 6 8 10 12 上のような4つの数列が存在する。 このとき…

問題 問題概要 隣合う二点間の距離がすべて等しいかを見分ける。 解法 x座標がソートされていないのでまずはソートする。そのあと、順番に隣り合う区間の距離が等しいかを見ていけばいい。私は、x0とx1の距離を出しておいて、その値と他の隣り合う2点間の距…

問題 問題概要 時計の針が何時を指しているかを求める問題。 解法 modを取って計算していく。時計の針の{"XII", "I","II","III","IIII","V","VI","VII","VIII","IX","X","XI"}を先頭から順にmod12を利用して、0,1,2.......,11とする。これをさらに、T時間後…