ABC 247 参加記
94分6完(3ペナ)でした。575位、パフォーマンスは1757です。
A Move Right
問題
0, 1からなる4文字の文字列$S$が渡されます。1つ右にシフトしてください。
提出コード
int main(){
string S; cin >> S;
string T = "0";
rep(i, 3) T.pb(S[i]);
cout << T << '\n';
}
ACコード
int main(){
bitset<4> S; cin >> S;
S >>= 1;
cout << S << endl;
}
bitset
で入力を受け取るととても簡潔に書けますね、知りませんでした。
B Unique Nicknames
問題
$N$人の人がいて、人$i$の姓は$s_i$、 名は$t_i$です。それぞれにあだ名をつけます。人$i$あだ名は、
$s_i$か$t_i$のいずれかである
自分以外の人の姓/名と一致しない
を満たす必要があります。全員にあだ名をつけることはできますか?
- $2 \leq N \leq 100$、$N$は整数
- $s_i, t_i$は英小文字からなる1文字以上10文字以下の文字列
考察
適当に書いてペナを食らいました。$s_i = t_i$の時にいやなきもちになるので、気を付けて書きます。
提出コード
int main(){
ll N; cin >> N;
vs S(N), T(N);
rep(i, N){
cin >> S[i] >> T[i];
}
rep(i, N){
//人iにあだ名をつけれるか?
bool pass = false;
{
//姓をあだ名にした場合
bool ok = true;
string nic = S[i];
rep(j, N) if(i != j){
if(S[j] == nic) ok = false;
if(T[j] == nic) ok = false;
}
if(ok){
pass = true;
}
}
{
//名をあだ名にした場合
bool ok = true;
string nic = T[i];
rep(j, N) if(i != j){
if(S[j] == nic) ok = false;
if(T[j] == nic) ok = false;
}
if(ok){
pass = true;
}
}
if(!pass){
YesNo(false); exit(0);
}
}
YesNo(true);
}
C 1 2 1 3 1 2 1
問題
列$S_n$を次のように定義します。
$S_1$は1つの1からなる長さ1の列
$S_n(n \geq 2)$は$S_{n-1}, n, S_{n-1}$を順につなげた列
$N$が与えられるので、$S_N$を出力してください。
- $N \leq 16$
考察
最初問題文を読んだ時には「再帰してください」と書いてあったのに、コンテスト終了後に再度読んだら「順にやってください」と書いてありました。再帰をするより順にやった方がコード記述量が少なくなります。
提出コード
int main(){
ll N; cin >> N;
map<int, vector<int>> memo;
auto dfs = [&](auto&& self, ll x) -> vector<int> {
if(memo.find(x) != memo.end()) return memo[x];
if(x == 1){
return {1};
}
auto B = self(self, x - 1);
vector<int> ret = B;
ret.pb(x);
for(auto b: B) ret.pb(b);
return memo[x] = ret;
};
auto ans = dfs(dfs, N);
for(int i = 0; i < ans.size(); i++){
cout << ans[i] << (i != ans.size() - 1 ? ' ' : '\n');
}
}
ACコード
int main(){
ll N; cin >> N;
vi ans = {};
rrep(i, N){
vi nxt;
for(auto a: ans) nxt.pb(a);
nxt.pb(i);
for(auto a: ans) nxt.pb(a);
swap(ans, nxt);
}
for(int i = 0; i < ans.size(); i++){
cout << ans[i] << (i != ans.size() - 1 ? ' ' : '\n');
}
}
D Cylinder
問題
空の筒があります。クエリが$Q$個くるのでさばいてください。
1 x c
: 数$x$が書かれたボールを右側から$c$個入れる2 c
: 筒の左側からボールを$c$個取り出し、取り出したボールに書かれている数の合計を出力- $1 \leq Q \leq 2 \times 10^5$
- $0 \leq x \leq 10^9$
- $1 \leq c \leq 10^9$
考察
そのままやります。ボールを$c$個実際に入れることはできないので、圧縮します。
提出コード
int main(){
ll Q; cin >> Q;
deque<pll> que;
rep(q, Q){
int t; cin >> t;
if(t == 1){
ll x, c; cin >> x >> c;
que.pb({x, c});
}else{
ll c; cin >> c;
ll ret = 0;
while(c != 0){
auto [hx, hc] = que.front();
ll po = min(c, hc); //取り出した数
ret += hx * po;
que.front().se -= po;
c -= po;
if(que.front().se == 0){ //一番左にいるボールが0個になったとき
que.pop_front();
}
}
cout << ret << '\n';
}
}
}
E Max Min
問題
長さ$N$の数列$A$、$X, Y$があります。次の条件をすべて満たす整数の組$(L, R)$の個数を求めてください。
- $1 \leq L \leq R \leq N$
- $A_L, A_{L+1}, \cdots, A_{R}$の最大値は$X$であり最小値は$Y$である。
- $1 \leq N \leq 2 \times 10 ^ 5$
- $1 \leq A_i \leq 2 \times 10^5$
- $1 \leq Y \leq X \leq 2 \times 10 ^ 5$
- 入力される値はすべて整数
考察
順に数列を見ていきます。見ていく中で$X, Y$が現れる最近のインデックスと範囲外($X$より大きいか$Y$より小さいか)が現れる最近のインデックスを覚えておきます。$X, Y$が現れる最近のインデックスを$xi$, $yi$、範囲外が現れる最近のインデックスを$oi$とします。$i$番目が右端になるときの条件を満たす区間を数えていきます。
-
$A_i = X$の場合
$xi$を$i$に更新します。
答えに$yi - oi$を足せばよいです。右端を$i$とすると左端の最小は$oi$に、最大は$yi$となり、その間はどこを左端にしてもよいからです。
-
$A_i = Y$の場合
$yi$を$i$に更新します。
答えに$xi - oi$を足せばよいです。
-
$Y \leq A_i \leq X$の場合
答えに$\min(xi, yi) - oi$を足せばよいです。右端を$i$とすると左端の最小は$oi$に、最大は$\min(xi, yi)$となり、その間はどこを左端にしてもよいからです。
-
それ以外の場合
$oi, xi, yi$を更新します。$oi$を$i$に、$x_i, y_i$はnullとなります。
$xi, yi$がnullの時に注意してください。提出コードではx
,y
という変数を用意し、nullかどうかを見ています。
提出コード
int main(){
ll N, X, Y; cin >> N >> X >> Y;
vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
ll ans = 0;
ll x = 0, y = 0; // 0 -> null
ll xi, yi;
ll idx = 0;
ll oi = -1;
for(auto a: A){
if(a > X || Y > a){
x = 0; y = 0;
oi = idx;
}
if(a == X){
xi = idx;
x++;
}
if(a == Y){
yi = idx;
y++;
}
if(a == X){
if(y != 0) ans += yi - oi;
}elif(a == Y){
if(x != 0) ans += xi - oi;
}elif(!(a > X || Y > a)){
if(x > 0 && y > 0) ans += min(xi, yi) - oi;
}
idx++;
}
cout << ans << '\n';
}
…ans
に加算するところの条件分岐、$A_i$が$X$以下$Y$以上の時は$\min(xi, yi) - oi$を加算、でよくないですか?($A_i$が$X, Y$だった場合、$xi, yi$が今のインデックスに更新されるため) ということで書き直しました。
ACコード
int main(){
ll N, X, Y; cin >> N >> X >> Y;
vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
ll ans = 0;
ll xi = INF, yi = INF; //INF -> null
ll idx = 0;
ll oi = -1;
for(auto a: A){
if(a > X || Y > a){
xi = INF;
yi = INF;
oi = idx;
}
if(a == X){
xi = idx;
}
if(a == Y){
yi = idx;
}
if(X >= a && a >= Y){
if(xi != INF && yi != INF) ans += min(xi, yi) - oi;
}
idx++;
}
cout << ans << '\n';
}
F Cards
問題
$1, \cdots, N$の番号がついた$N$枚のカードがあり、カード$i$の表には$P_i$が、裏には$Q_i$が書かれています。ここで、$P, Q$は$1, \cdots, N$の並び替えです。$N$枚のカードから何枚かを選ぶ方法のうち、次の条件を満たすものは何通りありますか?998244353で割ったあまりをもとめてください。
- $1, \cdots, N$のどの数も選んだカードのいずれかに書かれている
- $1 \leq N \leq 2 \times 10 ^ 5$
考察
サンプル1を考えます。
3
1 2 3
2 1 3
3枚目のカードは、表裏ともに3が書かれています。このカードを選ばないと条件を満たさなくなるため、選ぶことが確定します。
1, 2枚目のカードは、両方選ぶ/どちらか一方を選ばない ことが可能です。よってこのサンプルの解は3通りとなります。
$P, Q$は$1, \cdots, N$の並び替えなので、
a b c d e
b c d e a
のような組に分けることができます。この組に対して、何通りの取り方ができるかを求めることができればよいです。これを求めます。
-
組の枚数が1枚のとき
具体的には、
a
a
のような場合です。この場合はこのカードを選ばなくてはならないため、1通りです。
-
組の枚数が2枚のとき
具体的には、
a b
b a
のような場合です。この場合は両方選ぶ/どちらか一方を選ばない の3通りが可能です。
-
組の枚数が3枚のとき
具体的には、
a b c
b c a
のような場合です。この場合について考えてみます。
- 1枚目を選ぶ場合
- 2枚目を選び、3枚目を選ぶ
- 2枚目を選び、3枚目を選ばない
- 2枚目を選ばず、3枚目を選ぶ
- 1枚目を選ばない場合
- 2枚目を選び、3枚目を選ぶ
の4通りです。
ここから、
- 1枚目を選ぶ場合
-
$i$番目のカードを選んだ場合、$i+1$番目ではカードを選ぶ/選ばない の2通りが可能
-
$i$番目のカードを選ばなかった場合、$i+1$番目のカードは必ず選ばなくてはならない
ということがわかります。このような選び方を考えていけばよいです。これはDPをすればよいです。
$N$番目の次のカードは1番目であることに注意してください。1番目を選んだ場合と選ばなかった場合で場合分けします。
-
$1$枚目を選んだ場合 : $N$枚目のカードを選ぶ/選ばない が可能
1枚目 2枚目 3枚目 4枚目 5枚目 6枚目 選ぶ 1 1 2 3 5 8 選ばない 0 1 1 2 3 5 -
1枚目を選ばなかった場合 : $N$枚目のカードを選ぶ のみ可能
1枚目 2枚目 3枚目 4枚目 5枚目 6枚目 選ぶ 0 1 1 2 3 5 選ばない 1 0 1 1 2 3
これらをかけていけばよいです。
提出コード
using mint = modint998244353;
int main(){
ll N; cin >> N;
vector<ll> P(N); for(int i = 0; i < N; i++) cin >> P[i];
vector<ll> Q(N); for(int i = 0; i < N; i++) cin >> Q[i];
dsu uf(N);
rep(i, N) uf.marge(P[i] - 1, Q[i] - 1);
vvi ret = uf.groups();
mint ans = 1;
for(auto r: ret) if(r.size() != 1){
mint k = 0;
//1枚目を選ぶ場合
{
pair<mint, mint> dp = {1, 0};
rep(i, r.size() - 1){
dp = {dp.fi + dp.se, dp.fi};
}
k += dp.fi + dp.se;
}
//1枚目を選ばない場合
{
pair<mint, mint> dp = {0, 1};
rep(i, r.size() - 1){
dp = {dp.fi + dp.se, dp.fi};
}
k += dp.fi;
}
ans *= k;
}
cout << ans.val() << '\n';
}
1枚目を選ぶDPと選ばないDPですが、選んだ場合の2枚目以降と選ばなかった場合の3枚目以降は同じです。よってこれらはまとめることができます。これらをまとめると公式解説の式が導けます。きれいですね(DPをしても十分通る制約なのでDPをしてもよいです)。
できませんでした。敗因はこの秋刀魚が半額だったからだと思われます。 https://t.co/at5VD2TnGM
— きょ (@Kyo_s_s) April 10, 2022
次のABCで入青したいです。
Comment is disabled to avoid unwanted discussions from 'localhost:1313' on your Disqus account...