ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

AtCoder Beginner Contest 129 A - Airplane

プログラミングコンテスト

最近夏バテ気味です、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc129)にて開催されました、AtCoder Beginner Contest 129 A問題「A - Airplane」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

空港 A, B, C があり、それぞれの空港の間では、双方向に飛行機が運航しています。

空港 A, B 間の飛行時間は片道 P 時間、空港 B, C 間の飛行時間は片道 Q 時間、空港 C, A 間の飛行時間は片道 R 時間です。

いずれかの空港からスタートして他の空港に飛行機で移動し、さらにそのどちらでもない空港に飛行機で移動するような経路を考えます。

飛行時間の和は最短で何時間になるでしょうか。

2.制約

  • 1 ≤ P , Q , R ≤ 100
  • 入力は全て整数である

3.入力例

  • 入力
3 2 3
  • 出力
5

4.初見の感想

  • 最大経路を通らずに通れば、最短で行ける

5.学びポイント

  • 経路にかかる時間をソート、最大値以外を足す

6.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int[] p = new int[3];
        p[0] = int.Parse(input[0]);
        p[1] = int.Parse(input[1]);
        p[2] = int.Parse(input[2]);
        Array.Sort(p);
        Console.WriteLine(p[0]+p[1]);
    }
}

7.最後に

2分ほどで解けたので満足です！

AtCoder Beginner Contest 133 D - Rain Flows into Dams

プログラミングコンテスト

怒涛の連続更新、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc133/tasks/abc133_d)にて開催されました、AtCoder Beginner Contest 133 D問題「D - Rain Flows into Dams」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

円形に N 個の山が連なっており、時計回りに山 1 , 山 2 , … , 山 N と呼ばれます。 N は奇数です。

これらの山の間に N 個のダムがあり、ダム 1 , ダム 2 , … , ダム N と呼ばれます。ダム i ( 1 ≤ i ≤ N ) は山 i と山 i + 1 の間にあります (山 N + 1 は山 1 のことを指します)。

山 i ( 1 ≤ i ≤ N ) に 2 x リットルの雨が降ると、ダム i − 1 とダム i にそれぞれ x リットルずつ水が溜まります (ダム 0 はダム N のことを指します)。

ある日、各山に非負の偶数リットルの雨が降りました。

その結果、ダム i ( 1 ≤ i ≤ N ) には合計で A i リットルの水が溜まりました。

各山に降った雨の量を求めてください。この問題の制約下では解が一意に定まることが証明できます。

2.制約

  • 入力は全て整数である。
  • 3 ≤ N ≤ 105− 1
  • N は奇数である。
  • 0 ≤ A_i ≤ 109
  • 入力が表す状況は、各山に非負の偶数リットルの雨が降った際に発生しうる。

3.入力例

  • 入力
5
3 8 7 5 5
  • 出力
2 4 12 2 8

4.初見の感想

  • 数式にするとよくわかる(入力をA,B,C,出力をx,y,zという関係で表します)
(x/2)+(y/2)=A
(y/2)+(z/2)=B
(z/2)+(x/2)=C

  • x,y,zのうち一つ判明すれば、あとは芋づる式に導出できる

  • 上の3つの式を全て足すと

x+y+z=A+B+C
  • ここからxを求めるなら,(y/2)+(z/2)=Bを使ってy,zを消す

5.学びポイント

  • 最初のダム以外のすべての和を取得したい

→偶数行目だけ足すと、綺麗に最初のダム以外のすべての和の半分が得られる！

  • 芋づる式に計算できるので、計算量が小さいのが最高

6.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        var input = Console.ReadLine().Split();
        long[] A = new long[N];
        long[] ans = new long[N];
        long sum = 0;
        long halfsum = 0;
        for (int i = 0;i < N; i++)
        {
            //全体和sumと最初のダム以外の数値の和halfsumを取得
            A[i] = long.Parse(input[i]);
            sum += A[i];
            if (i % 2 == 1) { halfsum += 2*A[i]; }
        }
　　　//最初のダムの値を計算
        ans[0] = sum - halfsum;
        for(int i = 0; i < N-1; i++)
        {
　　　//式はダムiとダムi+1の関係式なのでダムi+1がわかる
            ans[i + 1] = 2 * A[i] - ans[i];
        }
　　　//配列出力
        Console.WriteLine(string.Join(" ", ans));
    }
}

7.最後に

対称式はとりあえず足せって、大学受験でよく言われたの思い出しました(^-^;

AtCoder Beginner Contest 133 C - Remainder Minimization 2019

プログラミングコンテスト

初の緑パフォ出せてうれしくなっている、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc133/tasks/abc133_c)にて開催されました、AtCoder Beginner Contest 133 C問題「C - Remainder Minimization 2019」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

