ABC057

過去問をC#で解いていく・・・

コードの中にコメント書いてく形式にしてみました。

A問題

using System;

class Program{
 public static void Main(){

   var input = Console.ReadLine().Split(' ');
   int a = int.Parse(input[0]);
   int b = int.Parse(input[1]);
   
   int ans = a + b;
   if(ans >= 24) ans -= 24;

   Console.WriteLine(ans);
 }
}

B問題

using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

class Program{
 public static void Main(){

   //入力
   var nm = Console.ReadLine().Split();
   int n = int.Parse(nm[0]);
   int m = int.Parse(nm[1]);
   
   int[] a = new int[n];
   int[] b = new int[n];
   int[] c = new int[m];
   int[] d = new int[m];
   
   for(int i=0; i<n; i++){
     var ab = Console.ReadLine().Split();
     a[i] = int.Parse(ab[0]);
     b[i] = int.Parse(ab[1]);
   }
   for(int i=0; i<m; i++){
     var cd = Console.ReadLine().Split();
     c[i] = int.Parse(cd[0]);
     d[i] = int.Parse(cd[1]);
   }
   
   //処理
   for(int i=0; i<n; i++){
     //1番目のチェックポイントを初期値に設定
     int min = Math.Abs(a[i]-c[0]) + Math.Abs(b[i]-d[0]);;
     int ans = 0;
     
     //2番目以降のチェックポイントとの比較
     for(int j=1; j<m; j++){
       int l = Math.Abs(a[i]-c[j]) + Math.Abs(b[i]-d[j]);
       
       //より近いチェックポイントがあれば入れ替える
       if(l < min){
         min = l;
         ans = j;
       }
     }
     Console.WriteLine(ans+1);
   }
 }
}

あ

C問題

Nが10^10なので、普通にループを回すと間に合わない。

A<Bとしたとき、Nの平方根をSQRTは、A<=SQRT<=Bとなるはず(証明はしません)。このとき、Aは10^5以下になるから、平方根をとった後、先にAを決定して、そこから大きいほうのBの桁数を求めればOK！

using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

class Program{
 public static void Main(){

   //入力
   long n = long.Parse(Console.ReadLine());
   
   //処理
   long a = 0 , b = 0;
   //nの平方根を求める
	long m = (long)Sqrt(n);
   //mから割り切れる数を探して、F(a,b)が最小となる組み合わせを探す
   for(long i=m; i>0; i--){
     if(n % i == 0){
       a = i;
       b = n / a;
       break;
     }
   }
   
   //桁数を求める
   int ans = 0;
   while(b>0){
     b /= 10;
     ans++;
   }
   
   Console.WriteLine(ans);
 }
}

D問題

まず、選んだ品物の価値の平均が最大になるのは、価値が大きいほうからA個選べばいい。ポイントとなるのが、大きいほうからA個目と同じ価値の品物(Vaとする)が複数あった場合。複数あるうちから品物の数の合計がA個以上、B個以下になるように、Vaの品物を選択する。

n個からk個を選択するとき、nCkの計算が必要になるが、nCkの値はパスカルの三角形と対応するらしい。DPでパスカルの三角形のグラフを作成し、そこから必要となるnCkの値を使って答えを求める。

using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

class Program{
 public static void Main(){

   //入力
   var input = Console.ReadLine().Split();
   int n = int.Parse(input[0]);
   int a = int.Parse(input[1]);
   int b = int.Parse(input[2]);
   
   var input2 = Console.ReadLine().Split();
   long[] v = new long[n];
   for(int i=0; i<n; i++){
     v[i] = long.Parse(input2[i]);
   }
   
   //処理
   
   //降順に並べ替え
   Array.Sort(v);
   Array.Reverse(v);
   
   //解答用の変数の宣言
   double ave = 0;
   long num = 0;
   
   //一番大きい数とA番目に大きい数が同じ場合
   if(v[0] == v[a-1]){
     ave = v[0];
     
     //同じ要素の個数を数える
     int cnt = 0;
     for(int i=0; i<n; i++){
       if(v[0] != v[i]) break;
       else cnt++;
     }
     
     //dpでパスカルの三角形をつくる
     long[,] dp = new long[cnt+1,cnt+1];
     dp[0,0] = 1;
   　for(int i=1; i<=cnt; i++){
      for(int k=0; k<=i; k++){
       if(k >= 1){
         dp[i,k] = dp[i-1,k-1] + dp[i-1,k];
       }
       else {
         dp[i,k] = dp[i-1,k];
       }
      }
    }
     
     int sml = Min(b,cnt);
     for(int i=a; i<=sml; i++){
       num += dp[cnt,i];
     }
   }

   
   //一番大きい要素とA番目に大きい数が異なる場合
   else{
     long wa = 0;
     for(int i=0; i<a; i++){
       wa += v[i];
     }
     ave = (double)wa / a;
     
     //v[a-1]と同じ値の要素数を数える
     bool flg = false;
     int cnt = 0;
     int index = 0;
     
     for(int i=0; i<n; i++){
       if(v[i] == v[a-1]){
         if(!flg){
           index = i;//同じ値の要素番号をメモ
           flg = true;
         }
         cnt++;
       }
       if(flg == true && v[i] != v[a-1]){
         break;
       }
     }
     
     //dpでパスカルの三角形をつくる
     long[,] dp = new long[cnt+1,cnt+1];
     dp[0,0] = 1;
   　for(int i=1; i<=cnt; i++){
      for(int k=0; k<=i; k++){
       if(k >= 1){
         dp[i,k] = dp[i-1,k-1] + dp[i-1,k];
       }
       else {
         dp[i,k] = dp[i-1,k];
       }
      }
    }
     
     num = dp[cnt,a-index];
   }
   
   Console.WriteLine(ave);
   Console.WriteLine(num);
 }
}

パスカルの三角形、2か所で作っていて見栄え悪いですが、悪しからず。問題そのものというよりも、型の変換のエラーにかなり時間がかかった。あとC#の二次元配列の要素、[x,y]こんな感じで指定するのね。

今回の問題を機に、nCkについて別記事でまとめようと思う。調べていると問題としては、nCk(mod p)のほうが出題率は高いみたいなので、そっちもまとめたい。(結構理解大変だった)