ferinの競プロ帳

競プロについてのメモ

ABC

ABC015-D問題

abc015.contest.atcoder.jpナップザック問題でk個のみつかえるという制約を加えたような問題です。ナップザック問題で持つ状態に加えて今までに使用したスクリーンショットの枚数を状態として持つことで解けます。まずメモ化再帰で実装しました。次に動的計…

ABC008-D問題

abc008.contest.atcoder.jp 蟻本で似た問題(P121, Bribe the Prisoners)を見たことがあったので同じように考えて実装しました。機械を動かしたあとその機械で取った金塊で分断された場所は互いに関係しない独立した場所です。なので、ある機械を動かしたと…

ABC037-D問題

abc037.contest.atcoder.jp解説通りf(y, x) を再帰的に求めて全てのf(y, x)を足す感じで実装しました。定番のメモ化再帰という印象の問題でした。

ABC038-D問題

abc038.contest.atcoder.jp解説読んでもわからなかったBainary Indexed Tree(BIT)ってなんだよ!ってのとソートの方法を指定する方法についてのメモ。 BITについては以下のスライドが分かりやすかったです。和ではなくその区間の最大値を保存することである…

ABC040D

abc040.contest.atcoder.jpUnionFindをある程度理解したあとだったので解法が何をやっているのかは割と早く理解できましたが、実装に手間取ってしまいました… 年をキーとして2つの値をもつ組を降順にソートする必要があります。最終的にvectorvector > を使…

ABC041D

abc041.contest.atcoder.jp解説を読んでも満点解法がなかなかわからず苦労したのでそのメモです。 まずトポロジカルソートは有向辺が全て1方向へ向くようにソートをソートをすることです。入力例1についてトポロジカルソートを行ってみると以下の2通りになり…

ABC049D

abc049.contest.atcoder.jp自力では手も足も出なかったのでeditorialと解説放送を参考に実装しました。 youtu.be https://youtu.be/jvAX9Z7beLgグラフの連結を管理するために、グループ分けを管理するためのデータ構造であるUnion-Find木を使います。 道路で…

ABC030を解いてみた

