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

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

【プログラミングコンテスト】AtCoder記事まとめ

久しぶりに今週末は予定のない終末なのでAtCoderに全力注げそうな、ねむーです。

今回はいつもと趣向を変えて、今まで作成したAtCoder問題との記事のまとめを作成しました!

空欄はまだ解いてない問題ですので、更新を気長にお待ちください(^-^;

令和AtCoderの解答記事一覧

コンテスト A問題 B問題 C問題 D問題 E問題 F問題
ABC153 A - Serval vs Monster B - Common Raccoon vs Monster C - Fennec vs Monster D - Caracal vs Monster E - Crested Ibis vs Monster
ABC152 C - Low Elements D - Handstand 2
ABC150 A - 500 Yen Coins B - Count ABC C - Count Order
ABC147 A - Blackjack B - Palindrome-philia C - Honest Or Unkind2 D - Xor Sum 4
ABC146 A - Can't Wait for Holiday B - ROT N C - Buy an Integer
ABC145 A - Circle B - Echo C - Average Length
ABC138 A - Red or Not B - Resistors in Parallel
ABC137 C - Green Bin
ABC136 D - Gathering Children
ABC135 A - Harmony
ABC133 A - T or T C - Remainder Minimization 2019 D - Rain Flows into Dams
ABC132 B - Ordinary Number C - Divide the Problems D - Blue and Red Balls
ABC129 A - Airplane B - Balance
ABC128 A - Apple Pie
ABC127 A - Ferris Wheel
ABC126 C - Dice and Coin

ABC以外のコンテスト

コンテスト A問題 B問題 C問題 D問題
三井住友信託銀行プログラミングコンテスト A - November 30 B - Tax Rate C - 100 to 105
第二回全国統一プログラミング王決定戦 A - Sum of Two Integers
diverta 2019 Programming Contest A - Consecutive Integers

平成AtCoderの解答記事一覧

コンテスト A問題 B問題 C問題 D問題
Tenka1 Programmer Beginner Contest 2019 A - On the Way B - e e *ee *e C - Stones
ABC124 A - Buttons B - Great Ocean View C - Coloring Colorfully D - Handstand
ABC123 A - Five Antennas B - Five Dishes C - Five Transportations
エクサウィザーズ2019 A - Regular Triangle B - Red or Blue
ABC122 A-Double Helix B - ATCoder C - GeT AC
早稲田大学プロコン2019 A - WAsedAC B - 10 puzzle
ABC121 C - Energy Drink Collector
ABC120 A - Favorite Sound B - K-th Common Divisor C - Unification
ABC119 A - Still TBD B - Digital Gifts C - Synthetic Kadomatsu
ABC118 A - B +/- A C - Monsters Battle Royale
ABC117 A - Entrance Examination B - Polygon C - Streamline
全国統一プログラミング王決定戦 A - Subscribers B - Touitsu C - Different Strokes
ABC116 C - Grand Garden
ABC115 C - Christmas Eve
ABC114 C - 755
ABC113 C - ID
ABC112 C - Pyramid

最後に

この記事はブログのトップに固定しておくので、復習や問題探しなどにご活用ください!

リンクミス等あれば、コメントにて指摘してもらえると助かります(^^)

AtCoder Beginner Contest 186 A - Brick

朝布団から出られない季節ですね、ねむーです。

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

0.はじめに

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

1.問題文

トラックが 1 台あります。このトラックには合計で N キログラム以下の荷物を載せることができます。

このトラックに、 1 個 W キログラムのレンガを最大でいくつ載せることができますか?

2.制約

  • 1 ≤ N , W ≤ 1000
  • N , W は整数である。

3.入出力例

  • 入力
10 3
  • 出力
3

4.初見の感想

  • 割り算を行って最大数を求める

    5.学びポイント

  • intの割り算は余りが出ないので最大値が出せる

    6.コードと簡単な解説

using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            String[] input = Console.ReadLine().Split();
            int N = int.Parse(input[0]);
            int W = int.Parse(input[1]);
            Console.WriteLine(N / W);
        }
    }
}

7.最後に

良いペースで更新できてますね。

AtCoder Beginner Contest 188 C - ABC Tournament

今日は帰りにたい焼きを買っちゃいました、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc188/tasks/abc188_c)にて開催されました、AtCoder Beginner Contest 188 C問題「C - ABC Tournament」の問題と僕との戦闘記です。

0.はじめに

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

1.問題文

選手 1 から選手 2N までの 2N 人の選手がトーナメント形式のプログラミング対決をします。 選手 i のレートは A i です。どの 2 人の選手のレートも異なり、 2 人の選手が対戦すると常にレートが高い方が勝ちます。

トーナメント表は完全二分木の形をしています。 より正確には、このトーナメントは以下の要領で行われます。

i= 1 , 2 , 3 , … , N について順に、以下のことが行われる。

各整数 j ( 1 ≤ j ≤ 2N−i ) について、まだ負けたことのない選手のうち、 2 j − 1 番目に番号の小さい選手と 2 j 番目に番号の小さい選手が対戦する。 準優勝する、すなわち最後に行われる対戦において負ける選手の番号を求めてください。

