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

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

AtCoder Beginner Contest 124 A - Buttons

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

昨日はTOEICを受けてきて長文アレルギーを再認識しました、ねむーです。

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

0.はじめに

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

1.問題文

2 個のボタンがあり、大きさはそれぞれ A , B です。

大きさ X のボタンを押すと、 X 枚のコインを獲得し、そのボタンの大きさが 1 小さくなります。

あなたは、いずれかのボタンを押すことを 2 回行います。 同じボタンを 2 回押しても構いません。

最大で何枚のコインを獲得できるでしょうか。

2.制約

  • 入力は全て整数である。
  • 3 ≤ A , B ≤ 20

3.入力例

  • 入力
6 6
  • 出力
12

4.初見の感想

  • 基本的には大きいボタンを連続で押しておけばよさそう(1しか減らないので)
  • 両方同じ高さの時は両方を押した方がよさそう

5.学びポイント

  • 僕はifで条件分岐しましたが、Max関数を使う方法もあるようですね！

6.コードの簡単な解説

  • まず、入力の値のパースを行う
        string[] input = Console.ReadLine().Split(' ');
        int[] button = new int[2];
        button[0] = int.Parse(input[0]);
        button[1] = int.Parse(input[1]);
  • ボタン1が大きい時はボタン1を連続で押す
        if (button[1]>button[0]) { Console.WriteLine(2*button[1]-1); }
  • ボタンが同じ高さなら両方押す
        else if(button[1] == button[0]) { Console.WriteLine(2 * button[1]); }
  • ボタン0が大きい時はボタン0を連続で押す
        else { Console.WriteLine(2 * button[0] - 1); }

7.全コード

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

class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int[] button = new int[2];
        button[0] = int.Parse(input[0]);
        button[1] = int.Parse(input[1]);
        if (button[1]>button[0]) { Console.WriteLine(2*button[1]-1); }
        else if(button[1] == button[0]) { Console.WriteLine(2 * button[1]); }
        else { Console.WriteLine(2 * button[0] - 1); }
    }
}

8.最後に

この問題は2:50で解けたので上出来かな？と思ってます

AtCoder Beginner Contest 124 D - Handstand

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

初めてD問題を解いてみます、ねむーです。

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

0.はじめに

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

1.問題文

N 人の人が左右一列に並んでいます。

0, 1 からなる長さ N の文字列 S と正整数 K が与えられます。

左から i 番目の人は、 S の i 文字目が 0 のとき直立し、1 のとき逆立ちしています。

あなたは K 回まで以下の指示を行います。一度も行わなくても構いません。

指示: 1 ≤ l ≤ r ≤ N を満たす整数 l , r を選ぶ。左から l , l + 1 , . . . , r 番目の人の状態を反転する。すなわち、 i= l , l + 1 , . . . , r について、左から i 番目の人は直立していれば逆立ちし、逆立ちしていれば直立する。

K 回までの指示で、逆立ちした人を連続で最大何人並ばせることができるか求めてください。

2.制約

  • N は 1 ≤ N ≤ 105 を満たす整数である。

  • K は 1 ≤ K ≤ 105 を満たす整数である。

  • 文字列 S の長さは N である。

  • 文字列 S の各文字は 0 または 1 である。

3.入力例

  • 入力
14 2
11101010110011
  • 出力
8

4.初見の感想

  • 入れ替える範囲を選ぶ基準となるものが、「入れ替え範囲の長さ+入れ替え範囲の左右の1のみからなる文字列の長さ」と複雑
  • 全探索的な手法が有効そう、しかし計算量が爆発してしまう
  • 文字列の真ん中の方を入れ替える方が効率的、なぜなら範囲の両端も長さに含めることができるから

→「0が連なる塊」をK個だけ含む大きな区間で考えられる

5.学びポイント

  • 左端と右端が移動する場合なので、累積和の考え方が使えそう
  • 他にも「尺取り法」で実装するパターンや、真ん中が効率的なことから中央から2部探索とかも別解としてあるようです

