これで難易度5はおしまい B - たのしいカードゲーム (Card Game is Fun) Bは前から何枚取り除くかを考えればよいので，取り除くBの枚数と，そのときのAとの共通部分を調べればいい． #include <bits/stdc++.h> using namespace std; int main() { int a, b; cin >> a >> b; </bits/stdc++.h>…

A - JJOOII (JJOOII) 連続するJ，O，I を数える．JJOOOIIIのようなケースに気をつける． s = input() cnt_j, cnt_o, cnt_i = 0, 0, 0 ans = [0] for i in range(len(s)): if cnt_i != 0 and s[i] != 'I': cnt_j, cnt_o, cnt_i = 0, 0, 0 if s[i] == 'J': if …

A - 惑星探査 (Planetary Exploration) PythonだとTLE，PyPyだとMLEで死ぬので，C++で解く．許して．二次元累積和 #include <bits/stdc++.h> using namespace std; int main() { int m, n, k; cin >> m >> n >> k; vector<string> geo(m); vector<vector<int>> query(k, vector<int>(4)); for (int i </int></vector<int></string></bits/stdc++.h>…

B - 共通部分文字列 文字列sを前から1つずつ除いたものと文字列tを比べる，文字列tを前から1つずつ除いたものと文字列sを比べれば最大の共通部分が分かります． #include <bits/stdc++.h> using namespace std; int main() { string s1, s2; cin >> s1 >> s2; int l1, l2, c</bits/stdc++.h>…

