目次
-
1.はじめに
- 自己紹介
- 今回のテーマ
- 2.サイトで何問かアルゴリズム系の実装の練習をしました
- 3.感想
1.はじめに
自己紹介
こんにちは。sgswといいます。
今大学生で、好きな言語はPythonです。
公式サイトはこちら(外部サイトに飛びます)
今回のテーマ
今日は、最近のところこちらのサイトに書かれている内容を理解し、内容をPythonに翻訳したりして、アルゴリズムとデータ構造の勉強＆復習をしていましたが、読むだけで飽きてきたので実際に問題を解きたくなったのでサイトで練習をしました。
その時にやったもののうち、特に面白かった問題のコードの記録を残しておきたいと思います。
2.サイトで何問かアルゴリズム系の実装の練習をしました
問題は、CodeForcesというサイトから適当に見つけてきました。
(1) D. Firecrackers
C++だと実装が簡単ですね。Pythonにはmultisetに対応するものがないので、どうやってやるのか?
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for (int (i) = 0; (i) < n; (i)++)
using P = pair<int,int>;
void slv(){
int n,m,rob,cop;
cin>>n>>m>>rob>>cop;
multiset<int> S;
rep(i,m){int x;cin>>x;S.insert(x);}
int ans = 0;
if (rob > cop){
int new_rob = n + 1 - rob;
int new_cop = n + 1 - cop;
rob = new_rob;
cop = new_cop;
}
assert(1 <=rob && rob < cop && cop <= n);
int chance = min(cop - rob - 1,m);
vector<int> V(chance);
rep(i,chance){V[i] = cop - 1 - i;}
reverse(V.begin(),V.end());
for (auto e: V){
if (S.lower_bound(e) == S.begin()){continue;}
auto itr = S.lower_bound(e);
itr--;
ans++;
S.erase(itr);
}
cout << ans << endl;
return;
}
signed main(){
int t;cin>>t;
while(t--)slv();
return 0;
}
(2)F. Full Turn
平行で同じ向きでないベクトルペアの個数を数える、ということは分かりましたが、そこからの実装が迷走して苦労しました。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for (int (i) = 0; (i) < n; (i)++)
using P = pair<int,int>;
int gcd(int a, int b){return (b == 0) ? a : gcd(b, a % b);}
template<class T>
class dict{
public:
map<T,int> memo;
void add(T obj){
if (memo.find(obj) == memo.end()){memo[obj]++;}
else{memo[obj]++;}
return;
}
int get(T obj){
if (memo.find(obj) == memo.end()){return 0;}
return memo[obj];
}
map<T,int> & data(){
return memo;
}
};
void slv(){
int n;cin>>n;
dict<P> V;
rep(i,n)
{int x,y,u,v;
cin>>x>>y>>u>>v;
int a,b;
a = u - x,b = v - y;
int g = gcd(a,b);
if (g < 0){g *= -1;}
a /= g;b /= g;
P key = P{a,b};
V.add(key);
}
int res = 0;
for (auto [elem,v] :V.data()){
auto [a,b] = elem;
P opp_elem = P{-a,-b};
res += V.get(elem)*V.get(opp_elem);
}
res /= 2;
cout << res << endl;
return;
}
signed main(){
int t;cin>>t;
while(t--) {slv();}
return 0;
}
(3) D.program
インデックスの操作で混乱して大変でした。
INF = 1 << 64
def slv():
n, m = map(int, input().split())
s = input()
querys = [tuple(map(int, input().split())) for i in range(m)]
dpr = [(0, 0) for i in range(n + 1)]
dpl = [(0, 0) for i in range(n + 1)]
dps = [0 for i in range(n + 1)]
for i in range(n - 1, -1, -1):
M, m = dpr[i + 1]
if s[i] == "+":
dpr[i] = (M + 1, min(m + 1, 0))
else:
dpr[i] = (max(M - 1, 0), m - 1)
tot = 0
for i in range(1, n + 1):
if s[i - 1] == "+":
tot += 1
else:
tot -= 1
tmpM, tmpm = max(dpl[i - 1][0], tot), min(dpl[i - 1][1], tot)
dpl[i] = (tmpM, tmpm)
dps[i] = tot
for l, r in querys:
lM, lm = dpl[l - 1]
rM, rm = dpr[r]
m = min(lm, dps[l - 1] + rm)
M = max(lM, dps[l - 1] + rM)
# print((lM,lm),dps[l - 1],(rM,rm))
# print(l, r, (m, M))
if m <= 0 <= M:
print(M - m + 1)
else:
print(M - m + 2)
return
def main():
T = int(input())
for _ in range(T):
slv()
return
if __name__ == "__main__":
main()
(4) C.Fence Repainting
面白かったです！でも少し実装がめんどくさかった。
from collections import defaultdict
T = int(input())
def array(f):
return list(map(f, input().split()))
def solver():
n, m = map(int, input().split()) # plank = n,painter = m
bef = array(int)
aft = array(int)
painter = array(int)
painter_color = defaultdict(list)
painter_left = [0]*(n + 1)
for i, c in enumerate(painter):
painter_left[c] += 1
#differ_array = []
for i in range(n):
if bef[i] != aft[i]:
if painter_left[aft[i]] == 0:
print("NO")
return
painter_left[aft[i]] -= 1
painter_color[aft[i]].append(i)
#differ_array.append((i,bef[i],aft[i]))
if all(painter[-1] != elem for elem in aft):
print("NO")
return
print("YES")
const_idx = -1
res_array = []
for i in range(1, m + 1):
color = painter[-i]
if i == 1:
for j in range(n):
if bef[j] != aft[j] and aft[j] == color:
const_idx = j
break
if const_idx < 0:
for j in range(n):
if bef[j] == aft[j] and aft[j] == color:
const_idx = j
break
assert const_idx >= 0
res_array.append(const_idx + 1)
if const_idx in painter_color[color]:
painter_color[color].remove(const_idx)
continue
if painter_color[color]:
v = painter_color[color].pop()
res_array.append(v + 1)
continue
else:
res_array.append(const_idx + 1)
print(*res_array[::-1])
return
for _ in range(T):
solver()
(5). Floor and Mod
これは特に面白かったです。
最終的に sum floor(N/i) i = 1...Nを数えることに帰着したのですが、
そのままやるとO(N)で終わらないので、O(N**0.5)に工夫しました。
#import random
def array(f):
return list(map(f, input().split()))
def floor_sum(X, N):
#return X//1 + .... X//N
res = 0
for i in range(X//N, X + 1):
if i * i > X:
for j in range(1, N + 1):
if X//j >= i:
res += X//j
else:
break
break
if i == 0:
continue
n = min(X//i, N) - X//(i + 1)
res += n * i
return res
# def naive_floor_sum(X, N):
# return sum(X//i for i in range(1, N + 1))
# def random_checker(T=100):
# for _ in range(T):
# x, n = random.randint(1, 100000), random.randint(1, 100000)
# a = floor_sum(x, n)
# b = naive_floor_sum(x, n)
# assert a == b
# print("OKOK")
# return
def slv():
x, y = map(int, input().split())
ans = 0
for b in range(1, y + 1):
if x//(b + 1) >= b - 1:
ans += b - 1
else:
ans += floor_sum(x, y + 1) - floor_sum(x, b)
break
print(ans)
return
def main():
T = int(input())
# random_checker()
for _ in range(T):
slv()
main()
3.感想
何となくこれでいけそうと思っても、そこからの実装方針が立たなかったり、アイデアが浮かんでからの実装力のなさを痛感させられました。
こちらのサイトの勉強と合わせて、これからも進めて行きたい感じです。