6.コードの簡単な解説

  • まず、入力の値のパースを行う
        string[] line = Console.ReadLine().Split(' ');
        int N = int.Parse(line[0]);
        int K = int.Parse(line[1]);
        char[] input = Console.ReadLine().ToArray();
  • 0から1に切り替わる点を保存するリストなどを準備
        List<int> list = new List<int>();
        int now = 1;
        int ct = 0;
        list.Add(0);
        int ans = 0;
  • １から０に切り替わる瞬間ではK個入れ替えた時の区間の長さを計算します
        for(int i = 0; i < N; i++)
        {
            if (now == 1 && input[i] == '0')
            {
                now = 0;
                if (ct - K >= 0) { ans = Math.Max(ans, i - list[ct - K]); }
            }
  • 1から0に切り替わる瞬間ではリストに区間の始点として保存
            else if (now == 0 && input[i] == '1')
            {
                now = 1;
                list.Add(i);
                ct++;
            }
        }
  • 文字列が全て1の時、文字列が全て0の時、K=0の時、これらは切り替え点がないので例外処理
        if (now == 1)
        {
            if ((ct - K) >= 0) { ans=Math.Max(ans,N-1-list[ct-K]+1); }
            else { ans = N; }
        }
        else if ((ct - K + 1) >= 0)
        {
            ans = Math.Max(ans, N - 1 - list[ct - K+1] + 1);
        }
        else
        {
            ans = N;
        }
        Console.WriteLine(ans);
    }
}

7.全コード

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

class Program
{
    static void Main(string[] args)
    {
        string[] line = Console.ReadLine().Split(' ');
        int N = int.Parse(line[0]);
        int K = int.Parse(line[1]);
        char[] input = Console.ReadLine().ToArray();
        List<int> list = new List<int>();
        int now = 1;
        int ct = 0;
        list.Add(0);
        int ans = 0;
        for(int i = 0; i < N; i++)
        {
            if (now == 1 && input[i] == '0')
            {
                now = 0;
                if (ct - K >= 0) { ans = Math.Max(ans, i - list[ct - K]); }
            }
            else if (now == 0 && input[i] == '1')
            {
                now = 1;
                list.Add(i);
                ct++;
            }
        }
        if (now == 1)
        {
            if ((ct - K) >= 0) { ans=Math.Max(ans,N-1-list[ct-K]+1); }
            else { ans = N; }
        }
        else if ((ct - K + 1) >= 0)
        {
            ans = Math.Max(ans, N - 1 - list[ct - K+1] + 1);
        }
        else
        {
            ans = N;
        }
        Console.WriteLine(ans);
    }
}

8.最後に

他の解法もできればやってみたいですね！

AtCoder Beginner Contest 124 C - Coloring Colorfully

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

今回のABC124は自己ベストのパフォーマンス949が出せてご満悦のねむーです。

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

0.はじめに

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

1.問題文

左右一列に N 枚のタイルが並んでおり、各タイルの初めの色は長さ N の文字列 S で表されます。

左から i 番目のタイルは、 S の i 番目の文字が 0 のとき黒色で、1 のとき白色で塗られています。

あなたは、いくつかのタイルを黒色または白色に塗り替えることで、どの隣り合う 2 枚のタイルも異なる色で塗られているようにしたいです。

最小で何枚のタイルを塗り替えることで条件を満たすようにできるでしょうか。

2.制約

  • 1 ≤ | S | ≤ 105
  • S i は 0 または 1 である。

3.入力例

  • 入力
10010010
  • 出力
3

4.初見の感想

  • 制約が105なので、入れ替える場所をすべて試す全探索的な考え方は無理そう
  • 最終的な変更結果となる白黒の並びは「奇数番目が白、偶数番目が黒」もしくは「奇数番目が黒、偶数番目が白」の2パターンしかない
  • 上の2パターンと入力の差を考えればよいのでは？

5.コードの簡単な解説

  • まず、入力を配列に保存します
        char[] input = Console.ReadLine().ToArray();
  • 奇数番目が黒、偶数番目が白のパターンとの誤差をカウント
        int count = 0;
        for (int i = 0; i < input.Count(); i++)
        {
            if (i % 2 == 0 && input[i] == '0')
            {
                count++;
            }
            else if(i % 2 == 1 && input[i] == '1') { count++; }
        }
  • 同様に奇数番目が白、偶数番目が黒のパターンも行う
        int count_another = 0;
        for (int i = 0; i < input.Count(); i++)
        {
            if (i % 2 == 0 && input[i] == '1')
            {
                count_another++;
            }
            else if (i % 2 == 1 && input[i] == '0') { count_another++; }
        }
  • 結果が少ない方を出力
        if (count > count_another) { Console.WriteLine(count1); }
        else { Console.WriteLine(count); }

6.全コード

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

class Program
{
    static void Main(string[] args)
    {
        char[] input = Console.ReadLine().ToArray();
        int count = 0;
        for (int i = 0; i < input.Count(); i++)
        {
            if (i % 2 == 0 && input[i] == '0')
            {
                count++;
            }
            else if(i % 2 == 1 && input[i] == '1') { count++; }
        }
        int count_another = 0;
        for (int i = 0; i < input.Count(); i++)
        {
            if (i % 2 == 0 && input[i] == '1')
            {
                count_another++;
            }
            else if (i % 2 == 1 && input[i] == '0') { count_another++; }
        }
        if (count > count_another) { Console.WriteLine(count1); }
        else { Console.WriteLine(count); }
    }
}