D - パスタ (Pasta) bit全探索は厳しいので，DPを使ってとく．指定されたソースを使う日の処理，最後に10000で割ることに注意して実装する． n, k = map(int, input().split()) ab = [list(map(int, input().split())) for _ in range(k)] dp = [[0 for _ in…

D - 1年生 (A First Grader) bit全探索だと満点は取れないので，別の方法を考える．番目までに+か-を入れてきたときの和でDPすればうまくいく． 今の数字を，番目に追加する文字をとすると，DP遷移式は， - 0のとき，dp[ + 1][ - ] += dp[ ][ ] + 20のとき，…

IOIOI 文字列を逐一数えるのは面倒なので，"I"と"O"が交互の並び条件を満す長さの列を調べる． "I"と"O"が交互に並んでいるかはflagのT or Fで判定(一つ前が"I"ならT，"O"ならF)． n = int(input()) m = int(input()) s = input() cnt = 0 flag = False ans …

D - 薄氷渡り 一つの経路を調べた後に氷を経路を調べる前の状態に戻す必要があるので，再帰関数で実装します． m = int(input()) n = int(input()) ice = [[0] * (m + 2)] for _ in range(n): tmp = list(map(int, input().split())) ice.append([0] + tmp +…

A - twiblr 条件式とBを比較する． a, b = map(int, input().split()) m = 2 * a + 100 if m > b: print(m - b) else: print(0) B - Almost GCD の範囲が小さいので，2以上以下の自然数を全探索する． n = int(input()) a = list(map(int, input().split()))…

自分用に記録 与えられた式(2-17)より 滑車 : ← (ア) A : ← (イ) B : ← (ウ) 糸の長さが一定なので， ← (エ) が成り立つ． よって，上の4式から A を消去すると，． (イ)より，，同様に． 問題文よりなので < ，つまり < ． Fの最小値を聞いているので，で考…

contest - コンテスト (Contest) 考えたこと 与えられたlogを読んで，うまく処理する n, m, t, x, y = map(int, input().split()) p = [int(input()) for _ in range(m)] logs_time = [] logs_player = [] logs_problem = [] logs_state = [] for i in range…

D - カード並べ 考えたこと itertoolsで順列作って，数える from itertools import permutations n = int(input()) k = int(input()) cards = [input() for _ in range(n)] cnt_set = set([]) per = list(permutations(cards, k)) for i in range(len(per)):…

E - チーズ (Cheese) 考えたこと ねずみの最初の体力は 1 であり，チーズを 1 個食べるごとに体力が 1 増える．ただし，ねずみは自分の体力よりも硬いチーズを 食べることはできない とあるので，チーズは1からNまでを順番に食べていくことになります．二点…

C - 最高のピザ (Best Pizza) 考えたこと 問題の頭を読んだときは「お，DPかな」と思ったけど，トッピングのカロリーでsortかけて大きい順に取るだけでした． n = int(input()) a, b = map(int, input().split()) c = int(input()) d = [int(input()) for _ …

poster - JOIポスター (JOI Poster) 考えたこと 再帰関数で殴る!!!!．初めて再帰関数を書いたので雑な部分は許して． n, k = map(int, input().split()) def solve(n, k): if k <= 2 ** (n - 1): return 'J' * (2 ** (n - 1)) + 'O' * (2 ** (n - 1)) elif n…

A - 旅人 考えたこと 累積和するだけなのに，難易度5なのはで割るのを忘れるからだと思う←忘れた人 n, m = map(int, input().split()) city = [int(input()) for _ in range(n - 1)] dis = [int(input()) for _ in range(m)] mod = 10**5 csum = [0] for i i…

1 - 電飾 (illumination) 考えたこと 交互列ごとに区切ると，番目の交互列に機械を使うと左右の交互列(だと片方)と必ず接続される．このことから，入力を交互列ごとに区切って，交互列のどれに機械を使えばよいかを判断すればよい．2つ以下の交互列にしか区…

D - 暑い日々 (Hot days) 非常に眠いので，支離滅裂なことを書いています．いつもだろ 考えたこと 日目の選択に日目以外の情報は必要ない．なので，DPする．DP[i][j]は日目に個目の服を選んだときの値を保持している． d, n = map(int, input().split()) t =…

D - シルクロード (Silk Road) 考えたこと 愚直に求めようとすると，それぞれの町で2通りあるので計算量が以上になって間に合わなさそうなので，DPを使って解く． 普通にDPするだけ 町の数日程のDPテーブルを作る n, m = map(int, input().split()) d = [int…

A - 鉄道旅行 (Railroad Trip) 考えたこと 鉄道はとの区間しか移動できないから，それぞれの鉄道に何回乗るかをカウントする． カウントしたらをそれぞれの鉄道で計算するだけだが，鉄道に何回乗るかをカウントするのがネックになる． 愚直に区間内の配列の…

A - ストーブ (Stove) 考えたこと それぞれのを計算して，大きい順からマッチを使った方がストーブが燃料を節約できます．最初の訪問者が来たときは，必ずマッチを消費することに注意します． n, k = map(int, input().split()) visitors = [int(input()) fo…

A - 勇者ビ太郎 (Bitaro the Brave) 考えたこと 前から愚直に累積和をすると，PythonはTLE，PyPyだとMLEになります． そこで後ろから，調べることにします．Oは後ろから調べると行ごとに値を保持すればいいので，大きいlistを使う必要がありません．Iは列の…

B - いちご (Strawberry) 考えたこと とりあえず右端まで行くのが良さそうなので、右端から開始すると考えます。右端から地点0に向って進んでいきます。途中で、青いイチゴがあれば赤くなるまでその場で待機します。 n = int(input()) at = [list(map(int, i…

C - 桁和 (Digit Sum) 考えたこと N以下の全ての自然数を試そうとすると、きつそうなので別の方法を考えます。 考え方を逆にして、Nから1までの整数を調べてみることにします。を操作してNにできるなら、操作してiにできるような整数もNになります。(j→i→N) …

A - 碁石ならべ 考えたこと 石の状態をlistで管理します。配列に(石の色,連続する個数)のtupleを保存して操作します。問題文と同じく白は0、黒は1で保存します。 例:([(0, 2), (1, 2), (0, 3)])これは、0011000を表します まずは、iが偶数のときを考えます。…

F - 船旅 考えたこと 最短経路を求める問題なので、クエリに従って辺を追加して、dijkstraする。無向グラフなので、両方向に辺を追加する。 from heapq import heappush, heappop n, k = map(int,input().split()) info = [list(map(int,input().split())) f…

D - 星座探し 考えたこと 全探索するだけ。実行時間も10secもあるので雑な全探索でも耐えます。 disという配列に探したい星座の星間の距離を入れて、見えている全ての星に対してそれぞれ調べます。 m = int(input()) targets = [list(map(int,input().split(…

fiber - 光ファイバー (Fiber) 考えたこと グラフを連結して最終的に連結してるグループの数を考える問題。グラフについて色々調べてみると、UnionFindというのがあるらしいので使う。 PythonでのUnionFindから、いらない部分を削いで書きました。 class Uni…

building - ビルの飾り付け (Building) 考えたこと 前から貪欲に取っていけば大丈夫だと思っていたけど、それだとダメだったのでDPします。 ので初期化したdpテーブルを考えます。 [1:]]を

mall - ショッピングモール (Mall) 考えたこと ひとつずつコストの和を取っていると間に合わないので、うまく計算量を減らす必要があります。そこで、累積和を使います。私も初めて使いましたが、二次元累積和というものらしい。 m, n = map(int,input().spl…