競プロをしながら、節約と株式投資でセミリタイアを目指す東大卒のブログ

東大卒でメーカー勤務の私がセミリタイアするために投資や競プロを頑張っていこうという趣旨で始めたブログです。独身男性です。お金の大切さや今後の生き方も併せて伝えられたらと思います。

ABC166で書いたコード

using System;
using System.Numerics;
using System.Linq;
using System.Collections.Generic;
using System.Text;

namespace Atcoder20200419
{
   class ProgramA
    {
        static void Main(string args)
        {
            //入力
            string a = Console.ReadLine();

           //もしABCならARC,ARCならABC
            if(a == "ABC")
                Console.WriteLine("ARC");
            else
                Console.WriteLine("ABC");

        }
    }
    class ProgramB
    {
        static void Main(string args)
        {
            //入力
            string a = Console.ReadLine().Split(' ');
            int n = int.Parse(a[0]);
            int k = int.Parse(a[1]);
            int sunuke = new int[n];

            //条件を読んで、お菓子を持っていたら1にする
            for (int i = 0i < ki++)
            {
                int d = int.Parse(Console.ReadLine());
                string s = Console.ReadLine().Split(' ');
                for(int j = 0;j <d;j++)
                {
                    sunuke[int.Parse(s[j]) - 1] = 1;
                }
            }
 
            int count = 0;

            //お菓子ない人をあぶりだす
            for (int i = 0i < ni++)
            {
                if (sunuke[i] == 0)
                    count++;
                
            }

            //答え出力
            Console.WriteLine(count);
 
 
        }
    }
    
    class ProgramC
    {
        static void Main(string args)
        {
            //入力
            string a = Console.ReadLine().Split(' ');
            int n = int.Parse(a[0]);
            int m = int.Parse(a[1]);
            long h = new long[n];
            long count = new long[n];

            string s = Console.ReadLine().Split(' ');
            for (int i = 0i < ni++)
                h[i] = long.Parse(s[i]);

            //それぞれ不適合条件を取り出す
            for (int i = 0i < mi++)
            {
                string pass = Console.ReadLine().Split(' ');
                if (h[long.Parse(pass[0]) - 1] > h[long.Parse(pass[1]) - 1])
                    count[long.Parse(pass[1]) - 1]++;

                if (h[long.Parse(pass[0]) - 1] < h[long.Parse(pass[1]) - 1])
                    count[long.Parse(pass[0]) - 1]++;

                if (h[long.Parse(pass[0]) - 1] == h[long.Parse(pass[1]) - 1])
                {
                    count[long.Parse(pass[0]) - 1]++;
                    count[long.Parse(pass[1]) - 1]++;
                }
                    
            }

            int ans = 0;

            //もし不適行条件がなければ足す
            for (int i = 0i < ni++)
            {
                if (count[i] == 0)
                    ans++;
                
            }

            //答え出力
            Console.WriteLine(ans);


        }
    }

    class ProgramD
    {
        static void Main(string args)
        {
            //入力
            long x = long.Parse(Console.ReadLine());

            //Aを0から1000、Bを-1000から1000で全探索(10の6乗なので間に合う)
            for (long i = 0i < 1000i++)
                for (long j = -1000j < 1000j++)
                {
                    if(i*i*i*i*i - j*j*j*j*j == x)
                    {
                        Console.WriteLine(i + " " + j);
                        return;
                    }
 
                }
 
        }
    }

    class ProgramE
    {
        static void Main(string args)
        {
            //入力
            long n = long.Parse(Console.ReadLine());
            long a = new long[n]; //Lの数を残しておく
            long L = new long[n]; //i側の条件
            long R = new long[n]; //j側の条件

            string[] s = Console.ReadLine().Split(' ');

            //式変形からi + Ai = j - Ajでこの比較をする(i < j)
            for (int i = 0i < ni++)
            {
                L[i] = i - long.Parse(s[i]);
                R[i] = i + long.Parse(s[i]);
            }

            long count = 0;

            //i < jの条件下なので、jの値を求める。そしてその時の値がiにあるかみる
            for(int i = 0;i < n;i++)
            {
                //j側の条件を見る
                long temp2 = L[i];
                //aの中にはすでにi側で満たす数が入っている
                if(temp2 > 0)
                    count += a[temp2];

                //R側の条件を求める
                long temp = R[i];

                //i側の条件を追加する
                if(temp < n)
                {
                    a[temp]++;
                }
                

            }

            //答え出力
            Console.WriteLine(count);
        }
    }
    
}

競技プログラミング~ABC166~

おはようございます。しほみんです。

 

2週間前の復習です。ここから最近調子よく解けているので、ようやく軌道に乗ってきたかなあって感じです。もっと早く解きたいのが悩みです。

 

atcoder.jp

 

自分の競技プログラミングへのスタンスです。

<自分のプログラミング力>

・レートは800程度になりました。緑と茶をうろちょろしています。

・C#でクラスとかつかってアプリケーションは作れます。

<Atcoderでのスタンス>

・アルゴリズムについて問題でいろいろ学んでいる。PAST58点の初級レベル。

・基本的に時間がないのでぶっつけ本番でやっている。現在48回参加、もうすぐ一年。

・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色(1200以上)は欲しい。

 

 