7.最後にご報告

遂にAtCoder茶色になりました！

これからもレート更新できるようがんばります！

f:id:nemurin_blog:20190413235126p:plain

AtCoder Beginner Contest 123 C - Five Transportations

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

研究室の後輩のPCの環境構築で一日終わってしまいました、ねむーです。

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

0.はじめに

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

1.問題文

AtCoder 社は成長し、2028 年になってついに 6 つの都市 (都市 1 , 2 , 3 , 4 , 5 , 6 ) からなる AtCoder 帝国を作りました！

AtCoder 帝国には 5 つの交通機関があります。

  • 電車：都市 1 から 2 まで 1 分で移動する。 1 つの電車には A 人まで乗ることができる。
  • バス：都市 2 から 3 まで 1 分で移動する。 1 つのバスには B 人まで乗ることができる。
  • タクシー：都市 3 から 4 まで 1 分で移動する。 1 つのタクシーには C 人まで乗ることができる。
  • 飛行機：都市 4 から 5 まで 1 分で移動する。 1 つの飛行機には D 人まで乗ることができる。
  • 船：都市 5 から 6 までを 1 分で移動する。 1 つの船には E 人まで乗ることができる。

それぞれの交通機関は、各整数時刻 ( 0 , 1 , 2 , 3 , . . . ) に、都市から出発します。 いま、 N 人のグループが都市 1 におり、全員都市 6 まで移動したいです。全員が都市 6 に到着するまでに最短で何分かかるでしょうか？ なお、乗り継ぎにかかる時間を考える必要はありません

2.制約

  • 1 ≤ N , A , B , C , D , E ≤ 1015
  • 入力中の値はすべて整数である。

3.入力例

  • 入力
10000000007
2
3
5
7
11
  • 出力
5000000008

4.初見の感想

→総移動人数÷最も運搬人数の少ない場所の移動人数で大まかな時間が分かる

→上の割り算で余りがある場合は切り上げの必要がある( 最後の一人を通す回数が必要なため)

  • 型に注意する必要がある

→解答はO(1016)になる可能性があるのでlong型を使う必要があります！(これを見落としていて一回WAになりました…)

