CF #691 (Div. 2) 参戦記録 p.37

itsukiです。
Codeforces # 691 (Div. 2) に参戦した様子です。解説記事ではありません。

Dashboard - Codeforces Round #691 (Div. 2) - Codeforces

結果は A, B の 2完でした。初めてコンテスト中に 2問解けました！
回答時間合計：72分30秒
スコア：1387

考察の流れ

A. Red-Blue Shuffle

Problem - A - Codeforces

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

Problem - B - Codeforces

ひとまず図を書いて法則性を探す（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 に出ないこと

引き続き、のんびり精進します。

#備忘録 #参戦記録 #codeforces #プログラミング #競プロ #C言語 #691 #Div2