AtCoder Grand Contest 043
6366 ワード
Preface
とても毒の1度、ABは自分で思った(ORZ陳指導)、Cはまったく問題解の神仙のやり方を感嘆することができなくて、Dはもともとすでに作ってそれから複雑に考えました(あるいは習慣が使然としますか?)
E私は長い間問題を見ても分からないし、この移動曲線の定義が仙人で、F神仙問題はできないので、捨てられた.
A - Range Flip Find Route
ごみhl 666日常はテーマを見間違えて、テーマの中の反転矩形は反転正方形と見なしました
実際に見損なわなければ簡単です.二つの方向にしか歩けないので、つながっている黒い格子は全部一度にひっくり返すことができます.DPを作って、各点が反転しているかどうかを記録すればいいです.
B - 123 Triangle
ちょっと頭を使うB問題.まず、この数列は一度も行われていないことがわかります.すべての数は減少するか、変わらないかのどちらかです.
最初は(0)がなかったので、先に作ってあげましたが、今は数列に(0,1,2)しかありません.
前に述べた答えはこの3つしかありませんが、データを手にすると(2)があまり現れないことがわかります.私たちはいつ(2)があるかもしれないかを考えてみましょう.
簡単な証明(または推定?)を経て,答えが(2)である必要条件は数列に(0,2)しかないことであることが分かった.
理由は簡単です.(1)の出現があれば、(0)も(2)も発生するので、答えは(2)ではありません.
私たちはまずこのような状況を置いて、今数列の中に(1)があることを考えて、それでは私たちはよく考えてみると、この時の答えは(0)か(1)しかない以上、私は(2)をすべて(0)と見なすことができません!
だから今は数列に(0,1)しかありません.そして、この時の減算が異或になったことに気づきました.それから、私たちは直接各数の答えへの貢献を考えました.
この数列の変換過程が楊輝三角であることは個人的にも分かるので,係数は組合せ数である.
次に、(C_n^m)のパリティを要求します.この古典的なやり方は、ルーカスの定理に基づいています.
\[C_n^m=C_{\lfloor\frac{n}{2}\rfloor}^{\lfloor\frac{n}{2}\rfloor}\times C_{n\mod 2}^{m\mod 2}\]
(2 ot|C_n^m)では(m)バイナリの各ビットが(n)より小さく、(noperatorname{xor}m=n-m)に等しいことがわかりやすい.
そしてまた振り返ってみると(0,2)だけの場合、直接(2)を(1)として最後に(2)を乗せればいいのです
C - Giant Graph
神様の問題、この考え方は本当に巧みですね.
まず、その点の寄与がおかしいことを発見しました.では、ここから始めましょう.((x,y,z))と((x',y',z'))について、(x+y+zであれば、((x,y,z))の寄与が選択((x',y',z'))を超えることはありません(トップ(10^{18})個ですから)
したがって,点の(x+y+z)の大きさに従って逆順に貪欲に取るだけでよいことが分かった.このとき,無方向図を有方向図に変えることができる.
そして、私たちがこの値を列挙して、どれだけ選択できるかを考えて、それから......
それから全然できないことに気づいて、直接GG(点開題解)
私达は1つの経典のゲーム论の问题を考えにきます:1枚は図の上に1つの驹があって、2人は交代で移动して、毎回必ず図の上の辺に沿って歩かなければならなくて、谁が歩けないで负けて、どれらの点が先手の必ず负ける点を闻きます
各点のSG関数を求めることを容易に考え,このときのすべての(SG_x=0)の点が選択でき,前の貪欲な要求を満たすことに驚く.
妙は妙だが、これはただの図だろう.慌てないで、私达は点の间の连辺の方式を観察して、简単にこの时の3枚の図が互いに独立していることを発见して、ゲーム论の姿势によってこの时の1つの点のSG関数は3枚の図の中で対応する点のSG関数の异或値です
したがって,一つの点((x,y,z))が(SG 1_xoperatorname{xor}SG 2_xoperatorname{xor}SG_3=0)を満たすと,この点は最後に選択できる.
そこで図ごとにSG関数を求めて(SG_i=x)の寄与を統計して直接列挙すればよい
注意1枚のDAGのSG関数は(O(sqrt n))であるため、総複雑度は(O(n))である(サボり用の
D - Merge Triplets
ORZは気違いに性質の陳指導を探して、私は混じって飲んでこの問題をしました
まず,最後のPPシーケンスを直接DPすることを考慮し,シナリオ数を求めることを肯定する.
私たちは簡単に1つの性質を見つけることができます:(forall iin[1,n-3],a_i,とても簡単で、もし1つの数字がその後ろの3つの数よりも大きいならば、それは必然的に同じグループから来たことを説明して、このように4つの数と1つのグループが題意に合わないことがあります
次に,このシーケンスを長さ(1/2/3)のサブ列に分割することができ,各サブ列の先頭が後の数より大きいことが分かった.次に,各サブストリングの先頭の数は必ずそれ以前のすべての数より大きいことを見出した.
そしてそれだけで終わりですか?明らかに違う!これは各グループが3つを超えないことを保証するだけなので、総グループ数が(n)であることをどのように保証するかを考えます.
すべての長さが(3)の文字列が明らかに三元グループになっていることを考慮し、残りの長さが(1)と長さが(2)の
長さが(1)の文字列は(1,1,1)でもよいし、長さが(2)の(1,2)でもよいし、長さが(2)のものは(1)とつづるしかない
そこで、長さが(2)の文字列の個数が長さが(1)の文字列の個数以下であるという別の性質を得た.
そこで充要性を満たし,DPを考えると,(f_{i,j,k})は既に確定した前(i)個数を表し,長さが(2)の文字列個数から長さが(1)の文字列個数を減算し,前回の文字列先頭が(k)のシナリオ数を表すと考えられる.
移転は非常に明らかで、直接(O(n^4))の暴力を出すことができて、明らかに接頭辞と最適化で(O(n^3))になりやすいが、どうせ通れないなら必要ない.
暴力コード
そしてこの列挙の冒頭の考えに偏り、そのまま穴に落ちた.
実際には,すべての数の相対順序を決定するだけで,相対順序が決定されるとシーケンス全体が決定されることを考慮した.
従って、例えば、長さが(2)の文字列を入れる場合、前の(i)個数に(i+1)の相対位置があるので、係数に((i+1))を乗じて、他の場合と同様である
そして(O(n^2))してしまいました233
Postscript
本当に私が怠けているのではありませんて、EFはしてはいけないように見えて、道QQQを捨てました
とても毒の1度、ABは自分で思った(ORZ陳指導)、Cはまったく問題解の神仙のやり方を感嘆することができなくて、Dはもともとすでに作ってそれから複雑に考えました(あるいは習慣が使然としますか?)
E私は長い間問題を見ても分からないし、この移動曲線の定義が仙人で、F神仙問題はできないので、捨てられた.
A - Range Flip Find Route
ごみhl 666日常はテーマを見間違えて、テーマの中の反転矩形は反転正方形と見なしました
実際に見損なわなければ簡単です.二つの方向にしか歩けないので、つながっている黒い格子は全部一度にひっくり返すことができます.DPを作って、各点が反転しているかどうかを記録すればいいです.
#include
#include
#include
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int n,m,f[N][N][2]; char a[N][N];
int main()
{
RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%s",a[i]+1);
memset(f,127,sizeof(f)); if (a[1][1]=='.') f[1][1][0]=0; else f[1][1][1]=1;
for (i=1;i<=n;++i) for (j=1;j<=m;++j) if (i!=1||j!=1)
if (a[i][j]=='.') f[i][j][0]=min(min(f[i-1][j][0],f[i-1][j][1]),min(f[i][j-1][0],f[i][j-1][1]));
else f[i][j][1]=min(min(f[i-1][j][0]+1,f[i-1][j][1]),min(f[i][j-1][0]+1,f[i][j-1][1]));
return printf("%d",a[n][m]=='.'?f[n][m][0]:f[n][m][1]),0;
}
B - 123 Triangle
ちょっと頭を使うB問題.まず、この数列は一度も行われていないことがわかります.すべての数は減少するか、変わらないかのどちらかです.
最初は(0)がなかったので、先に作ってあげましたが、今は数列に(0,1,2)しかありません.
前に述べた答えはこの3つしかありませんが、データを手にすると(2)があまり現れないことがわかります.私たちはいつ(2)があるかもしれないかを考えてみましょう.
簡単な証明(または推定?)を経て,答えが(2)である必要条件は数列に(0,2)しかないことであることが分かった.
理由は簡単です.(1)の出現があれば、(0)も(2)も発生するので、答えは(2)ではありません.
私たちはまずこのような状況を置いて、今数列の中に(1)があることを考えて、それでは私たちはよく考えてみると、この時の答えは(0)か(1)しかない以上、私は(2)をすべて(0)と見なすことができません!
だから今は数列に(0,1)しかありません.そして、この時の減算が異或になったことに気づきました.それから、私たちは直接各数の答えへの貢献を考えました.
この数列の変換過程が楊輝三角であることは個人的にも分かるので,係数は組合せ数である.
次に、(C_n^m)のパリティを要求します.この古典的なやり方は、ルーカスの定理に基づいています.
\[C_n^m=C_{\lfloor\frac{n}{2}\rfloor}^{\lfloor\frac{n}{2}\rfloor}\times C_{n\mod 2}^{m\mod 2}\]
(2 ot|C_n^m)では(m)バイナリの各ビットが(n)より小さく、(noperatorname{xor}m=n-m)に等しいことがわかりやすい.
そしてまた振り返ってみると(0,2)だけの場合、直接(2)を(1)として最後に(2)を乗せればいいのです
#include
#include
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int n,b[N],ret; char a[N]; bool one;
int main()
{
RI i,j; for (scanf("%d%s",&n,a),--n,i=0;i C - Giant Graph
神様の問題、この考え方は本当に巧みですね.
まず、その点の寄与がおかしいことを発見しました.では、ここから始めましょう.((x,y,z))と((x',y',z'))について、(x+y+zであれば、((x,y,z))の寄与が選択((x',y',z'))を超えることはありません(トップ(10^{18})個ですから)
したがって,点の(x+y+z)の大きさに従って逆順に貪欲に取るだけでよいことが分かった.このとき,無方向図を有方向図に変えることができる.
そして、私たちがこの値を列挙して、どれだけ選択できるかを考えて、それから......
それから全然できないことに気づいて、直接GG(点開題解)
私达は1つの経典のゲーム论の问题を考えにきます:1枚は図の上に1つの驹があって、2人は交代で移动して、毎回必ず図の上の辺に沿って歩かなければならなくて、谁が歩けないで负けて、どれらの点が先手の必ず负ける点を闻きます
各点のSG関数を求めることを容易に考え,このときのすべての(SG_x=0)の点が選択でき,前の貪欲な要求を満たすことに驚く.
妙は妙だが、これはただの図だろう.慌てないで、私达は点の间の连辺の方式を観察して、简単にこの时の3枚の図が互いに独立していることを発见して、ゲーム论の姿势によってこの时の1つの点のSG関数は3枚の図の中で対応する点のSG関数の异或値です
したがって,一つの点((x,y,z))が(SG 1_xoperatorname{xor}SG 2_xoperatorname{xor}SG_3=0)を満たすと,この点は最後に選択できる.
そこで図ごとにSG関数を求めて(SG_i=x)の寄与を統計して直接列挙すればよい
注意1枚のDAGのSG関数は(O(sqrt n))であるため、総複雑度は(O(n))である(サボり用の
mapでなければ)#include
#include
#include
#include
#include D - Merge Triplets
ORZは気違いに性質の陳指導を探して、私は混じって飲んでこの問題をしました
まず,最後のPPシーケンスを直接DPすることを考慮し,シナリオ数を求めることを肯定する.
私たちは簡単に1つの性質を見つけることができます:(forall iin[1,n-3],a_i,とても簡単で、もし1つの数字がその後ろの3つの数よりも大きいならば、それは必然的に同じグループから来たことを説明して、このように4つの数と1つのグループが題意に合わないことがあります
次に,このシーケンスを長さ(1/2/3)のサブ列に分割することができ,各サブ列の先頭が後の数より大きいことが分かった.次に,各サブストリングの先頭の数は必ずそれ以前のすべての数より大きいことを見出した.
そしてそれだけで終わりですか?明らかに違う!これは各グループが3つを超えないことを保証するだけなので、総グループ数が(n)であることをどのように保証するかを考えます.
すべての長さが(3)の文字列が明らかに三元グループになっていることを考慮し、残りの長さが(1)と長さが(2)の
長さが(1)の文字列は(1,1,1)でもよいし、長さが(2)の(1,2)でもよいし、長さが(2)のものは(1)とつづるしかない
そこで、長さが(2)の文字列の個数が長さが(1)の文字列の個数以下であるという別の性質を得た.
そこで充要性を満たし,DPを考えると,(f_{i,j,k})は既に確定した前(i)個数を表し,長さが(2)の文字列個数から長さが(1)の文字列個数を減算し,前回の文字列先頭が(k)のシナリオ数を表すと考えられる.
移転は非常に明らかで、直接(O(n^4))の暴力を出すことができて、明らかに接頭辞と最適化で(O(n^3))になりやすいが、どうせ通れないなら必要ない.
暴力コード
#include
#define RI int
#define CI const int&
using namespace std;
const int N=105;
int n,mod,f[N*3][N*6][N*3],ans;
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
int main()
{
RI i,j,k,t; for (scanf("%d%d",&n,&mod),f[0][n*3][0]=1,i=0;i<3*n;++i)
for (j=0;j<=6*n;++j) for (k=0;k<=3*n;++k) if (f[i][j][k]) for (t=k+1;t<=3*n;++t)
{
inc(f[i+1][j-1][t],f[i][j][k]);
if (t-1-i>0) inc(f[i+2][j+1][t],1LL*f[i][j][k]*(t-1-i)%mod);
if (t-1-i>1) inc(f[i+3][j][t],1LL*f[i][j][k]*(t-1-i)%mod*(t-2-i)%mod);
}
for (i=0;i<=3*n;++i) inc(ans,f[3*n][i][3*n]); return printf("%d",ans),0;
}
そしてこの列挙の冒頭の考えに偏り、そのまま穴に落ちた.
実際には,すべての数の相対順序を決定するだけで,相対順序が決定されるとシーケンス全体が決定されることを考慮した.
従って、例えば、長さが(2)の文字列を入れる場合、前の(i)個数に(i+1)の相対位置があるので、係数に((i+1))を乗じて、他の場合と同様である
そして(O(n^2))してしまいました233
#include
#define RI int
#define CI const int&
using namespace std;
const int N=6005;
int n,mod,f[N][N<<1],ans;
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
int main()
{
RI i,j,k,t; scanf("%d%d",&n,&mod); n*=3; f[0][n]=1;
for (i=0;i Postscript
本当に私が怠けているのではありませんて、EFはしてはいけないように見えて、道QQQを捨てました