5.コードの簡単な解説

        string input = Console.ReadLine();
        long n = long.Parse(input);
        long[] capacity = new long[5];
        input = Console.ReadLine();
        capacity[0] = long.Parse(input);
        input = Console.ReadLine();
        capacity[1] = long.Parse(input);
        input = Console.ReadLine();
        capacity[2] = long.Parse(input);
        input = Console.ReadLine();
        capacity[3] = long.Parse(input);
        input = Console.ReadLine();
        capacity[4] = long.Parse(input);
        Array.Sort(capacity);
        if (n <= capacity[0]) { Console.WriteLine("5"); }
        else { if (n % capacity[0] != 0) { Console.WriteLine(5 + ((n-n % capacity[0]) / capacity[0])); }
        else { Console.WriteLine(4 + (n / capacity[0])); }

6.全コード

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

class Program
{
    static void Main(string[] args)
    {
        string input = Console.ReadLine();
        long n = long.Parse(input);
        long[] capacity = new long[5];
        input = Console.ReadLine();
        capacity[0] = long.Parse(input);
        input = Console.ReadLine();
        capacity[1] = long.Parse(input);
        input = Console.ReadLine();
        capacity[2] = long.Parse(input);
        input = Console.ReadLine();
        capacity[3] = long.Parse(input);
        input = Console.ReadLine();
        capacity[4] = long.Parse(input);
        Array.Sort(capacity);
        if (n <= capacity[0]) { Console.WriteLine("5"); }
        else { if (n % capacity[0] != 0) { Console.WriteLine(5 + ((n-n % capacity[0]) / capacity[0])); }
        else { Console.WriteLine(4 + (n / capacity[0])); }
        }
    }
}

7.最後に

初めてコンテスト出場時間内にC問題が解けたので幸せです(^^)

AtCoder Beginner Contest 123 B - Five Dishes

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

研究室のレイアウト変更で腕が筋肉痛、ねむーです。

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

0.はじめに

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

1.問題文

AtCoder 料理店では、以下の 5 つの料理が提供されています。ここで、「調理時間」は料理を注文してから客に届くまでの時間とします。

  • ABC 丼： 調理時間 A 分
  • ARC カレー： 調理時間 B 分
  • AGC パスタ： 調理時間 C 分
  • APC ラーメン： 調理時間 D 分
  • ATC ハンバーグ： 調理時間 E 分

また、この店には以下のような「注文のルール」があります。

  • 注文は、 10 の倍数の時刻 (時刻 0 , 10 , 20 , 30 , . . . ) にしかできない。
  • 一回の注文につき一つの料理しか注文できない。
  • ある料理を注文したら、それが届くまで別の注文ができない。ただし、料理が届いたちょうどの時刻には注文ができる。

E869120 君は時刻 0 に料理店に着きました。彼は 5 つの料理全てを注文します。最後の料理が届く最も早い時刻を求めてください。 ただし、料理を注文する順番は自由であり、時刻 0 に注文することも可能とであるとします。

最後の料理が届く最も早い時刻を整数で出力せよ。

2.入力例

  • 入力
101
86
119
108
57
  • 出力
481

3.初見の感想

  • 最も時間ロスが大きい注文は最後に注文することで時間が節約できる

→時間のロスは(10-(調理時間の1の位の値))で計算できる

  • 最後の注文以外の注文時間は1の位繰り上げの値となる

4.コードの簡単な解説

  • 入力の値のパースを行い、時間ロス計算と1の位切り上げを行う
        int min = 10;
        string input = Console.ReadLine();
        int a = int.Parse(input);
        if (a % 10 != 0 && a % 10 < min) { min = a % 10; }
        if (a % 10 != 0) { a += (10 - (a % 10)); }
  • 最後の注文の切り上げ分を最終結果からマイナスしておく
        Console.WriteLine(a+b+c+d+e+min-10);

5.全コード

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

class Program
{
    static void Main(string[] args)
    {
        int min = 10;
        string input = Console.ReadLine();
        int a = int.Parse(input);
        if (a % 10 != 0 && a % 10 < min) { min = a % 10; }
        if (a % 10 != 0) { a += (10 - (a % 10)); }
        input = Console.ReadLine();
        int b = int.Parse(input);
        if (b % 10 != 0 && b % 10 < min) { min = b % 10; }
        if (b % 10 != 0) { b += (10 - (b % 10)); }
        input = Console.ReadLine();
        int c = int.Parse(input);
        if (c % 10 != 0 && c % 10 < min) { min = c % 10; }
        if (c % 10 != 0) { c += (10 - (c % 10)); }
        input = Console.ReadLine();
        int d = int.Parse(input);
        if (d % 10 != 0 && d % 10 < min) { min = d % 10; }
        if (d % 10 != 0) { d += (10 - (d % 10)); }
        input = Console.ReadLine();
        int e = int.Parse(input);
        if (e % 10 != 0 && e % 10 < min) { min = e % 10; }
        if (e % 10 != 0) { e += (10 - (e % 10)); }
        Console.WriteLine(a+b+c+d+e+min-10);
    }
}

6.最後に

全探索するような手法もあるみたいですね…

本番中にこの手法を思いついてよかったです！

【プログラミングコンテスト】AtCoder Beginner Contest 123①

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

今日は選挙に行ってきました、ねむーです。

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

0.はじめに

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

1.問題文

AtCoder 市には、 5 つのアンテナが一直線上に並んでいます。これらは、西から順にアンテナ A , B , C , D , E と名付けられており、それぞれの座標は a , b , c , d , e です。 2 つのアンテナ間の距離が k 以下であれば直接通信ができ、 k より大きいと直接通信ができません。 さて、直接 通信ができないアンテナの組が存在するかどうか判定してください。 ただし、座標 p と座標 q ( p < q ) のアンテナ間の距離は q − p であるとします

2.制約

  • a , b , c , d , e , k は 0 以上 123 以下の整数
  • a < b < c < d < e

3.入力例

  • 入力
1
2
4
8
9
15
  • 出力
Yay!
  • 入力
15
18
26
35
36
18
  • 出力
:(

4.初見の感想

  • 条件判定で解けそうです

5.学びポイント

  • 「5つの数字から2つ選んだ時の差が全てk以下」

→素直に実装すると10条件になる

→a<b<c<d<eの条件を使ってa-eだけ考えましょうね(本番は気づかなかった)

  • 「以上」ですのでイコールを含みます！(本番の時見逃してWA出しました)

6.全コード

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

class Program
{
    static void Main(string[] args)
    {
        string input = Console.ReadLine();
        int a = int.Parse(input);
        input = Console.ReadLine();
        int b = int.Parse(input);
        input = Console.ReadLine();
        int c = int.Parse(input);
        input = Console.ReadLine();
        int d = int.Parse(input);
        input = Console.ReadLine();
        int e = int.Parse(input);
        input = Console.ReadLine();
        int k = int.Parse(input);
        if (Math.Abs(a - e) <= k) { Console.WriteLine("Yay!"); }
        else { Console.WriteLine(":("); }
    }
}

7.最後に

問題文はしっかり読みましょう!(めっちゃ反省してます)

【プログラミングコンテスト】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

最後に

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

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