問題 問題概要 N人の人がM個の教室を掃除する. 一人が掃除する連続区間の教室が与えられる. ひとつの教室につき一人以上が掃除をしていればいい. どの区間を掃除する人はさぼることができるか. さぼる人は 同時に1人として考える. 解法 まずimos法を利用して…

問題 問題概要 与えられた文字列に応じて出力する文字列を変更する. 解法 string s; while(cin>>s){ //処理 } 上記のような方法で, スペースまでの文字列を受け取り, 終了したらwhileを抜けれる. ミス なし. コード #include <bits/stdc++.h> using namespace std; typedef </bits/stdc++.h>…

問題 問題概要 A1をstartとした時の頂点までの最短経路の情報が与えられる. その木の高さで作ることのできるグラフは何通りあるか, mod1e9+7で答えろ. 解法 まず, A１からの最短経路の情報が与えられているはずなので, A1以外で最短経路が0であればそのよう…

問題 問題概要 Nが素数ならPrime Nが合成数で, 1の位が2,5で割り切れず, 各桁の和が3で割り切れないとき, Prime それ以外なら Not Prime 解法 まず, 普通に素数判定をし, 素数ならPrime. 次に, 1のくらいが2, 5で割り切れず, 各桁の和が3で割り切れないけれ…

問題 問題概要 プレイヤーが交互に1個以上の石をとる. 最後に石をとったプレイヤーの勝利. 先手はA個まで, 後手はB個まで石をとることができる. 最適に行動したときどちらが勝利するか. 解法 まずN<=Aの時は先手がN個とって勝ち. 次に, 二人のプレイヤーが合…

問題 問題概要 タイプ 1 ： S に数 X を追加する。 タイプ 2 ： S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する。 この２つを高速に行うことができるデータ構造を使えばよい。 解法 今回の問題は、Xがあまり大きくない。よって、バ…

問題 問題概要 省略。 解法 SA と SB の両方に現れる要素の個数は、一方の集合の要素がもう一方にあるかを単純に調べるだけでできる。 SA と SB の少なくともどちらか一方には現れる要素の個数は、setを使い、重複がないようにいくつあるかを調べれば簡単に…

問題 問題概要 省略。 解法 union find を使って、連結成分がいくつできているかを数得ればよい。連結成分を１つにするのに必要な辺の数は答えになるので、答えは(連結成分の数-1)となる。 ミス なし。 コード #include <bits/stdc++.h> using namespace std; typedef long </bits/stdc++.h>…

問題 問題概要 100マス計算のようなマスが与えられる。その中で積の値が、小さいほうから数えて、K番目に位置する値を求めよ。 解法 editorialがわかりやすい。 AtCoder Regular Contest 037 解説 from AtCoder Inc. www.slideshare.net 答えをmidとすると、…

問題 問題概要 連結成分の中で、閉路がなく、木である連結成分の個数を求める。 解法 閉路を検出する問題。dfsで探索して、すでに探索した頂点をmemoで記録しておいて、同じところに2度来たら、その連結成分は閉路を持つので木ではないのでカウントしない。 …

問題 問題概要 省略 解法 ランダムウォークの表のようなものを考えて、+y方向に、(1-0の数)、-y方向に(0-1の数)として表を考える。そして、dp配列に、dp[i][j][k] := i番目まで見て、(1-0)の最大値がjで、(0-1)の最小値がkの時の場合の数 として、更新してい…

問題 問題概要 省略 解法 山の中央と決めて、その左右に条件を満たしながら、伸ばせるだけ伸ばした時がその時の山の最大となる。これを山の中央に対してすべて行うと TLEしてしまう。そこで、 if(h[mid - 1] < h[mid] && h[mid] > h[mid + 1]) という条件を…

問題 問題概要 省略 解法 まず、ワーシャルフロイドで、任意の２点間の最短距離を計算しておく。そのあとは、辺が一つ追加されるだけなので、追加される辺が、x-yであれば、任意の２点間の最短距離は、i -> j = i -> x -> y -> j = i -> y -> x -> j のなか…

問題 問題概要 省略 解法 解く時間が小さい順にといていけば、ペナルティーが最小になる。何通りあるかは、同じもののなかで並び替えてもペナルティーが最小であることに違いはないので、同じ数字がx個あれば、x!通り存在することになるので、それらをかけ合…

問題 問題概要 盤面上での陸地の繋がりを調べえる問題。ただし、1マス分だけ陸地にすることができる。 解法 10x10の盤面で小さいので、100個あるマスを1つ変えた時に、どうなるかを調べる。全探索するということ。 回りの4方向で陸どおしでつながっている部…

問題 問題概要 省略 解法 dpで解いた。dp[i][j] := i回数字を引いて、jになるなら、true、とおいてループで回して埋めていった。 dp[i][j+k]=trueならdp[i][j]=trueとなるので(ただし、jはngでない)、このことから漸化式らしきものが立てられる。 ミス nがい…

問題 問題概要 HxWの２次元マスの中で考えられる3x3のマスを考え、それぞれの3x3のマスの中に黒のマスがいくつあるかを調べる。 解法 HxWのマスを持つことはできない。また制約を見ると、ほとんどの部分が白のマスであり、黒の部分は少数である。よって、与…

問題 問題概要 省略。 解法 bit全探索。sの長さがnのとき、n-1個の場所に+を入れることができるので、+を入れる場所を2n-1通り全部試せばいい。実装方法は、bitを使い、1であればその部分に+を入れて、0であればその部分に+を入れない。例えば、s=125の場合…

問題 問題概要 省略。 解法 よくあるのは、used[y][x]で(x, y)へ行くことができたことをメモしてbfsをやったりしていたが、今回は、何回壁を壊して、(x, y)へ到達できたかの情報も必要なので、used[y][x][k]として、k=0なら壁を壊さず、(x, y)へ到達できてお…

問題 問題概要 省略。 解法 領域からでたら、ベクトル(dx, dy)の方向を変更して、進むような形で、実装した。 ミス こういう問題どうとこうか迷う。 コード #include <iostream> #include <string> #include <queue> #include <cmath> #include <cstdio> using namespace std; #define rep(i,n) for(i</cstdio></cmath></queue></string></iostream>…

問題 問題概要 省略。 解法 sからgまでの経路が存在するとき、答えを小さくすれば、条件を満たし、答えを大きくしていくと、条件を満たさなくなる。そのため、答えを2分探索していけばよいことになる。また、ある地点まで、最短でいったときが、そのますの明…

問題 問題概要 省略。 解法 モジュール使うと楽だね。 ミス なし。 コード import datetime y, m, d = map(int, raw_input().split('/')) t = datetime.date(y, m, d) while t.year % (t.month * t.day) != 0: t += datetime.timedelta(1) print"%04d/%02d/%…

問題 問題概要 s->iへ到達できるか。ただし、通れる頂点に制約あり。 解法 思いついたのは、逆からunion-find。頂点iに行けるかを見る場合、i以上の頂点を使い、sからiへたどり着けるかを見れば良いので、i=n-1からi=0の順に調べ、そのつど、追加できる辺を…

問題 問題概要 省略 解法 1つだけのものだけで、kこ買うパターン セットだけで、kこ以上買うパターン 1つとセットでkこ買うパターン の3つを試して、それらの最小値を出せばいい。 ミス なし コード #include <iostream> using namespace std; typedef long long ll; i</iostream>…

問題 問題概要 木の直径を求める。 解法 木の直径を求めるアルゴリズム。 適当な頂点から最も遠い頂点xを選び、さらに、xから最も遠い頂点yを選ぶ。xとyの距離が木の直径となる。 ミス 直径は初めて。 コード #include <iostream> #include <algorithm> #include <vector> #include <queue> #incl</queue></vector></algorithm></iostream>…

問題 問題概要 ２次元累積和。 解法 このサイトを参考にした。 paiza.hatenablog.com 白か黒をマイナスの数字として扱うことで、２次元累積和を用いて計算することができる。やり方は、まず、横方向の累積和を取り、次は、それを縦方向に累積和をとる。この…

問題 問題概要 省略 解法 参考サイト imulan.hatenablog.jp 上のサイトを見たらだいぶわかった。 ダブリングと２分探索を使うらしい。蟻本の最後の方にもかいてあった。 int now = a; for (int i = 19; i >= 0; --i){ if(nx[i][now] < b){ now = nx[i][now];…

問題 問題概要 省略 解法 dpでとく。dp[i][j][k] := x[i]まで見て、選んだ数がj個で、合計値がkの時の場合の数 として、漸化式を立てて、ループを回して計算し、dp[n - 1][j][j * a]の和を取れば回答となる。 ミス 特になし。 コード #include <iostream> #include <cstdio> us</cstdio></iostream>…

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

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