CF #691 (Div. 2) 参戦記録 p.37
itsukiです。
Codeforces # 691 (Div. 2) に参戦した様子です。解説記事ではありません。
結果は A, B の 2完でした。初めてコンテスト中に 2問解けました！
回答時間合計：72分30秒
スコア：1387
考察の流れ
A. Red-Blue Shuffle
n <= 1000 だから、順列の全探索は無理そう
確率の値ではなく「どっちが勝つ確率が高いか」を求めればいい
1枚のカードに 2つの数字が書かれているので、各カードに書かれた数値の大小をカウントする
「書かれている数字が相手よりも大きいカード」を先頭桁にすれば相手に勝てるので、カウント数が多い方が勝つ確率が高い
#include <stdio.h>
int main(){
int t;
scanf("%d",&t);
while(t){
int i,n,cnt=0;
char r[1005]={0},b[1005]={0};
scanf("%d",&n);
scanf("%s",r);
scanf("%s",b);
for(i=0; i<n; i++){
if ( r[i] > b[i] ){ cnt++; }
else if( r[i] < b[i] ){ cnt--; }
}
if ( cnt > 0 ){ printf("RED\n"); }
else if( cnt < 0 ){ printf("BLUE\n"); }
else { printf("EQUAL\n"); }
t--;
}
return 0;
}ここまで：25分16秒
・問題末尾の Note がすごく親切で助かった
B. Move and Turn
ひとまず図を書いて法則性を探す（N=1 の場合はべた書きで 4 を返すことにする）
どうやら偶奇で分かれるようで、綺麗だな～と悠長に N=7 まで手書きする（下図の赤が N=6, 青が N=7）
N が偶数の場合は、 N=2 は 4 (2*2)、N=4 は 9 (3*3)、N=6 は 16 (4*4)…
N が奇数の場合は、N=3 は 12（縦 2 点が 3 列 + 縦 3 点が 2 列）、N=5 は 24（縦 3 点が 4 列 + 縦 4 点が 3 列）、N=7 は 40（縦 4 点が 5 列 + 縦 5 点が 4 列）…
#include <stdio.h>
int main(){
int i,n;
scanf("%d",&n);
if (n==1) { printf("4\n"); }
else if(n%2==0){ printf("%d\n", ((n/2)+1)*((n/2)+1) ); }
else { printf("%d\n", ((n/2)+1)*((n/2)+2)*2); }
return 0;
}ここまで：72分30秒
・規則性が綺麗で解いてて楽しかった
・複数のテストケースに回答する問題が多いイメージがあったが、なるほど規則性が見えてしまうから単一のテストケースをこなす問題だったのだろうか？
まとめ
・初の 2完で嬉しい
・「18:35から開始」という超人権こどふぉだったので参加したが、終了25分後から始まった AtCoder Beginer Contest 186 は散々だった…すべてを使い果たしてしまった
・当面、同じ日に Codeforces と AtCoder の Rated に出ないこと
引き続き、のんびり精進します。