srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

arc

ARC 045 B - ドキドキデート大作戦高橋君

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

ARC 045 A - スペース高橋君

arc

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

ARC 044 B - 最短路問題

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

ARC 044 A - 素数判定

arc

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

ARC 046 B - 石取り大作戦

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

ARC 033 C - データ構造

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

ARC 033 B - メタ構文変数

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

ARC 032 B - 道路工事

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

ARC 037 C - 億マス計算

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

ARC 037 B - バウムテスト

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

ARC 036 C - 偶然ジェネレータ

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

ARC 036 B - 山のデータ

arc

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

ARC 035 C - アットコーダー王国の交通事情

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

ARC 035 B - アットコーダー王国のコンテスト事情

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

ARC 031 B - 埋め立て

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

ARC 011 C - 123引き算

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

ARC 061 D - すぬけ君の塗り絵 / Snuke's Coloring

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

ARC 061 C - たくさんの数式 / Many Formulas

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

ARC 005 C - 器物損壊!高橋君

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

ARC 005 B - P-CASカードと高橋君

arc

問題 問題概要 省略。 解法 領域からでたら、ベクトル(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>…

ARC 003 C - 暗闇帰り道

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

ARC 002 B - 割り切れる日付

arc

問題 問題概要 省略。 解法 モジュール使うと楽だね。 ミス なし。 コード 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/%…

ARC 056 B - 駐車場

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

ARC 056 A - みんなでワイワイみかん

arc

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

ARC 022 C - ロミオとジュリエット

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

ARC 025 B - チョコレート

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

ARC 060 E - 高橋君とホテル / Tak and Hotels

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

ARC 060 C - 高橋君とカード / Tak and Cards

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

ARC 059 D - アンバランス / Unbalanced

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

ARC 059 C - いっしょ / Be Together

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

ARC057 A - 2兆円

arc

問題 問題概要 省略 解法 ループを回すだけ。一見、制約が大きいので回すだけではダメなように見えるが、金額は最低でも2倍に増えて行くので(k=1を除いて)、計算量がlogになり、時間内に可能。ただし、 k=1の場合は例外として処理する必要がある。 ミス 特に…