非負整数 L , R が与えられます。 2 つの整数 i , j を L ≤ i < j ≤ R を満たすように選びます。 ( i × j ) mod 2019 の最小値を求めてください。

2.制約

  • 入力は全て整数
  • 0 ≤ L < R ≤ 2 × 10 9

3.入力例

  • 入力
2020 2040
  • 出力
2

4.初見の感想

  • (i*j)%2019すればよいのは思いつく
  • 全探索すると計算時間が死ぬ

5.学びポイント

  • 剰余は最大2018までしかない

→数字の取りうる幅は0~2018の間、ループも最初から2019番目以降は計算する価値がない

  • 計算は(i%2019)*(j%2019)でよい

→合同式の性質より、コンテスト中にGoogleで調べました（笑）

6.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        long L = long.Parse(input[0]);
        long R = long.Parse(input[1]);
        long ans = long.MaxValue;
        //2019番目以降をMin条件でカット
        for(long i=L;i<=Math.Min(R,L+2018); i++)
        {
            for(long j = i + 1; j <= Math.Min(R, L + 2018); j++)
            {
　　　　 //最小値更新
                ans=Math.Min(ans,(i%2019)*(j%2019)%2019);
            }
        }
        Console.WriteLine(ans);
    }
}

7.最後に

めっちゃタイプミスしてこの問題3回出しなおしました（笑）

AtCoder Beginner Contest 132 B - Ordinary Number

プログラミングコンテスト

毎日雨でズボンが濡れてしんどいです、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc132/tasks/abc132_b)にて開催されました、AtCoder Beginner Contest 132 B問題「B - Ordinary Number」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

{ 1 , 2 , . . . , n } の順列 p = { p 1 , p 2 , . . . , p n } があります。

以下の条件を満たすような p i ( 1 < i < n ) がいくつあるかを出力してください。

  • p i − 1 , p i , p i + 1 の 3 つの数の中で、 p i が 2 番目に小さい。

2.制約

  • 入力は全て整数である。
  • 3 ≤ n ≤ 20
  • p は { 1 , 2 , . . . , n } の順列である。

3.入力例

  • 入力
9
9 6 3 2 5 8 7 4 1
  • 出力
5

4.初見の感想

  • 真ん中の数字が2番目に小さいとはどういうことか？

→3つの数の中で、[最大、真ん中、最小]or[最小、真ん中、最大]というパターンの2通り。

  • 「最大＞真ん中&&真ん中＞最小」という条件式で判定できる

5.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        //入力
        int N = int.Parse(Console.ReadLine());
        string[] input = Console.ReadLine().Split();
        int[] list = new int[N];
        for(int i = 0; i < N; i++)
        {
            list[i] = int.Parse(input[i]);
        }
　　//条件判定
        int ans = 0;
        for(int i = 0; i < N-2; i++)
        {
            if (list[i] > list[i + 1] && list[i + 1] > list[i + 2]) { ans++; }
            else if(list[i] < list[i + 1] && list[i + 1] < list[i + 2]) { ans++; }
        }
        Console.WriteLine(ans);
    }
}

6.最後に

簡単な問題なので、コードを簡潔に書けるよう工夫したいところです。

AtCoder Beginner Contest 132 C - Divide the Problems

プログラミングコンテスト

最近AtCoderで伸び悩んでいる、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc132/tasks/abc132_c)にて開催されました、AtCoder Beginner Contest 132 C問題「C - Divide the Problems」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

高橋君は、 N 個の競技プログラミング用の問題をつくりました。 それぞれの問題には 1 から N の番号がついており、問題 i の難易度は整数 d i で表されます(大きいほど難しいです)。

高橋君はある整数 K を決めることで、

難易度が K 以上ならば「 A R C 用の問題」 難易度が K 未満ならば「 A B C 用の問題」 という風に、これらの問題を二種類に分類しようとしています。

「 A R C 用の問題」と「 A B C 用の問題」が同じ数になるような整数 K の選び方は何通りあるでしょうか。

2.制約

  • 2 ≦ N ≦ 105
  • N は偶数である。
  • 1 ≦ d i ≦ 105
  • 入力は全て整数である。

3.入力例

  • 入力
14
99592 10342 29105 78532 83018 11639 92015 77204 30914 21912 34519 80835 100000 1
  • 出力
42685

4.初見の感想

  • Kの取り方は「ABC問題の最大値＜K≦ARC用問題の最小値」という条件で表せる

→つまり「ARC用問題の最小値ーABC問題の最大値」でKのとりうる数がわかる

  • とりあえずソートは必要
  • ABC問題の最大値はN/2-1番目の配列、ARCの最小値はN/2番目の配列に格納されている

5.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
　　//入力
        int N = int.Parse(Console.ReadLine());
        string[] input = Console.ReadLine().Split();
        int[] list = new int[N];
        for(int i = 0; i < N; i++)
        {
            list[i] = int.Parse(input[i]);
        }
        //ソート
        Array.Sort(list);