2.制約

  • 1 ≤ N ≤ 16
  • 1 ≤ A i ≤ 109
  • A i は相異なる
  • 入力に含まれる値は全て整数である

3.入出力例

  • 入力
4
6 13 12 5 3 7 10 11 16 9 8 15 2 1 14 4
  • 出力
2

4.初見の感想

  • 勝負を一つ一つ計算していると計算量が大きすぎる

5.学びポイント

  • 試合の方法はきまっているので、1~2N-1番までのトーナメントの勝者と2N-1+1~2N番目の勝者が決勝を行う
  • 1~2N-1番までの数の最大値と2N-1+1~2N番目の数の最大値を比較すると準優勝がわかる

6.コードと簡単な解説

using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            String[] input = Console.ReadLine().Split();
            long max = (long)Math.Pow(2, N);
            long[] A = new long[max];
            for (long i = 0; i < max; i++)
            {
                A[i] = long.Parse(input[i]);
            }
            long max_left = 0;
            long max_left_point = 0;
            for (long i = 0; i < (max / 2); i++)
            {
                if (A[i] > max_left) { max_left = A[i]; max_left_point = i+1; }
            }
            long max_right = 0;
            long max_right_point = 0;
            for (long i = (max / 2); i < max; i++)
            {
                if (A[i] > max_right) { max_right = A[i]; max_right_point = i + 1; }
            }
            if (max_left < max_right) { Console.WriteLine(max_left_point); }
            else { Console.WriteLine(max_right_point); }
        }
    }
}

7.最後に

すこし発想に時がかかってしまったので精進します

AtCoder Beginner Contest 188 B - Orthogonality

在宅勤務だと刺激のない日々ですね、ねむーです。

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

0.はじめに

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

1.問題文

2 つの N 次元ベクトル A= ( A 1 , A 2 , A 3 , … , A N ) , B= ( B 1 , B 2 , B 3 , … , B N ) が与えられます。 A と B の内積が 0 かどうかを判定してください。 すなわち、 A 1 B 1 + A 2 B 2 + A 3 B 3 + ⋯ + A N B N= 0 かどうかを判定してください。

2.制約

  • 1 ≤ N ≤ 100000
  • − 100 ≤ A i ≤ 100
  • − 100 ≤ B i ≤ 100
  • 入力に含まれる値は全て整数である

3.入出力例

  • 入力
3
1 3 5
3 -6 3
  • 出力
Yes

4.初見の感想

  • ループで内積を計算する

5.学びポイント

  • 特になし

6.コードと簡単な解説

using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            String[] input_A = Console.ReadLine().Split();
            String[] input_B = Console.ReadLine().Split();
            int ans = 0;
            for(int i = 0; i < N; i++)
            {
                ans += int.Parse(input_A[i]) * int.Parse(input_B[i]);
            }
            if (ans == 0)
            {
                Console.WriteLine("Yes");
            }
            else { Console.WriteLine("No"); }
        }
    }
}

7.最後に

シンプルに解けて良かったです。

AtCoder Beginner Contest 188 A - Three-Point Shot

連休明けはついだらけてしまいますね、ねむーです。

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

0.はじめに

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

1.問題文

バスケットボールの試合が行われており、現在の両チームの得点は X 対 Y です。ここで X≠ Y であることが保証されます。 現在劣勢であるチームが、 3 ポイントシュートを一本成功させて優勢に立つことはできますか? つまり、現在得点が低い側のチームが 3 点を得た場合、そのチームの得点が他方のチームの得点より真に高くなるかを判定してください。

2.制約

  • 0 ≤ X ≤ 100
  • 0 ≤ Y ≤ 100
  • X≠ Y
  • X , Y は整数である

3.入出力例

  • 入力
12 15
  • 出力
No

4.初見の感想

  • 差が3点差以下なら逆転可能
  • 差は2数の絶対値で計算できる

    5.学びポイント

  • 特になし

    6.コードと簡単な解説

using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            String[] input = Console.ReadLine().Split();
            int X = int.Parse(input[0]);
            int Y = int.Parse(input[1]);
            if (Math.Abs(X - Y) <= 2) { Console.WriteLine("Yes"); }
            else { Console.WriteLine("No"); }
        }
    }
}

7.最後に

ブログ更新ペースを取り戻していきたい。。。

AtCoder Beginner Contest 187 D - Choose Me

今日は仕事帰りにたい焼きを食べちゃいました、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc187/tasks/abc187_d)にて開催されました、AtCoder Beginner Contest 187 D問題「D - Choose Me」の問題と僕との戦闘記です。

0.はじめに

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

1.問題文

AtCoder 市で市長選挙が行われます。候補者は青木氏と高橋氏です。 市には N 個の町があり、 i 番目の町には青木派の有権者が A i 人、高橋派の有権者が B i 人います。他に有権者はいません。 高橋氏は、それぞれの町で演説を行うことができます。 高橋氏がある町で演説を行った場合、その町の高橋派も青木派も全員高橋氏に投票します。 一方、高橋氏がある町で演説を行わなかった場合、その町の青木派は全員青木氏に投票し、高橋派は投票に行きません。 高橋氏が青木氏より多く票を獲得するためには、最小でいくつの町で演説をする必要があるでしょうか?

