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

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

AtCoder Beginner Contest 154 D - Dice in Line

無事修論を出しまして一段落、ねむーです。

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

0.はじめに

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

1.問題文

N 個のサイコロが左から右に一列に並べてあります。左から i 番目のサイコロは 1 から p i までの p i 種類の目がそれぞれ等確率で出ます。

隣接する K 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めてください。

2.制約

  • 1 ≤ K ≤ N ≤ 200000
  • 1 ≤ p i ≤ 1000
  • 入力で与えられる値は全て整数

3.入出力例

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

4.初見の感想

  • それぞれのサイコロの期待値は独立に求められる
  • 計算量O(N)で解きたい

5.学びポイント

  • 期待値和がK個になるまで期待値を前から足し合わせる
  • K個を超えたら最初の期待値を減じて、新しい数字を足し合わせる
  • 上の処理で連続するK個の期待値和を計算できる

6.コードと簡単な解説

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

class Program
{
    public static void Main()
    {
        string []input=Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int K = int.Parse(input[1]);
        input = Console.ReadLine().Split();
        int[] p = new int[N];
        double[] avg = new double[N];
        double max = 0;
        double temp = 0;
        for(int i=0; i < N; i++)
        {
            p[i] = int.Parse(input[i]);
            //期待値計算
            avg[i] = (p[i] - 1) * 0.5 + 1;
            if (i >= K) {
                //順に連続期待値和を計算
                temp = temp + avg[i] - avg[i - (K)];
            }
            else
            {
                temp += avg[i];
            }
            if (temp > max) { max = temp; }
        }
        Console.WriteLine(max);
    }
}

7.最後に

最初にKを見逃してて一回WAしました…

AtCoder Beginner Contest 151 C - Welcome to AtCoder

週末にバイキングにいくので楽しみです、ねむーです。

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

0.はじめに

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

1.問題文

高橋君は AtCoder のコンテストに参加しています。

このコンテストでは、 N 問の問題が出題されます。

高橋君はコンテスト中に M 回の提出を行いました。

i 回目の提出は p i 番目の問題への提出であり、結果は S i (AC または WA) でした。

高橋君の正答数は、AC を 1 回以上出した問題の数です。

高橋君のペナルティ数は、高橋君が AC を 1 回以上出した各問題において、初めて AC を出すまでに出した WA の数の総和です。

高橋君の正答数とペナルティ数を答えてください。

2.制約

  • N , M , p i は整数
  • 1 ≤ N ≤ 105
  • 0 ≤ M ≤ 105
  • 1 ≤ p i ≤ N
  • S i は AC か WA のいずれか

3.入出力例

  • 入力
2 5
1 WA
1 AC
2 WA
2 AC
2 WA
  • 出力
2 2

4.初見の感想

  • トータルの問題数でのAC数を出せばよいのでAC数は1変数でOK

5.学びポイント

  • 最終的にACしない問題はWAとカウントされない
  • WAの数は配列で保持しておく
  • その問題がACしたらWA数に加える

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 M = int.Parse(input[1]);
        //ACしたかどうかのflag
        bool []flag=new bool[N];
        //WAの数を配列で保持
        int[] wa_hidden = new int[N];
        for (int i = 0; i < N; i++)
        {
            flag[i] = false;
            wa_hidden[i] = 0;
        }
        int ac = 0;
        int wa = 0;
        for (int i = 0; i < M; i++)
        {
            string[] temp = Console.ReadLine().Split();
            int p = int.Parse(temp[0])-1;
            string S = temp[1];
            if (flag[p] == false && S == "AC") { 
            //ACしたらWAの数を反映する
ac++;flag[p] = true;wa += wa_hidden[p]; }
            if (flag[p] == false && S == "WA") { wa_hidden[p]++; }
        }
        Console.WriteLine(ac+" "+wa);
    }
}

7.最後に

最初WAしたままの問題のWAもカウントしてました…

AtCoder Beginner Contest 151 B - Achieve the Goal

今週は晴れが多くてうれしいです、ねむーです。

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

0.はじめに

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

1.問題文

高橋君は N 科目のテストを受けます。各テストは K 点満点であり、点数はそれぞれ 0 以上の整数です。

高橋君は N − 1 科目のテストを既に受けており、 i 番目の科目のテストの点数は A i 点でした。

高橋君の目標は、 N 科目のテストの平均点を M 点以上にすることです。

高橋君が目標を達成するためには、最後のテストで最低何点取る必要があるか出力してください。

達成不可能である場合は、代わりに -1 を出力してください。

2.制約

  • 2 ≤ N ≤ 100
  • 1 ≤ K ≤ 100
  • 1 ≤ M ≤ K
  • 0 ≤ A i ≤ K
  • 入力中のすべての値は整数である。

3.入出力例

  • 入力
4 100 60
0 0 0
  • 出力
-1

4.初見の感想

  • 取るべき点数と今持ってる点数を比較して行きます
  • 取るべき点数はN×M、持ってる点数はAの配列和で計算します