　　//計算&出力
        Console.WriteLine(list[N / 2] - list[N / 2 - 1]);
    }
}

6.最後に

今回はC問題が簡単だったみたいですね～

AtCoder Beginner Contest 132 D - Blue and Red Balls

プログラミングコンテスト

久しぶりの更新です、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc132/tasks/abc132_d)にて開催されました、AtCoder Beginner Contest 132 D問題「D - Blue and Red Balls」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

K 個の青いボールと N − K 個の赤いボールがあります。同じ色のボールは区別が不可能です。すぬけ君と高橋君はこれらのボールで遊んでいます。

まず、すぬけ君が、 N 個のボールを左から右に一列に並べます。

次に、高橋君は、これらのうち K 個の青いボールのみを回収します。高橋君は、 1 回の操作で連続して並ぶ青いボールを何個でも回収することができます。高橋君は、常に K 個の青いボールを回収するのにかかる操作の回数が最小になるように行動します。

K 個の青いボールを回収するために高橋君がちょうど i 回操作をする必要があるボールの並べ方は何通りあるでしょうか。 1 ≤ i ≤ K をみたす i それぞれについて答えを計算し、 109 + 7 で割った余りを答えてください。

2.制約

  • 1 ≤ K ≤ N ≤ 2000

3.入力例

  • 入力
2000 3
  • 出力
1998
3990006
327341989

4.初見の感想

  • 同じものを含む順列の問題ですね～
  • なるほど、(実装)わからん

5.問題の方針

  • 青色のかたまりが何個あるかで分類したい
  • 赤色の球を先に並べておいて、その間に青い球を挿入するという考え方を使う！(これにより挿入箇所の数を固定＝操作回数別に考えられる)
  • 赤色の玉の数はN-K個。つまり挿入箇所は両端も含めてN-K+1個。
  • i個の挿入箇所を選ぶとすると、N-K+1個からi個選べばよい。
  • N個の青玉をi個の挿入箇所にどう入れるのは、N-1個の青玉同士の間の中から区切り棒を入れるi-1か所を選ぶのと同じ
  • つまりN-K+1Ci×K-1Ci-1ってことです。数Aって難しい。

6.実装の方針

  • 幸いN,Kは2000以下なのでパスカルの三角形を使ってコンビネーション(C)の値を事前計算しときます。
  • 定義通り割り算する方法だとオーバーフローなどを考慮する必要が出てきて僕の実力ではやや難しそうです…(特殊な方法はありますが)
  • 1000000007のあまり忘れないでね

7.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        //入力
        string[] input = Console.ReadLine().Split();
        long N = long.Parse(input[0]);
        long K = long.Parse(input[1]);
        long mod = 1000000007;
        long[,] ncr = new long[N+1, K+1];
　　//パスカルの三角形を実行
        for (long i = 0; i < N+1; i++)
        {
            for (long j = 0; j < K+1; j++)
            {
　　　　 //1行目だけ初期化すればあとは自動計算
                if (j == 0) ncr[i, j] = 1;
                else if (i == 0) ncr[i, j] = 0;
                else ncr[i, j] = (ncr[i - 1, j]+ncr[i-1,j-1])%mod;
            }
        }
        for (var i = 1; i <= K; i++)
        {
            long a = ncr[N-K+1,i];
            long b = ncr[K - 1, i - 1];
            Console.WriteLine(a * b % mod);
        }
    }
}

8.最後に

学びが多すぎてびっくり…

diverta 2019 Programming Contest A - Consecutive Integers

プログラミングコンテスト

少し更新が途絶えてしまいましたが復活しました、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/diverta2019)にて開催されました、diverta 2019 Programming Contest A問題「A - Consecutive Integers」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

すぬけ君は 1 , 2 , … , N の N 個の整数を持っています。 すぬけ君はこれらの整数から K 個の整数を選んで高橋君にあげようと考えています。

連続する K 個の整数を選ぶ方法は何通りありますか？

2.制約

  • 入力は全て整数
  • 1 ≤ K ≤ N ≤ 50

3.入力例

  • 入力
13 3
  • 出力
11

4.初見の感想

  • 最後尾がNなので連続するK個の数字を選ぼうとすると、最後尾をNとした時の先頭はN-K
  • 連続する数字の先頭は1~N-kまでのN-k+1通り考えられる

5.学びポイント

  • N-K+1は場合の数なので、０以下にならないよう注意する

6.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
//入力のパース
        string[] input = Console.ReadLine().Split(' ');
        int N = int.Parse(input[0]);
        int K = int.Parse(input[1]);
//N-K+1を計算
        if (N - K + 1 >= 0) { Console.WriteLine(N - K + 1); }
        else { Console.WriteLine(0); }
    }
}

7.最後に

これからも自分のペースでがんばります(^-^;