今回は、ABCDで30分、1WAでした。まあ、そこそこですが、みんな簡単に解けていたのでレートは低めでした。でも、パフォーマンス1010と744→774で復活してきました。

今回みたいなE問題は結構定番みたいだったのできちんと解きたいところです。A-D問題は速度的に悪くはなかったです。BとCは似た問題だったので、丁寧に解けたのはまあよかったかなと。

 

今回はE問題まで振り返って終わります。

 

 

ここから問題です。

A問題

ABCかARCが与えられます。ABCとARCは交互に開催されます。

次はどっちか出力しなさい。

 

これはifで分岐するだけです。

(構成例)

if(s == "ARC")

   Console.WriteLine("ABC");

else

   Console.WriteLine("ARC");

 

 

B問題

N人の人がいます。(N1,N2,N3,...,Nnとする)

K種類のお菓子があり、それぞれNiの人がそのお菓子を持っています。

お菓子を持っていない人にはいたずらをします。

いたずらをする人数を求めなさい。

 

これもそれぞれ条件をすべて読んで、お菓子を持っている人にフラグを立てます。

そして、そのフラグが立っていない人はお菓子を持っていないので、それを数えればよいです。

 

(構成例)

for(int i = 0; i < n; i++)

{

   int d = int.Parse(Console.ReadLine());

   string s = Console.ReadLine().Split(' ');

    for(int j = 0; j < d; j++)

         ans[int.Parse(s[j]) -1]++;

}

for(int i = 0;i <n;i++)

   if(ans[i] == 0)

      count++;

Console.WriteLine(count);

  

C問題

 Nこの展望台があります。i番目の展望台の高さはHiです。また、異なるM個の道があって、それぞれ展望台iと展望台jがつながっています。

いい展望台はどのつながっている展望台よりも大きい必要があります。

このときいい展望台の数を数えてください。

 

うーんパッと見た感じ結構まとめるのが面倒な感じです。

でもよくよく考えたら条件を丁寧に追っていくだけです。

 

自分はまず全部いい展望台だとして、それぞれ条件を調べていくと満たさないものがあるのでその時は省いていくってことをしました。

最後に残った展望台をカウントして足していくだけです。

ただ、どっちも同じ場合は両方可能性がなくなることに注意です。

 

(構成例)

long H = new long[n];(ここにそれぞれの高さを入れる)

 

for(int i = 0; i < m;i++)

    string[] s = Console.ReadLine().Split(' ');

         if( H[int.Parse(s[0])] > H[int.Parse(s[1])])

                 ans[int.Parse(s[1])]) = 0;

        else if( H[int.Parse(s[0])] < H[int.Parse(s[1])])

                 ans[int.Parse(s[0])]) = 0;

        else//両方同じとき

                ans[int.Parse(s[0])]) = 0;

                ans[int.Parse(s[1])]) = 0;

for(Int i  = 0;i <n;i++)

     sum += ans[i];

Console.WriteLine(sum);

 

D問題

(aの5乗)-(bの5乗)= Nを満たす(a,b)を求めよ。

ただし、Nは存在するa,bの時の数しかない。

 

Nの制限条件を見ます。Nは10の9乗までです。

だとするとa,bは1000から-1000もとれば、a、bは10の15乗から-10の15乗をとるので、

なんかもとめるNは出てきそうです。

 

ということで、全探索します。

aもbも負であることと、aもbも正であることと反転の関係になるので、

aは0から1000、bは-1000から1000までで調べれば十分です。

 

(構成例)

for(int a = 0; a <= 1000; a++)

   for(int b = -1000; b <= 1000;b++)

   {

       if(a*a*a*a*a - b*b*b*b*b == 1)

           Console.WriteLine(a + " "+ b);

           return;

   }

 

 

E問題

N人の参加者がいて、i番の人の身長はAiです。

そして、極秘取引する人は以下の条件です。

・2人の番号の絶対値の差は身長の和に等しい。

 

この満たすペアの数を求めなさい。

 

うーんこのまま考えてしまうとどうあがいてもN(N-1)/2通りを全部求めないとならないので、厳しいです。自分はここで詰まって終わりました。

ここでは式変形を考えてみます。

2人の番号をiとj(i < j)とします。すると上記条件は以下のようにあらわせます。

j -i = Ai + Aj

これを変数分離で分けます。

Ai + i = j - Aj

Xi = Ai+i, Yj = j- Ajはあらかじめ求めておけます。

 

あとはどうやって比較するかですが、i < jの条件をうまく使っていきます。

forループで実はできます。0からN - 1まで考えます。変数をxとします。

1. j = xのYiを求めます。そしてsum[Yi]の数求めます。

2. 最初にi = x -1の時のXiの数値を記録しておきます。(sum[Xi]とかで配列を作ります)

 

あとはこれを繰り返します。

 

こうすることで2のときsumの配列にはi<jの条件のものがすべて入っています。

そして次の1に戻って追加するとi+1のものがはいるので、次の2はj+1でi +1 < j +1で成立したまま考えられます。

 

そこのループはこんな感じです。

for(int x = 0; x < n;x++)

    ans += sum[Yi];

    sum[X(i-1)]++;

 

ただし、sumのとる数は限られるので境界条件だけは気を付けてください。

詳しくはコードを見てください。

 

最後に....

E問題は変数分離さえできればなんとかできた気がしますね。また一歩強くなりたいものです。ではでは。