abc030.contest.atcoder.jp A問題 if文で比較しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { double a, b, c, d; cin >> a >> b >> c >> d; i</bits/stdc++.h>…

ABC029を解いてみた

abc029.contest.atcoder.jp A問題 文字列の最後にsを連結しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { string s; cin >> s; cout << s + 's</bits/stdc++.h>…

ABC028を解いてみた

abc028.contest.atcoder.jp A問題 条件に合わせて分岐して出力しました。Perfectのスペル間違えてWA出したので気をつけたい。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.141592653</bits/stdc++.h>…

ABC027を解いてみた

abc027.contest.atcoder.jp A問題 長方形は向かい合っている辺の長さが等しいです。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { int a, b, c; cin >></bits/stdc++.h>…

ABC025を解いてみた

abc025.contest.atcoder.jp A問題 入力をソートして(n-1)/5文字目、(n-1)%5文字目が答えの文字列になります。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { vector<char> str; string ans = "", temp; int n; c</char></bits/stdc++.h>…

ABC026を解いてみた

abc026.contest.atcoder.jp A問題 x=1からx=a-1まで全探索で実装しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int a, ret = 0, maxret = -1; cin >> a; for(int x=1; x</bits/stdc++.h>

ABC024を解いてみた

abc024.contest.atcoder.jp A問題 条件に沿って実装しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int a, b, c, k, s, t, ans = 0; cin >> a >> b >> c >> k; cin >> s >> t; if(s+t >= k) ans</bits/stdc++.h>…

ABC049を解いてみた

abc049.contest.atcoder.jp A問題 入力がa, i, u, e, oならvowel、そうでなければconsonantを出力しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { string str; cin >> str; if(str == "a" || str</bits/stdc++.h>…

ABC023を解いてみた

abc023.contest.atcoder.jp A問題 string型で入力を受けとり1桁ずつに区分けし加算していきました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int x, ans = 0; string str; cin >> str; for(int i=0;</bits/stdc++.h>…

ABC040を解いてみた

abc040.contest.atcoder.jp A問題 n-1とx-nのうち小さい方を出力しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int n = 0, x = 0; cin >> n >> x; if(x-1 >= n-x) cout << n-x << endl; else c</bits/stdc++.h>…

ABC022を解いてみた

abc022.contest.atcoder.jp A問題 N日目のとき、適正体重かどうかを判定しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int n=0, s=0, t=0, w=0, a[1000], ans=0; cin >> n >> s >> t; cin >> w</bits/stdc++.h>…

ABC041を解いてみた

A問題 入力をString型で受けとりS[i-1]を出力しました。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { string S; int i; cin >> S; cin >> i; cout << S[i-1] << endl; return 0; } B問題 直方体の体積の</bits/stdc++.h>…

ABC042を解いてみた

abc042.contest.atcoder.jp A問題 入力をソートして5, 5, 7になっていればYES, なっていなければNOを出力しました。 a = [int(i) for i in input().split()] a.sort() if a[0] == 5 and a[1] == 5 and a[2] == 7: print("YES") else: print("NO") B問題 ソー…

ABC048に参加してみた

abc048.contest.atcoder.jp A問題 スライスを使って先頭の文字だけを取得して連結しました。 s = [i for i in input().split()] ans = s[0][0:1] + s[1][0:1] + s[2][0:1] print(ans) B問題 ans = b/x - a/x で求まります。aがxの倍数の時だけans++とすれば…

ABC043を解いてみた

abc043.contest.atcoder.jp A問題 1からNまでの和をn(n+1)/2で求めます。 n = int(input()) print(int(n*(n+1)/2)) B問題 sの長さは10以下と非常に短いため、条件に従って答えとなる文字列を操作していけばよさそうです。この方針で実装しました。 s = list(…

ABC044を解いてみた

abc044.contest.atcoder.jp A問題 k k >= n のとき ans = n*x と場合分けできるのでそれに従って実装するだけです。 n = int(input()) k = int(input()) x = int(input()) y = int(input()) if k < n: ans = k*x+(n-k)*y else: ans = n*x print(ans) B問題 …

ABC045を解いてみた

abc045.contest.atcoder.jp A問題 台形の面積の公式を実装するだけです。 a = int(input()) b = int(input()) h = int(input()) print(int((a+b)*h/2)) B問題 Sa, Sb, Sc import sys stra = input() strb = input() strc = input() flag = 1 while True: if …

ABC046を解いてみた

abc046.contest.atcoder.jp A問題 内包表現を使って入力を受けとり、set関数で重複を削除した配列の長さをlen()で数えました。 print(len(list(set([int(i) for i in input().split()])))) B問題 一番左のボールに塗る色がk種類あり、その右のボールの色はk-…

ABC021を解いてみた

A問題 nが8より大きいか、4より大きいか…と貪欲的に判定していきました。 A問題にしては難しいなーと思ったら数字の重複可能なことを見逃してました… n = int(input()) flag = [0 for _ in range(4)] count = 0 if n >= 8: flag[3] = 1 n -= 8 count += 1 if…

ABC015を解いてみた

A問題 len(a)でaの長さがわかるのでaとbの長さを比較して長い方を出力しました。 B問題 n=100と小さいので全探索で解きました。a[i]が0でないときだけバグ、バグのあるソフトの総数を表す変数に加算していき割って切り上げたものを出力しました。 C問題 n, k …

ABC014を解いてみた

abc014.contest.atcoder.jp A問題 (a%b == 0) のとき0を出力し、そうでないとき(b-(a%b))を出力しました。A問題でif文使うの珍しい気がしました。 B問題 x = bin(x)[2:][::-1] として配列で扱いました。あとはforループで1文字ずつ確かめていって(x[i] == 1)…

ABC013を解いてみた

abc013.contest.atcoder.jp A問題 入力の文字コードとAの文字コードの差をとって出力しました。 B問題 足す方と引く方に10回ずつループして目標の値に到達するまでにかかる回数が短い方を出力しました。 C問題 わからなかったので解説の通りに実装。ynのとき…

ABC012を解いてみた

A問題 a, b を受け取って b, aを出力しました。 B問題 int(n/3600) を時間、その分をnから引いてint(n/60)を分、その分をnから引いた分を秒を表す変数に代入します。そして、zfill()で0パディングして":"と連結して出力しました。 C問題 制約と入出力例から…