2.制約

  • 入力は全て整数
  • 1 ≤ N ≤ 2 × 105
  • 1 ≤ A i , B i ≤ 109

3.入出力例

  • 入力
4
2 1
2 2
5 1
1 3
  • 出力
1

3 番目の町で演説を行うと、青木氏が 5 票、高橋氏が 6 票を得ます。

4.初見の感想

  • 最も効率よく演説したい
  • 効率は演説したときの票の増減差である、2*A+Bで計算できる

    5.学びポイント

  • どの街を回ったかは関係なく、演説した街の数だけ出せばよい
  • ソートして演説でついた増減差が青木派の数を超えればよい

    6.コードと簡単な解説

using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            long[,] A = new long[N,2];
            long[] B =new long[N];
            long sum=0;
            for(int i=0;i<N;i++){
                String[] input = Console.ReadLine().Split(' ');
                A[i,0]=long.Parse(input[0]);
                A[i,1]=long.Parse(input[1]);
                B[i]=A[i,0]*2+A[i,1];
                sum+=A[i,0];
            }
            Array.Sort(B);
            long ans=0;
            for(int i=N-1;i>=0;i--){
                sum -= B[i];
                ans++;
                if(sum<0){break;}
            }
            Console.WriteLine(ans);
        }
    }
}

7.最後に

何を基準に選ぶのかという視点を常に持ちたいですね。

AtCoder Beginner Contest 187 C - 1-SAT

最近こたつでよく寝落ちをしてしまいます、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc187/tasks/abc187_c)にて開催されました、AtCoder Beginner Contest 187 C問題「C - 1-SAT」の問題と僕との戦闘記です。

0.はじめに

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

1.問題文

N 個の文字列 S 1 , S 2 , … , S N が与えられます。 各文字列は、英小文字からなる空でない文字列の先頭に ! を 0 文字か 1 文字付加したものです。 文字列 T は、 T の先頭に ! を 0 文字付加しても 1 文字付加しても S 1 , S 2 , … , S N のいずれかに一致するとき、不満な文字列であるといいます。 不満な文字列があるかどうか判定し、あれば 1 つ示してください。

2.制約

  • 1≤N≤2×105
  • 1≤|Si|≤10
  • Siは英小文字からなる空でない文字列の先頭に ! を 0文字か 1文字付加したものである。

3.入出力例

  • 入力
6
a
!a
b
!c
d
!d
  • 出力
a

文字列 a は、先頭に ! を 0 文字付加する場合は S 1 と、 1 文字付加する場合は S 2 と一致するため不満な文字列です。 a の他に、d を出力しても正解になります。

4.初見の感想

  • 単純にループを回して各要素を比較する解法でも解けそう

5.学びポイント

  • HashSetを利用するとContainsで存在するかを確認できるから便利です

6.コードと簡単な解説

using System;
using System.Collections.Generic;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            HashSet<String> hs = new HashSet<String>();
            for(int i=0;i<N;i++){
                hs.Add(Console.ReadLine());
            }
            foreach(var x in hs){
                if(hs.Contains("!"+x)){Console.WriteLine(x);return;}
            }
          Console.WriteLine("satisfiable");
        }
    }
}

7.最後に

HashSetの使い方を復習できたのでよかったです!

AtCoder Beginner Contest 187 B - Gentle Pairs

仕事が始まってしまいました、ねむーです。

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

0.はじめに

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

1.問題文

x y 平面上に 1 , 2 , … , N の番号が付けられた N 個の点があります。点 i は ( x i , y i ) にあり、 N 個の点の x 座標は互いに異なります。

以下の条件を満たす整数の組 ( i , j )

( i < j ) の個数を求めてください。

点 i と点 j を通る直線の傾きが − 1 以上 1 以下である。

2.制約

  • 入力は全て整数
  • 1≤N≤103
  • |x_i| ,|y_i|≤ 103
  • i≠jならば x_i≠x_j

3.入出力例

  • 入力
3
0 0
1 2
2 1
  • 出力
2

4.初見の感想

  • 傾きは2点を選ぶと一意に決まる

5.学びポイント

  • 傾き(y/x)が1以下かを判定するより、Y<Xを判定した方が早い

6.コードと簡単な解説

using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] x= new int[N];
            int[] y= new int[N];
            for(int i=0;i<N;i++){
                String[] input = Console.ReadLine().Split(' ');
                x[i]=int.Parse(input[0]);
                y[i]=int.Parse(input[1]);
            }
            int ans=0;
            for(int i=0;i<N;i++){
                for(int j=i+1;j<N;j++){
                    if(Math.Abs(y[i]-y[j])<=Math.Abs(x[i]-x[j])){ans++;}
                }
            }
            Console.WriteLine(ans);
        }
    }
}

7.最後に

割り算はできるだけ避ける方向でいきたいですね。