Codeforces Round #605 (Div. 3)
7976 ワード
A. Three Friends
タイトルリンク
テーマの大意
3つの数(a,b,c)をあげて、各数は左、右またはその場で動かないことを選択して、(minleft(left|a-bright|+left|a-cright|+left|b-cright|right)の値を求めることができます)
問題を解く構想.まず定義に従って答えを求め、3つの数が待ちたい場合は0を直接出力し、2つの数が連続している場合は(2)を減算し、そうでない場合は(4)を減算する. は依然として定義に従って答えを求め、4未満であれば0を出力し、そうでなければ4出力を減算する.
ACコード1
ACコード2
B. Snow Walking Robot
タイトルリンク
テーマの大意
1つの四角い格子の中で、(0,0)点から出発して、毎回上へ、下へ、右へ、左へ1つの格子を前進することができて、それぞれ(U,D,R,L)の文字で表して、あなたに(U,D,R,L)だけを含む文字列をあげて、できるだけ少ない文字を削除してそして新しいソートをやり直して、同時に各点が最大1回通過して、最後に(0,0)のこの点に戻って、最後の文字列を出力します.
問題を解く構想.
それぞれの統計(U,D,R,L)の個数が、最後に(0,0)という点に戻るようにするには、(U)と(D)の文字の個数が同じでなければならず、(R)と(L)の文字の個数が同じでなければならない場合、両者の最大値を取って、それぞれ出力すればよい.
ACコード
C. Yet Another Broken Keyboard
タイトルリンク
テーマの大意
文字列(s)、同時に(k)文字の文字配列(t)をあげて、(s)の中で(t)の中の文字だけを含む文字列の個数を求めます.
問題を解く構想.
まず文字配列(t)を巡回し、別の配列(str)で各文字が利用可能か否かをマークし、文字列全体を巡回し、要求に合致する最長文字列長(len)を求め、答えに(frac{ntimesleft(n+1right)}{2})を加えることで可能である.
ACコード
D. Remove One Element
タイトルリンク
テーマの大意
(n)個の数字を含む配列(a)を与えて、配列(a)の中で最大1つの配列を削除することができて、最長で厳格にサブ配列の長さを増加します.
問題を解く構想.
この問題は典型的な動的計画の問題である.
配列dp[i]は(a_i)を起点とする最長子配列長を表し、遷移方程式は[dp[i]=begin{cases}1&i=n\1&a[i]geq a[i+1]\dp[i+1]+1&a[i]配列dp 2[i]は(a_i)を終点とする最長子配列長を表し、遷移方程式は[dp 2[i]=begin{cases}1&i=1\1&a[i-1]geq a[i]\dp[i-1]+1&a[i-1]である 配列全体を巡回(a)、(a_{i+1}>a_{i-1})の場合、結果は(max(result,dp 2[i+1]+dp[i-1]))となる。
ACコード
E. Nearest Opposite Parity
テーマの大意
(n)個の整数からなる配列をあげます.ワンタッチで移動すると、位置(i)から位置(i-a_i)((1leq(i-a_i))の場合)または位置(i+a_i)((i+a_ileq n)の場合)にジャンプできます.
(1)から(n)までの各位置(i)について、任意の位置(j)に到達するために必要な最小移動回数を知りたい場合は、(a_j)と(a_i)が反対のパリティを持つようにします(すなわち、(a_i)が奇数の場合は、(a_j)は偶数でなければなりません.逆も同様です).
問題を解く構想.構想一:逆方向構築図は、偶数の場合、偶数(a_i)から奇数(a_j)までの最小移動回数逆方向構築図の後に、すべての奇数(a_j)から(a_i)までの最短経路の長さが即位する答えであるが、偶数はそれほど多く、各偶数はすべての奇数からその最短経路を計算し、時間の複雑さが高すぎる.このときスーパーソースポイントを使って、1つのポイントからすべての奇数までの距離を(0)に設定して、最短のパスを走って出て、すべての偶数の答えが出てきました.奇数の場合も同じです.つまり、2つのスーパーソースポイントを見つけて最短パスを2回走ります. 構想2:同様に逆方向建図であるが、最短経路ではなく、建図中にジャンプして到達できる点を見つけてキューに入れ、BFS検索すればよい.このようなコード量を大幅に減らすことができます.
ACコード
F. Two Bracket Sequences
テーマの大意
カッコ文字列(s,t)を2つあげて、最も短い合法的な文字列がそのサブシーケンスに文字列(s,t)を含むことを満たすことを見つけます.
問題を解く構想.
この問題もダイナミックプランニングの問題ですが、この問題は3 Dダイナミックプランニングです.(dp[i][j][k])は(s)列が(i)に一致し、(t)列が(j)に一致したときに(k)個()個が一致しない最小長さを表す.移行方程式は書きにくいので、具体的にはコードを見てください.サブシーケンスに(s),(t)が含まれ、最後の文字列ができるだけ短くなるようにするには、文字列(s),(t)で合法的なカッコをできるだけ構築する必要があります.
ACコード
まとめ
やっと(CodeForces)の問題を完全に補完できるようになりました.(A)問題は本当に馬鹿で、そんなに簡単で、その時は意外にも長い間詰まっていました.(B)、(C,D)問題は比較的簡単で、ただ(D)小さな細部がうまく処理されていないので、(wa)は2回も処理されました.(E)、(F)は試合後の交流の後に補充されたものです.とうとう点数が上がった,ううううう
タイトルリンク
テーマの大意
3つの数(a,b,c)をあげて、各数は左、右またはその場で動かないことを選択して、(minleft(left|a-bright|+left|a-cright|+left|b-cright|right)の値を求めることができます)
問題を解く構想.
ACコード1
#include
const int maxn = 1e5+100;
typedef long long ll;
using namespace std;
int q;
ll a[4];
int main()
{
// freopen("data.txt","r",stdin);
cin>>q;
while(q--)
{
for(int i=0;i<3;i++)
{
cin>>a[i];
}
sort(a,a+3);
ll res = a[1]-a[0]+a[2]-a[0]+a[2]-a[1];
if(a[0]==a[1]&&a[1]==a[2]){
}
if(a[0]==a[1]&&a[1]+1==a[2]){
res-=2;
}else if(a[1]==a[2]&&a[0]+1==a[1]){
res-=2;
}else{
res-=4;
}
res = max(1LL*0,res);
cout< ACコード2
#include
typedef long long ll;
using namespace std;
int main()
{
int q;
cin>>q;
while(q--){
int a,b,c;
cin>>a>>b>>c;
int res = abs(a-b)+abs(b-c)+abs(a-c);
res = (res>4)?res-4:0;
cout< B. Snow Walking Robot
タイトルリンク
テーマの大意
1つの四角い格子の中で、(0,0)点から出発して、毎回上へ、下へ、右へ、左へ1つの格子を前進することができて、それぞれ(U,D,R,L)の文字で表して、あなたに(U,D,R,L)だけを含む文字列をあげて、できるだけ少ない文字を削除してそして新しいソートをやり直して、同時に各点が最大1回通過して、最後に(0,0)のこの点に戻って、最後の文字列を出力します.
問題を解く構想.
それぞれの統計(U,D,R,L)の個数が、最後に(0,0)という点に戻るようにするには、(U)と(D)の文字の個数が同じでなければならず、(R)と(L)の文字の個数が同じでなければならない場合、両者の最大値を取って、それぞれ出力すればよい.
ACコード
#include
const int maxn = 1e5+100;
typedef long long ll;
using namespace std;
int main()
{
// freopen("data.txt","r",stdin);
int q;
cin>>q;
while(q--){
string s;
cin>>s;
int a=0,b=0,c=0,d=0;
for(int i=0;i C. Yet Another Broken Keyboard
タイトルリンク
テーマの大意
文字列(s)、同時に(k)文字の文字配列(t)をあげて、(s)の中で(t)の中の文字だけを含む文字列の個数を求めます.
問題を解く構想.
まず文字配列(t)を巡回し、別の配列(str)で各文字が利用可能か否かをマークし、文字列全体を巡回し、要求に合致する最長文字列長(len)を求め、答えに(frac{ntimesleft(n+1right)}{2})を加えることで可能である.
ACコード
#include
const int maxn = 1e5+100;
typedef long long ll;
using namespace std;
bool str[200];
int main()
{
// freopen("data.txt","r",stdin);
for(int i=0;i<200;i++){
str[i]=true;
}
int n,k;
cin>>n>>k;
string s;
cin>>s;
getchar();
for(int i=0;i>c;
str[c-'0']=false;
}
ll res=0;
int cnt=0;
for(int i=0;i D. Remove One Element
タイトルリンク
テーマの大意
(n)個の数字を含む配列(a)を与えて、配列(a)の中で最大1つの配列を削除することができて、最長で厳格にサブ配列の長さを増加します.
問題を解く構想.
この問題は典型的な動的計画の問題である.
配列dp[i]は(a_i)を起点とする最長子配列長を表し、遷移方程式は[dp[i]=begin{cases}1&i=n\1&a[i]geq a[i+1]\dp[i+1]+1&a[i]配列dp 2[i]は(a_i)を終点とする最長子配列長を表し、遷移方程式は[dp 2[i]=begin{cases}1&i=1\1&a[i-1]geq a[i]\dp[i-1]+1&a[i-1]である 配列全体を巡回(a)、(a_{i+1}>a_{i-1})の場合、結果は(max(result,dp 2[i+1]+dp[i-1]))となる。
ACコード
#include
const int maxn = 2e5+100;
typedef long long ll;
using namespace std;
int number[maxn];
ll dp[maxn];
ll dp2[maxn];
int main()
{
// freopen("data.txt","r",stdin);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>number[i];
}
dp[n]=1;
ll res=1;
for(int i=n-1;i>=1;i--){
if(number[i]number[i-1]){
dp2[i] = dp2[i-1]+1;
}else{
dp2[i]=1;
}
}
for(int i=1;i<=n;i++){
if(i+1<=n&&number[i+1]>number[i-1]){
res=max(res,dp[i+1]+dp2[i-1]);
}
}
cout< E. Nearest Opposite Parity
テーマの大意
(n)個の整数からなる配列をあげます.ワンタッチで移動すると、位置(i)から位置(i-a_i)((1leq(i-a_i))の場合)または位置(i+a_i)((i+a_ileq n)の場合)にジャンプできます.
(1)から(n)までの各位置(i)について、任意の位置(j)に到達するために必要な最小移動回数を知りたい場合は、(a_j)と(a_i)が反対のパリティを持つようにします(すなわち、(a_i)が奇数の場合は、(a_j)は偶数でなければなりません.逆も同様です).
問題を解く構想.
ACコード
#include
#define INF 0x3f3f3f3f3f3f3f
const int maxn=2e5+10;
typedef long long ll;
using namespace std;
typedef pair P;
struct edge
{
int to,cost;
};
vectorG[maxn];
int number[maxn];
ll d[maxn];
int n;
ll res[maxn];
void dijks(int s)
{
priority_queue,greater
>pq;
fill(d,d+n+1,INF);
d[s]=0;
pq.push(P(0,s));
while(!pq.empty())
{
P p=pq.top();
pq.pop();
int v=p.second;
if(d[v]
d[v]+G[v][i].cost)
{
d[G[v][i].to]=d[v]+G[v][i].cost;
pq.push(P(d[G[v][i].to],G[v][i].to));
}
}
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>number[i];
}
for(int i=1;i<=n;i++){
if(number[i]+i<=n){
edge e = {i,1};
G[number[i]+i].push_back(e);
}
if(i-number[i]>=1){
edge e = {i,1};
G[i-number[i]].push_back(e);
}
}
for(int i=1;i<=n;i++){
if(number[i]%2==1){
edge e = {i,0};
G[0].push_back(e);
}
}
dijks(0);
for(int i=1;i<=n;i++){
if(number[i]%2==0){
res[i] = d[i];
}
}
G[0].clear();
for(int i=1;i<=n;i++){
if(number[i]%2==0){
edge e = {i,0};
G[0].push_back(e);
}
}
dijks(0);
for(int i=1;i<=n;i++){
if(number[i]%2==1){
res[i] = d[i];
}
}
for(int i=1;i<=n;i++){
if(res[i]>=INF){
cout< F. Two Bracket Sequences
テーマの大意
カッコ文字列(s,t)を2つあげて、最も短い合法的な文字列がそのサブシーケンスに文字列(s,t)を含むことを満たすことを見つけます.
問題を解く構想.
この問題もダイナミックプランニングの問題ですが、この問題は3 Dダイナミックプランニングです.(dp[i][j][k])は(s)列が(i)に一致し、(t)列が(j)に一致したときに(k)個()個が一致しない最小長さを表す.移行方程式は書きにくいので、具体的にはコードを見てください.サブシーケンスに(s),(t)が含まれ、最後の文字列ができるだけ短くなるようにするには、文字列(s),(t)で合法的なカッコをできるだけ構築する必要があります.
ACコード
#include
#define INF 0x3f3f3f3f
const int maxn = 2e2+40;
typedef long long ll;
using namespace std;
int n,m;
string s,t;
bool res[maxn][maxn][2*maxn];
int dp[maxn][maxn][2*maxn];
int dfs(int i,int j,int cnt){
if(i==n&&j==m)
return cnt;
if(cnt>n+m){
return 1e9;
}
if(~dp[i][j][cnt]){
return dp[i][j][cnt];
}
int op1 = 1 + dfs(i+(i>s>>t;
n = s.size();
m = t.size();
dfs(0,0,0);
int i=0,j=0,cnt=0;
while(i まとめ
やっと(CodeForces)の問題を完全に補完できるようになりました.(A)問題は本当に馬鹿で、そんなに簡単で、その時は意外にも長い間詰まっていました.(B)、(C,D)問題は比較的簡単で、ただ(D)小さな細部がうまく処理されていないので、(wa)は2回も処理されました.(E)、(F)は試合後の交流の後に補充されたものです.とうとう点数が上がった,ううううう