コンテスト
A問題
感想
円周率の小数第N位までを出力する問題だけど、小数第100位までの値が与えられている。
なので、与えられている文字列の先頭から$N+2$個を出力するといい。
コンテスト中提出コード
int main() {
ll n = in_ll();
string s = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
print(s.substr(0,n+2));
return 0;
}
B問題
感想
Xに賭けた人たちの中で、賭けた目の個数が最も少ない人たちの番号を昇順で出力する。
この問題ではNが小さいので、結構雑なコードでもTLEになることはない。
以下の手順で解いた。
- Xに賭けた人を探して、その人が賭けた目の個数とその人の番号iをvectorに記録する。(後にソートするのでこの順番で記録)
- vectorのsizeが0の場合、0を出力して終了する。
- vectorのsizeが0でない場合、vector昇順にソートする。
- ソート後の一番先頭が「Xにかけた人たちの中で、最も少ない賭けた目の個数」なので、この個数と同じ個数かけた人たちを探し、番号iを記録する。
- 番号を記録したvectorをソートする。
公式解説にRangesライブラリを使用した実装例が載っている。
https://atcoder.jp/contests/abc314/editorial/6977
Rustを触ってた時に使っていたiterに近い気がする。
間違えにくいコードが書けそう。
コンテスト中提出コード
int main() {
ll n = in_ll();
vector<set<ll>> a(n);
rep(i,n){
ll c = in_ll();
set<ll> t;
rep(i,c){
ll a = in_ll();
t.insert(a);
}
a[i] = t;
}
ll x = in_ll();
vvll ans;
rep(i,n) {
if(a[i].find(x) != a[i].end()){
vll t;
t.pb(a[i].size());
t.pb(i+1);
ans.pb(t);
}
}
if(ans.size() == 0 ) {
print(0);
return 0;
}
sort(all(ans));
ll p = ans[0][0];
vll aans;
fore(i,ans){
if(i[0] == p ) aans.pb(i[1]);
}
sort(all(aans));
print(aans.size());
fore(i,aans){
print(i);
}
return 0;
}
C問題
感想
同じ色の文字を1つ右にシフトさせる問題。
同じ色ごとにdequeを作って、$C_i$を見ながら$S$の何文字目かを格納する。
入力例だと、この時点で以下のようになっている。
$deque[0] : [0,3,6]$
$deque[1] : [1,4,5,7]$
$deque[2] : [2]$
同じ色の文字がSの何文字目に出てくるかがわかった。
前から順に格納しているので、Sの文字列に出てくる順になっている。
なので、dequeに格納している値を右にシフトすると、$S$の文字列に出てくる順も右にシフトできる。
操作としては、一番後ろの数値を前に持ってくる。
これはdequeのpop,appendleftでO(1)で行うことが可能。
入力例だとこの時点で以下のようになっている。
$deque[0] : [6,0,3]$
$deque[1] : [7,1,4,5]$
$deque[2] : [2]$
このdequeを使って文字列を出力する。
最初にdequeに格納した時と同様に$C_i$をみながら出力する。
$C_i$を順に見る操作のみ行なっているので、$O(N)$になる。
コンテスト中提出コード
import collections
N,M = list(map(int, input().split()))
S = input()
C = list(map(int, input().split()))
t = [collections.deque() for _ in range(M)]
for i,ci in enumerate(C):
t[ci-1].append(i)
for i in range(M):
tmp = t[i-1].pop()
t[i-1].appendleft(tmp)
for i,ci in enumerate(C):
tmp = t[ci-1].popleft()
print(S[tmp],end='')
print()
D問題
感想
$t_i$が2または3の時は全てが大文字か小文字になる。
つまり最終的に出力する文字列で、大文字が小文字か分からないものは、$t_i=1$の時に変更した文字列だけになる。
よって、最後に$t_i$が2または3になった時から追加された文字の$x_i$をsetに保存しておく。
また最後の出力時に大文字か小文字かを決めるため、最後の$t_i$が2か3かも覚えておく。
出力時には、$x_i$文字目がsetの中にあれば、$S[x_i]$をそのまま出力する。
ない場合は、最後の$t_i$が2の時は小文字、3の時は大文字を出力する。
クエリの処理で$O(Q)$、出力時に$O(N)$の計算が必要なので、合わせて$O(Q+N)$になる。
コンテスト中提出コード
N = int(input())
S = list(input().strip())
Q = int(input())
s = set()
sw = None
for _ in range(Q):
t,x,c = list(input().split())
x = int(x)-1
if t =='1':
s.add(x)
S[x] = c
elif t=='2':
s.clear()
sw = 's'
else:
s.clear()
sw = 'l'
for i,si in enumerate(S):
if i in s:
print(si,end='')
else:
if sw is None:
print(si,end='')
elif sw == 's':
print(si.lower(),end='')
else:
print(si.upper(),end='')
E問題
感想
考えたけど全然分からなかったので、後日再検討。
よく見ると、E問題とF問題は同じ配点だったので、Fを考えてみればよかった。
コメント