5.コードと簡単な解説

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]);
        int M = int.Parse(input[2]);
        string[] temp = Console.ReadLine().Split();
        int[] A = new int[N];
        for(int i = 0; i < N-1; i++)
        {
            A[i] = int.Parse(temp[i]);
        }
        int ans = N * M - A.Sum();
        if (ans <= 0) ans = 0;
        else if (ans > K) ans = -1;
        Console.WriteLine(ans);
    }
}

7.最後に

Achieve the Goalって表現かっこいいですよね！

AtCoder Beginner Contest 151 A - Next Alphabet

原付が故障して少しショックです、ねむーです。

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

0.はじめに

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

1.問題文

z でない英小文字 C が与えられます。アルファベット順で C の次の文字を出力してください。

2.制約

C は z でない英小文字

3.入出力例

  • 入力
y
  • 出力
z

4.初見の感想

  • char型は+1で次の文字にできる

5.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        string a = Console.ReadLine();
        char ans = (char)(a[0] + 1);
        Console.WriteLine(ans);
    }
}

7.最後に

最初はzも入力に含まれると思ってました…

AtCoder Beginner Contes 152 A - AC or WA

今年は雪が降らないので少しさみしいです、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc152/tasks/abc152_a)にて開催されました、AtCoder Beginner Contes 152 A問題「A - AC or WA」の問題と僕との戦闘記です。

0.はじめに

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

1.問題文

高橋君は、プログラミングコンテスト AXC001 に参加しており、問題 A にコードを提出しました。 この問題には N 個のテストケースがあり、すべてのテストケースに正解した場合のみ提出は AC となります。 高橋君の提出は、 N 個のテストケースのうち M 個のテストケースに正解しました。 高橋君の提出が AC となるか判定してください。

2.制約

  • 1 ≤ N ≤ 100
  • 0 ≤ M ≤ N
  • 入力はすべて整数である。

3.入出力例

  • 入力
3 3
  • 出力
Yes

4.初見の感想

  • NとMが一致しているかを判定します

    5.コードと簡単な解説

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 M = int.Parse(input[1]);
        if (N == M) { Console.WriteLine("Yes"); }
        else Console.WriteLine("No");
    }
}

7.最後に

問題文の解釈勝負ですね～

AtCoder Beginner Contest 152 B - Comparing Strings

最近紅茶がブームになっています、ねむーです。

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

0.はじめに

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

1.問題文

1 桁の正整数 a , b が与えられます。整数 a を b 回繰り返してできる文字列と 整数 b を a 回繰り返してできる文字列のうち、辞書順で小さい方を答えてください。

2.制約

  • 1 ≤ a ≤ 9
  • 1 ≤ b ≤ 9
  • a , b は整数

3.入出力例

  • 入力
4 3
  • 出力
3333

4.初見の感想

  • 先頭の数字が小さい方が、辞書順は早い
  • ２つの数字の小さい方で数字を作る

5.学びポイント

  • 改行しない文字表示はConsole.Writeでできる

6.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
        int a = int.Parse(input[0]);
        int b = int.Parse(input[1]);
        if (a < b) { for (int i = 0; i < b; i++) { Console.Write(a); } }
        else { for (int i = 0; i < a; i++) { Console.Write(b); } }
    }
}

7.最後に

久しぶりにConsole.Write使いましたね！

AtCoder Beginner Contest 153 C - Fennec vs Monster

久しぶりに晴れている気がします、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc153/tasks/abc153_c)にて開催されました、AtCoder Beginner Contest 153 C問題「C - Fennec vs Monster」の問題と僕との戦闘記です。

0.はじめに

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

1.問題文

フェネックは N 体のモンスターと戦っています。

i 番目のモンスターの体力は H i です。

フェネックは次の 2 種類の行動を行うことができます。

  • 攻撃：モンスターを 1 体選んで攻撃することで、そのモンスターの体力を 1 減らす
  • 必殺技：モンスターを 1 体選んで必殺技を使うことで、そのモンスターの体力を 0 にする

攻撃と必殺技以外の方法でモンスターの体力を減らすことはできません。

全てのモンスターの体力を 0 以下にすればフェネックの勝ちです。

フェネックが K 回まで必殺技を使えるとき、モンスターに勝つまでに行う攻撃の回数 (必殺技は数えません) の最小値を求めてください。

2.制約

  • 1 ≤ N ≤ 2 × 105
  • 0 ≤ K ≤ 2 × 105
  • 1 ≤ H i ≤ 109
  • 入力中のすべての値は整数である

3.入出力例

  • 入力
3 0
1000000000 1000000000 1000000000
  • 出力
3000000000

4.初見の感想

  • HPの大きい敵に必殺技を使いたい
  • HPの昇順にソートして、HPの和をK番目から考える
  • オーバーフローに注意してlong型を使用

5.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    public static void Main()
    {
        string[] input = Console.ReadLine().Split();
        long N = long.Parse(input[0]);
        long K = long.Parse(input[1]);
        long[] H = new long[N];
        input = Console.ReadLine().Split();
        for (long i = 0; i < N; i++)
        {
            H[i] = long.Parse(input[i]);
        }
        Array.Sort(H);
        Array.Reverse(H);
        long ans = 0;
        for(long i = K; i < N; i++)
        {
            ans += H[i];
        }
        Console.WriteLine(ans);
    }
}

6.最後に

実はブログ投稿ツイートのいいねに喜んでいます！