日曜日を赤太字にしてほしい男の備忘録です
コンテスト概要
AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY）
開催日:2025年4月27日 21:00-22:40
A - Odd Position Sum
考察
奇数番目を抜き出し総和を出すだけ。
for,if,%が使えればOK。0-indexにだけ注意。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int sum = 0;
for(int i=0;i<n;i++){
int x;
cin >> x;
//0-index(ゼロ始まり)なのでiが偶数の時に抜き出す。
if(i%2 == 0) sum += x;
}
cout << sum << endl;
}
B - Four Hidden
考察
高々10文字なので多少の無理も通りそう。
今回は安直に一文字ずつずらしながら確かめる。
ワイルドカードが多少厄介だが例外処理として扱えば、すべての文字列が一致しているかを確かめるだけで済む。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
string t,u;
cin >> t >> u;
string ans = "No";
//比較対象の文字数をlenとする
int len = u.length();
for(int i=0;i+len <= t.length();i++){
//文字列Tのi番目からlen文字を抜き取る。
string s = t.substr(i,len);
bool c = true;
for(int j=0;j<len;j++){
//j文字目が？なら無視
if(s[j] == '?') continue;
//文字が異なっているなら不一致
if(s[j] != u[j]) c = false;
}
//一致する部分文字列があったならYes
if(c) ans = "Yes";
}
cout << ans << endl;
}
C - 403 Forbidden
考察
安直に考えるのであれば、「ページごとに権限を持っている人リスト」もしくは「人ごとに見れるページのリスト」のどちらかを保持。質問された際にリストを参照すればおしまい。
と、行きたいところだがクエリ2「すべてのページの閲覧権限付与」が厄介。もしページが$10^5$ページあるならクエリ２ごとに$10^5$ページすべてのリストを書き換る必要がある。それを$10^5$人分行うとすれば間違いなくTLEになってしまう。
なのでクエリ２をうまく対処する必要がありそう。
全ページ書き換えるのが大変なら、書き換えた”ふり”をすればよさそう。全ページの権限を与えられた人は「全部見れる人リスト」で管理する。そうすれば作業は1回で済む。
というわけで流れとしては、
〇「ページごとの見れる人リスト」と「全ページ見れる人リスト」を用意。
〇クエリ１のとき「ページYを見れる人リスト」にXさんを追加
〇クエリ２のとき「全ページ見れる人リスト」にXさんを追加
〇クエリ３のときXさんが「全ページ見れる人リスト」にいるならYes。
そうでなくても「ページYを見れる人リスト」にXさんがいればYes。
こうすれば時間も余裕でACできる。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,m,q;
cin >> n >> m >> q;
//ページごとの見れる人リスト
vector<set<int>>num (m+1);
//全ページを見れる人リスト
vector<bool>evr (n+1,false);
for(int i=0;i<q;i++){
int c;
cin >> c;
if(c == 1){
int x,y;
cin >> x >> y;
//ページYのリストにXさんを追加
num[y].insert(x);
}
if(c == 2){
int x;
cin >> x;
//全ページ見れる人リストにXさんを追加
evr[x] = true;
}
if(c == 3){
int x,y;
cin >> x >> y;
//そもそも全ページ見れるならYes
if(evr[x]) cout << "Yes" << endl;
else{
//ページのリストの中にいるならYes
auto f = num[y].find(x);
if(f == num[y].end()) cout << "No" << endl;
else cout << "Yes" << endl;
}
}
}
}
D - Forbidden Difference
考察
数列のどの2つの数字をとっても差がDのものが出ないようにするのが目的。
なので順番とかには興味がなく、それぞれの数字が登場した回数が重要。この問題では回数だけ記憶することにする。
D=0のとき、すなわち数字はかぶってはいけないとき、重複のある数字を1個以外すべて削除すればよい。
D≠0のとき、Dで割った余りが同じものは相互に作用しうることがわかる。
例えばNを残すなら、差がDの（N-D）と（N+D）は消さなければならない。(N+D)が消えたので差がDの(N+2*D)は残してもよくて...
という風に差がDのものに作用していく。裏を返せば余りが異なるものはそれぞれ独立なので、余りごとに考えてあとで合算すればよさそう。
どれを残し、どれを消したら最大になるかはDPの得意分野なので余りごとにやっていく。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,d;
cin >> n >> d;
//D=0のとき
if(d == 0){
//（数字の種類）=（最終的な数列の要素数）
set<int>st;
for(int i=0;i<n;i++){
int x;
cin >> x;
st.insert(x);
}
//ほしいのは「消した数字の数」
cout << n - st.size() << endl;
return 0;
}
int lim = 1e6;
//1~1000000までの数の登場回数を管理
vector<int>num (lim + 1,0);
for(int i=0;i<n;i++){
int x;
cin >> x;
num[x]++;
}
//DP[0]：直前で消すという選択をした場合に数列に残る要素数。
//DP[1]：直前で残すという選択をした場合に数列に残る要素数。
vector<int>dp (2,0);
//余りごとにDPを計算
for(int i=0;i<d;i++){
int now = i;
while(now <= lim){
vector<int>nex (2,0);
//消す選択
//直前の「残す」「消す」のうち大きいほう
nex[0] = max(dp[0],dp[1]);
//残す選択
//直前の「消す」選択に「数字の個数」を足したもの
nex[1] = dp[0] + num[now];
dp = nex;
now += d;
}
//余りごとに独立なので大きいほうに合わせる
dp[1] = max(dp[0],dp[1]);
dp[0] = dp[1];
}
//ほしいのは「残った数」ではなく「消した数」
cout << n - dp[0] << endl;
}
E - Forbidden Prefix
考察
Trie木のことは知ってます。はい。
知ってるだけです。勉強します。はい。
F - Shortest One Formula
考察
得点がE問題と同じ、かつE問題を知識外であることが確定していたのでF問題に専念。
制約がやたら小さいので「2000個すべて列挙できるんじゃない？」と思い方針を立てる。
いろいろと言ってるが、できることは「足し算」と「掛け算」だけ。なのでそれぞれの数字ごとにどっちがより短く書けるかを調べ、よさそうなほうを採用する。
また式の作り方だが、N-1までの式ができていることを前提としてそれら2つを'+'または'*'で連結すればよさそう。
〇足し算
作りたい数をNとして、Nを2つの自然数i,jに分ける（i+j=N）。そして「iの式」と「jの式」を'+'で連結する。これをiを1から順に試す。この時一番文字数が少なく済んだものを「足し算の式」とする。
〇掛け算
作りたい数をNとして、Nを2つの自然数i,jに分ける(ij=N)。そして「iの式」と「jの式」を''で連結する...
と行きたいところだが、この「掛け算」一つ厄介なポイントがある。それは()を付ける必要があるということ。
安直につければよさそうだが例えば式iが(A)ｘ(B)という形だった場合、ここにはさらに()を付ける必要はなくそのまま連結してＯＫ。一方(A)ｘ(B)+(C)のときは()でくくる必要がある。
要するに式iが「足し算の式」の場合は()をつけ、「掛け算の式」なら不必要という塩梅である。
というわけであらかじめ式iが「足し算の式」を採用したか「掛け算の式」を採用したかのリストを持っておく必要がある。
下準備が終われば後は足し算同様に連結し文字数を調べ良いものを「掛け算の式」とする。
で、あとは「足し算の式」と「掛け算の式」でよいものをＮの式にする。
また「掛け算の式」を採用したならリストも更新しておく
これを欲しい数字まで繰り返す。
後1つ、注意点としては「１だけの数字」は「1だけの式」をあらかじめ立項しておく。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
//どんな数字にも対応できるよう2000までの式をあらかじめ作る方針
vector<string>ans (2001,"");
//最初の3つはどうせこうなので直接入力
ans[1] = "1",ans[2] = "1+1",ans[3] = "1+1+1";
//１だけの数字はベタ打ち
ans[11] = "11",ans[111] = "111",ans[1111] = "1111";
//「掛け算の式」かを確認する配列
vector<bool>mp (2001,false);
//１だけの数字ももちろん()は不要
mp[11] = mp[111] = mp[1111] = true;
for(int i=4;i<2001;i++){
//すでに式があるものは無視
if(ans[i] != "") continue;
//とりあえず大きい値を入れておく
int len = 4000;
for(int j=1;j<i;j++){
//式2つを+で連結されたものと長さを比べる
if(ans[j].length() + ans[i-j].length() + 1 < len){
//改善されたなら暫定的に式を更新
len = ans[j].length() + ans[i-j].length() + 1;
ans[i] = ans[j] + '+' + ans[i-j];
}
}
for(int j=2;j*j<=i;j++){
//割り切れないなら論外
if(i%j != 0) continue;
int xl = ans[j].length(), yl = ans[i/j].length();
string xs = ans[j],ys = ans[i/j];
//「足し算の式」なら両方に()を付けておく
if(!mp[j]) xl += 2, xs = '(' + xs + ')';
if(!mp[i/j]) yl += 2,ys = '(' + ys + ')';
//()を付けた後の2式を*で連結したものと長さを比べる
//文字数が「足し算の式」と同じでも後々掛け算のほうが得なので
//「掛け算の式」を優先させる
if(xl + yl + 1 <= len){
//改善されたら暫定的に式を更新
len = xl + yl +1;
ans[i] = xs + '*' + ys;
//この段階で「掛け算の式」の採用が確定しているので
//配列を更新
mp[i] = true;
}
}
}
int n;
cin >> n;
//すきなかずをだす
cout << ans[n] << endl;
}
結果
ABCD(1)F 5完 83:00 バーチャル参加
順位 814位相当
パフォーマンス 1588相当
感想
最近E問題解けなさすぎ。F問題が得意でギリギリ助かっている感じ。
まぁ文字列苦手なので勉強ですね。
前回も似たようなことを言った気がするけど。