Educational Codeforces Round 64 A.Inscribed Figures

A.Inscribed Figures

こんにちは。今回Codeforcesの方にも参加してみたのでその中で解けたというかある意味話題になった問題について書きたいと思います。

詳しくはCodeforcesのリンクを見てください。 問題はこちら

A Inscribed Figures問題の概要をざっくり書くと、丸、四角、三角形を与えられた順に内側に内接させる形でどんどん埋めていき、合計で何点と接しているか求めよという問題です。例えば丸→三角形ですと3点で接します。同様に三角形→丸も3点で接します。ただし四角→三角形の場合下の底辺で共通部分できてしまいます。この場合はInfiniteと出力することになります。以上ざっくりとした問題の説明です。　　

コンテスト中に考えたこと

とは言っても特になくて(笑)ただ紙に具体的に図形を内包させて何点で接するかあるいはInfiniteなのか考えただけでした。コードにコメントアウトしているので解ると思います。 ぱっと実装して投げたところpretestは普通に通りホッとしてました。...がここでなんとpretestにミスが見つかりリジャッジされることに...codeforcesならではなんですかね。 知りませんが()。 そしてリジャッジの結果なんと落ちました。(1500人くらいは落ちてた気がする)どうしてなのかなーと考えているうちになんとunratedに...。codeforcesの洗礼を浴びてしまいました。 ただ気になるので深く考えたところ、四角→丸→三角の並びのときに上の頂点が一致してしまいます。すなわちこのパターンがあるときは1だけ引かなければいけません。いわゆるコーナーケース ですね。これを直して無事通りました。 問題としては易しいので英語の勉強がてらやってみてはいかがでしょうか。 以下コードです。

#include <iostream>

using namespace std;

int main() {
    int n;
    int a[110];
    cin>>n;
    for(int i=0;i<n-1;i++) cin>>a[i];
  //1が丸　2が三角　3が四角
  // 四角→三角や三角→四角は底辺が重なるので"Infinite"
    for(int i=0;i<n-1;i++){
        if((a[i]==3 && a[i+1]==2) || (a[i]==2 && a[i+1]==3) ){
            cout<<"Infinite"<<endl;
            return 0;
        }
    }
    int cnt=0;
  // 丸と三角の場合+3 丸と四角の場合+4
    for(int i=0;i<n-1;i++){
        if((a[i]==1 && a[i+1]==2) || (a[i]==2 && a[i+1]==1) ) cnt+=3;
        else if((a[i]==1 && a[i+1]==3) || (a[i]==3 && a[i+1]==1) ) cnt+=4; 
    }
  // 四角→丸→三角のとき上の接点が重なるので-1
    for(int i=0;i<n-2;i++){
        if(a[i]==3 && a[i+1]==1 && a[i+2]==2) cnt--;
    }
    cout<<"Finite"<<endl;
    cout<<cnt<<endl;


    return 0;
}