ABC023を解いてみた
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; i<str.size(); i++) {
ans += (int(str[i])-48); //文字コード
}
cout << ans << endl;
return 0;
}
B問題
手順の回数は (n-1)/2 回となります。問題文の処理をこの回数分行い、できた文字列と与えられた文字列を比較しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
int main(void)
{
int n;
string s, comp = "b";
cin >> n;
cin >> s;
for(int i=1; i<=(n-1)/2; i++) {
if (i % 3 == 1) comp = "a" + comp + "c";
else if(i % 3 == 2) comp = "c" + comp + "a";
else comp = "b" + comp + "b";
}
if(s == comp) cout << (n-1)/2 << endl;
else cout << -1 << endl;
return 0;
}
C問題
部分点解法しか思い浮かばなかったので解説を見て実装しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define MAX_N 100000
int main(void)
{
int r, c, k;
cin >> r >> c >> k;
int n;
cin >> n;
vector<int> y(n), x(n), countrow(r, 0), countcol(c, 0);
for(int i=0; i<n; i++) {
cin >> y[i] >> x[i];
y[i]--; x[i]--;
//列、行ごとの飴の数
//countrow[i] = j i行目にj個の飴
countrow[y[i]]++; countcol[x[i]]++;
}
//特定の飴の個数の行、列の数
//numrow[i] = j 飴の数がi個の行がj個
vector<ll> numrow(n+1, 0), numcol(n+1, 0);
for(int i=0; i<r; i++) numrow[countrow[i]]++;
for(int i=0; i<c; i++) numcol[countcol[i]]++;
ll sum = 0;
for(int i=0; i<=k; i++) sum += numrow[i]*numcol[k-i];
for(int i=0; i<n; i++) {
//飴がある場所を起点としていて合計がk, k+1のとき
if(countrow[y[i]] + countcol[x[i]] == k) sum--;
else if(countrow[y[i]] + countcol[x[i]] == k+1) sum++;
}
cout << sum << endl;
return 0;
}
D問題
思い浮かばなかったので解説を見て実装しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
int main(void)
{
int n;
cin >> n;
vector<ll> h(n), s(n);
for(int i=0; i<n; i++) cin >> h[i] >> s[i];
ll hmax = *max_element(h.begin(), h.end()), smax = *max_element(s.begin(), s.end());
//一番大きいxとしてありえるのはmax(h)+max(s)*n
ll left=0, right=hmax+smax*n, mid=(left+right)/2;
bool flag = true;
vector<ll> t(n);
//二分探索
while( right-left > 1)
{
flag = true; mid=(left+right)/2;
// midのとき条件を満たすかを確かめる
for(int i=0; i<n; i++) {
if(mid < h[i]) t[i] = -1;
else t[i] = (mid-h[i])/s[i];
}
sort(t.begin(), t.end());
for(int i=0; i<n; i++) {
//貪欲的に考えていって成り立たないt[i]が存在するなら条件は満たさない
if(t[i] < i) {
flag = false;
break;
}
}
//条件を満たすなら
if(flag) {right = mid;}
//条件を満たさないなら
else {left = mid;}
}
cout << right << endl;
return 0;
}
ABC040を解いてみた
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 cout << x-1 << endl;
return 0;
}
B問題
1からsqrt(n)まで四角形の1辺を探索し、もう1辺を求めコストを算出しました。そのうち最小となるコストを出力しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
int main(void)
{
int n, j, cost, mincost = 300000;
cin >> n;
for(int i = 1; i <= sqrt(n); i++)
{
j = n/i;
cost = abs(i-j) + n - i*j;
mincost = min(mincost, cost);
}
cout << mincost << endl;
return 0;
}
C問題
dp[i] = (i番目まで移動するのにかかる最小コスト) という変数で、DPを行って求めました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define MAX_N 100000
int main(void)
{
int n, a[MAX_N], dp[MAX_N];
cin >> n;
for(int i=0; i<n; ++i)
cin >> a[i];
dp[0] = 0;
dp[1] = abs(a[1]-a[0]);
for(int i=2; i<n; ++i)
{
dp[i] = min(dp[i-1] + abs(a[i]-a[i-1]), dp[i-2] + abs(a[i]-a[i-2]));
}
cout << dp[n-1] << endl;
return 0;
}
D問題
Union-Find木を知らなかったので蟻本で勉強して出直してきます…
ABC022を解いてみた
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;
for(int i=1; i<n; ++i) cin >> a[i];
if(s <= w && w <= t) ++ans;
for(int i=1; i<n; ++i)
{
w += a[i];
if(s <= w && w <= t) ++ans;
}
cout << ans << endl;
return 0;
}
B問題
たどった花の種類別に数を数えて2個以上になった種類は、その数-1が受粉するという方針で実装しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define MAX_N 100000
int main(void)
{
int n=0, a=0, lis[MAX_N]={}, ans=0;
cin >> n;
for(int i=0; i<n; ++i)
{
cin >> a;
lis[a-1] += 1;
}
for(int i=0; i<MAX_N; ++i)
{
//if(i < 30) cout << "lis: " << lis[i] << endl;
if(lis[i] >= 2) ans += (lis[i]-1);
}
cout << ans << endl;
return 0;
}
C問題
もっとも短い経路の閉路を探すアルゴリズムが思いつかなかったので解説見て実装しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 999999999
#define MAX_N 300
int main(void)
{
//lis1が1に隣接する頂点へのコスト
int n, m, u, v, l, d[MAX_N][MAX_N]={}, lis1[MAX_N]={}, ret = 0, minret = INF;
//lisが1に隣接する頂点番号のリスト
vector<int> lis;
bool flag = true;
// dの初期化
fill( d[0], d[MAX_N], INF);
for(int i=1; i<MAX_N; ++i) d[i][i] = 0;
//入力
cin >> n >> m;
for(int i=0; i<m; ++i)
{
cin >> u >> v >> l;
if(u != 1 && v != 1) {d[u-1][v-1] = l; d[v-1][u-1] = l;}
else if(u == 1) {lis1[v-1] = l; lis.push_back(v);}
else {lis1[u-1] = l; lis.push_back(u);}
}
//ワーシャルフロイド
// d[i][j] で頂点iから頂点jへの最短距離
for(int k=0; k<n; ++k) {
for(int i=0; i<n; ++i) {
for(int j=0; j<n; ++j) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
// lis の中から2つを選択
for(int i=0; i < lis.size()-1; ++i) {
for(int j=i+1; j < lis.size(); ++j) {
ret = lis1[lis[i]-1] + lis1[lis[j]-1] + d[lis[i]-1][lis[j]-1];
//cout << "lis[i]:" << lis[i]-1 << " lis[j]:" << lis[j]-1 << " lis1[lis[i]]" << lis1[lis[i]-1] << " lis1[lis[j]]" << lis1[lis[j]-1] << " d" << d[lis[i]-1][lis[j]-1] << " ret:" << ret << endl;
minret = min(minret, ret);
}
}
//たどり着けるパターンがなかったら-1を出力
if(minret == INF) minret = -1;
cout << minret << endl;
return 0;
}
D問題
回転行列を使ってやるのかなとか考えてても実装方法が思い浮かばなかったので、解説見て実装しました。N点の重心と最遠点の比率による方法をつかいました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define MAX_N 100000
int main(void)
{
int n, ax[MAX_N], ay[MAX_N], bx[MAX_N], by[MAX_N];
double agx=0.0, agy=0.0, bgx=0.0, bgy=0.0, adist=0.0, bdist=0.0, maxadist=0.0, maxbdist=0.0;
cin >> n;
for(int i=0; i<n; i++) cin >> ax[i] >> ay[i];
for(int i=0; i<n; i++) cin >> bx[i] >> by[i];
for(int i=0; i<n; i++) {
agx += ax[i]; agy += ay[i];
bgx += bx[i]; bgy += by[i];
}
agx /= n; agy /= n;
bgx /= n; bgy /= n;
//cout << agx << " " << agy << " " << bgx << " " << bgy << endl;
for(int i=0; i<n; i++) {
adist = pow(ax[i] - agx, 2) + pow(ay[i] - agy, 2);
maxadist = max(maxadist, adist);
bdist = pow(bx[i] - bgx, 2) + pow(by[i] - bgy, 2);
maxbdist = max(maxbdist, bdist);
}
//cout << "maxa:" << maxadist << " maxb:" << maxbdist << endl;
cout << setprecision(12) << sqrt(maxbdist)/sqrt(maxadist) << endl;
return 0;
}
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問題
直方体の体積の計算自体はA*B*Cで求められる。変数はlong long型で確保しておきオーバーフローしないように掛けるたびに余剰の計算を行いました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
int main(void)
{
ll a, b, c, ans;
scanf("%lld %lld %lld", &a, &b, &c);
ans = (((a*b)%MOD)*c)%MOD;
printf("%lld\n", ans);
return 0;
}
C問題
vector< pair< int, int > > (身長と出席番号のペア）を作成し身長をもとにソートを実行、そしてその順番で出席番号を出力しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
int main(void)
{
int n = 0, a = 0;
scanf("%d", &n);
vector< pair<int, int> > height(n);
for(int i = 0; i < n; i++)
{
scanf("%d", &a);
height[i] = make_pair(a, i);
}
sort(height.begin(), height.end(), greater<pair<int,int> >());
for(int i = 0; i < n; i++)
printf("%d\n", height[i].second+1);
return 0;
}
D問題
満点解法のトポロジカルソートを用いる方法の計算が理解できなかったのでとりあえず全探索の部分点解法について。next_permutationを使って全パターンについて探索し、各パターンについてxがyより先に出ればそのパターンは条件を満たしていると考えられます。満点解法については理解できたら書きます…
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
int main(void)
{
int n = 0, m = 0, x[120], y[120], lis[16][16];
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++)
{
scanf("%d %d", &x[i], &y[i]);
}
vector<int> data;
for(int i = 1; i <= n; i++) {data.push_back(i);}
ll ans = 0;
bool flag = true;
do
{
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
//xのあとにyが出ればtrueに yのあとにxが出ればfalseになる
if(data[j] == x[i]) flag = false;
else if(data[j] == y[i]) flag = true;
}
if(!flag) break;
}
if(flag) ans++;
}while(next_permutation(data.begin(), data.end()));
printf("%d\n", ans);
return 0;
}
ABC042を解いてみた
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問題
ソート関数で辞書順に並べて出力しました。
n, l = map(int, input().split())
s = [[i for i in input()] for j in range(n)]
s.sort()
for i in range(n):
s[i] = "".join(s[i])
s = "".join(s)
print(s)
C問題
桁を増やす必要があるかどうか、Nをすでに超えているかどうかなどの場合分けをおこない1桁ずつ決めていきました。1～10Nまで全探索すればよいなんてやり方に気がつかないなんて…という感じです。
n, k = map(int, input().split())
d = [int(i) for i in input().split()]
ablenum = [int(i) for i in range(10)]
lis_n = str(n)
lis_n = list(lis_n)
# 使用可能な数一覧
for i in d:
ablenum.remove(i)
flag_bigdigit = -1
# max(ablenum)より大きい桁があるかどうか
for i in range(len(lis_n)):
_i = len(lis_n) - i - 1
if(int(lis_n[_i]) > max(ablenum)):
flag_bigdigit = _i
break
# max(ablenum)より大きい桁があれば
if(flag_bigdigit != -1):
flag_increaseDights = 1
# 桁を増やす必要があるかどうか確認
for i in range(flag_bigdigit-1, 0):
# nの桁より大きい数字がablenumに存在していれば桁を増やす必要はない
if(int(lis_n[i]) < max(ablenum)):
flag_increaseDights = 0
break
else:
flag_increaseDights = 0
ans = ""
# 桁を増やす必要があるならば
if(flag_increaseDights == 1):
for i in range(len(lis_n)+1):
# 一桁目は0以外の最も小さな数
if(i == 0):
mnum = min(ablenum)
if(mnum == 0):
mnum = ablenum[1]
ans += str(mnum)
# 2桁目以降は最も小さい数
else:
mnum = min(ablenum)
ans += str(mnum)
# 桁を増やす必要がなければ、各桁の数字以上の最も小さい数を使う
else:
flag_over = 0
for i in range(len(lis_n)):
if(flag_over == 0):
mnum = min(ablenum)
# その桁以上の数になるまで大きくする
j = 0
while mnum < int(lis_n[i]):
j += 1
mnum = ablenum[j]
# n以上となることが確定すれば
if(mnum > int(lis_n[i])):
flag_over = 1
ans += str(mnum)
# n以上となることが確定していれば使える中で最も小さい数を使う
else:
mnum = min(ablenum)
ans += str(mnum)
print(ans)
D問題
最短経路数はコンビネーションを使って計算できるので、nCr(mod m)を高速で求める方法を使って実装しました。逆元を予め求めておくことでコンビネーションはO(1)で計算できます。フェルマーの小定理から逆元はmod mのときx^m-2で求められます。二分累乗法でx^nはO(logn)で計算できるので逆元の列はO(nlogn)で計算可能です。
Pythonでh=w=10^5のケースを試してみたところ、明らかに2秒以内に計算できていなかったのでいろいろ試してみたんですが実行時間を減らすことができずC++で書き直しました。オーバーフローを気にしなくてもよかったりPythonは好きですが、競プロで使う分にはC++のほうがよさそうだと思えてきました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
ll fact[200000], ifact[200000], dp[100000];
int h, w, a, b;
//二分累乗法
ll binpow(ll x, ll e)
{
ll a = 1;
ll p = x;
while(e > 0)
{
if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
else {a = (a*p) % MOD; e--;}
}
return a;
}
int main(void)
{
fact[0] = 1;
ifact[0] = 1;
scanf("%d %d %d %d", &h, &w, &a, &b);
//逆元の列を計算
for(int i = 1; i < h+w; i++)
{
fact[i] = fact[i-1] * i % MOD;
ifact[i] = binpow(fact[i], MOD-2);
}
// (b-1, 0) から (b-1, h-a-1) までの経路数を計算
for(int i = 0; i < h-a; i++)
dp[i] = ((fact[b-1+i]*ifact[b-1]%MOD)*ifact[i]%MOD);
// (b-1, 0) から (b-1, h-a-1) から右下までの経路数を計算
ll ans = 0LL;
for(int i = 0; i < h-a; i++)
ans = (ans + ((dp[i]*fact[h+w-b-i-2]%MOD)*ifact[h-i-1]%MOD)*ifact[w-b-1]%MOD) % MOD;
printf("%lld\n", ans);
return 0;
}
ABC048に参加してみた
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++とすれば大丈夫（なはず）です。
指数表記をint()で整数に直そうとしたんですが、下のように値が変化してしまい悩んでました。
>>> 1000000000000000000/3 3.333333333333333e+17 >>> int(1000000000000000000/3) 333333333333333312
C問題
配列aを左から2つずつ区切っていったときにその2つのうち左側を優先的に減らす理由はないため、右側を優先的に減らしていく貪欲法で実装しました。
n, x = map(int, input().split())
a = [int(i) for i in input().split()]
count = 0
for i in range(n):
s = sum(a[i:i+2])
if s > x:
if (s - x > a[i+1]):
a[i+1] = 0
a[i] -= (s - x - a[i+1])
else:
a[i+1] -= sum(a[i:i+2]) - x
count += s - x
print(count)
D問題
適当に入力例を紙に書いて試していたところ、ab???baのように真ん中に挟まれているところがあったとしても関係なさそうだと思いつき、両端の文字と文字列の長さが偶数か奇数かで判断すればよさそうだと思い浮かび、ちゃんと証明できていたわけではありませんがとりあえず提出したらACでした。
s = input()
if s[0:1] == s[len(s)-1:len(s)]:
if len(s) % 2 == 1:
print("Second")
else:
print("First")
else:
if len(s) % 2 == 1:
print("First")
else:
print("Second")
雑感
Bで悩んでいた時間がすごいもったいなかったなと思いました。苦手なDPが出なかったこともあって4完できてよかったです。
ABC043を解いてみた
A問題
1からNまでの和をn(n+1)/2で求めます。
n = int(input()) print(int(n*(n+1)/2))
B問題
sの長さは10以下と非常に短いため、条件に従って答えとなる文字列を操作していけばよさそうです。この方針で実装しました。
s = list(input())
ans = ""
for i in s:
# 0を連結
if i == "0":
ans = ans + "0"
# 1を連結
elif i == "1":
ans = ans + "1"
# 一番右側の文字を削除
elif i == "B":
ans = ans[:len(ans)-1]
print(ans)
C問題
NとAの範囲が狭く全探索で問題なさそうです。置き換える後の数字はAの制約である-100から100の範囲で必ず収まります。置き換える後の数字を全て、全てのNに対して試せばよさそうです。O(AN)≒O(20000)程度で収まるため実行時間も問題なさそうです。
最初、range(-100, 100)としていて範囲に100が入っておらず一回WAを出してしまったので気をつけたいです。
n = int(input())
a = [int(i) for i in input().split()]
mincost = 10000000
for i in range(-100, 101):
cost = 0
for j in range(n):
cost += (a[j]-i) ** 2
mincost = min(cost, mincost)
print(mincost)
D問題
最初、しゃくとり法を使う方針で考えて提出しましたがWAを出してしまい考え直すと、長さが3の部分文字列がアンバランスでないときにその部分文字列を含む長さが4の部分文字列がアンバランスであることはありえません。そこで文字列を3文字ずつに区切っていきアンバランスであるかを確かめていけばよさそうです。この方針で実装したところWA… コーナーケースを考えると入力sが"aa","ff"といった同じ文字2文字の場合があり、この入力sはアンバランスな部分文字列となりますが、3文字以上の文字列に対してのみ確認を行っていたため判定できていませんでした。修正を行って提出してAC!
import sys
s = input()
# 同じ文字2文字はアンバランス
if len(s) == 2 and s[0:1] == s[1:2]:
print(1, 2)
sys.exit()
for i in range(len(s)-2):
#3文字で区切る
temp = s[i:i+3]
#アンバランスな部分文字列が存在すれば
if temp[0:1] == temp[1:2] or temp[1:2] == temp[2:3] or temp[2:3] == temp[0:1]:
print(i+1, i+3)
sys.exit()
print(-1, -1)
雑感
点数が低めのやさしめな問題だったのもあって自力で4完とれました。今日この後あるABCも頑張りたいです。
