2020-01-28

AtCoder Beginner Contest 153 D - Caracal vs Monster

最近Official髭男dismにハマってます、ねむーです。

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

0.はじめに

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

1.問題文

カラカルはモンスターと戦っています。

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

カラカルはモンスターを 1 体選んで攻撃することができます。モンスターを攻撃したとき、攻撃対象のモンスターの体力に応じて、次のどちらかが起こります。

モンスターの体力が 1 なら、そのモンスターの体力は 0 になる
モンスターの体力が X>1 なら、そのモンスターは消滅し、体力が ⌊ X / 2 ⌋ のモンスターが新たに 2 体現れる（ ⌊ r ⌋ は r を超えない最大の整数を表す）

全てのモンスターの体力を 0 以下にすればカラカルの勝ちです。

カラカルがモンスターに勝つまでに行う攻撃の回数の最小値を求めてください。

2.制約

1 ≤ H ≤ 10¹²
入力中のすべての値は整数である。

3.入力例

入力

1000000000000

出力

1099511627775

4.初見の感想

体力が２以上ある敵をすべて分裂させ体力１にした後、全部倒していく戦略をとることになる
体力1になるまでループなのでwhile文で回す
今何体いるかをnumで数えときます
num体全員に魔法を打つのでその回数を変数ansでcountします

5.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    public static void Main()
    {
        long H = long.Parse(Console.ReadLine());
        long num = 1;
        long ans = 0;
        while (H >= 2)
        {
            H = H / 2;
           //分裂する前に魔法をうつ回数を数える
            ans+=num;
           //２倍にモンスター数が分裂
            num *= 2;
        }
        //体力1の軍団を倒す魔法の回数を計測
        ans += num;
        Console.WriteLine(ans);
    }
}

6.最後に

本番中は意外と手間取ったんですが、この問題灰パフォなんですね…

2020-01-27

AtCoder Beginner Contest 150 A - 500 Yen Coins

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

雨模様が続いてますね、ねむーです。

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

0.はじめに

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

1.問題文

高橋君は 500 円玉を K 枚持っています。これらの総額が X 円以上である場合は Yes を、そうでない場合は No を出力してください。

2.制約

1 ≤ K ≤ 100
1 ≤ X ≤ 10⁵

3.入力例

入力

4 2000

出力

Yes

4.初見の感想

500×K>=Xを判定する

5.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    public static void Main()
    {
        string[] input = Console.ReadLine().Split();
        int K = int.Parse(input[0]);
        int X = int.Parse(input[1]);
        if (500 * K >= X) { Console.WriteLine("Yes"); }
        else { Console.WriteLine("No"); }
    }
}

6.最後に

シンプルに書けた気がします！

2020-01-27

AtCoder Beginner Contest 153 E - Crested Ibis vs Monster

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

今週はこの問題が解けず悔しかったです、ねむーです。

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

0.はじめに

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

1.問題文

トキはモンスターと戦っています。

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

トキは N 種類の魔法が使え、 i 番目の魔法を使うと、モンスターの体力を A_i 減らすことができますが、トキの魔力を B_i 消耗します。

同じ魔法は何度でも使うことができます。魔法以外の方法でモンスターの体力を減らすことはできません。

モンスターの体力を 0 以下にすればトキの勝ちです。

トキがモンスターに勝つまでに消耗する魔力の合計の最小値を求めてください。

2.制約

1 ≤ H ≤ 10⁴
1 ≤ N ≤ 10³
1 ≤ A_i ≤ 10⁴
1 ≤ B_i ≤ 10⁴
入力中のすべての値は整数である。

3.入力例

入力

出力

4.初見の感想

とりあえずMP効率のよい魔法をたくさん使って、HPが小さくなってきたらどの魔法使うか考え始める方針を最初に思いつきました(貪欲法的な感じ)
効率良いけどMPを大幅に使う魔法を２回使ってMP大幅に使うより、多少効率悪い魔法でも同じくHPを綺麗に削りきることができればMP効率が良いパターンが存在する
上の損得の分岐点を単純に見つけるのは非常に難しい
そもそもNが10³制約なので、いつもと違う感じがする

5.学びポイント

「体力Nを削り切るのに、最小何MPいるか」という値を繰り返し計算で求める
繰り返し計算なのでDP(動的計画法)が使える
計算量が許せば、全探索的な手法が最強ということを体現しています
実は個数制限なしナップサック問題だった

6.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    public static void Main()
    {
        string[] input = Console.ReadLine().Split();
        long H = long.Parse(input[0]);
        long N = long.Parse(input[1]);
        //DPの初期化
        long[] DP = new long[H + 1];
        DP[0] = 0;
        for(int i = 1; i <= H; i++) { DP[i] = long.MaxValue; }
        //各魔法ごとにDPで体力Nを削り切るのに、最小何MPいるかの表を埋める
        for(int i = 0; i < N; i++)
        {
            input = Console.ReadLine().Split();
            long a = int.Parse(input[0]);
            long b = int.Parse(input[1]);
            for(int j = 0; j < H; j++)
            {
                //魔法を使った時のMPを計算し比較
                if (DP[j] == long.MaxValue) continue;
                int k = (int)Math.Min(j + a, H);
                DP[k] = Math.Min(DP[k], DP[j] + b);
            }
        }
        Console.WriteLine(DP[H]);
    }
}

7.最後に

この問題解けないの、悔しい…

2020-01-23

AtCoder Beginner Contest 152 C - Low Elements

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

修論を書き上げるため競プロのペースが落ち気味の、ねむーです。

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

0.はじめに

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

1.問題文

1 , … , N の順列 P_1 , … , P_N が与えられます。次の条件を満たす整数 i ( 1 ≤ i ≤ N ) の個数を数えてください。

任意の整数 j ( 1 ≤ j ≤ i ) に対して、 P_i ≤ P_j

2.制約

1 ≤ N ≤ 2 × 10⁵
P_1 , … , P_N は 1 , … , N の順列である。
入力はすべて整数である。

3.入力例

入力

8
5 7 4 2 6 8 1 3

出力

4.初見の感想

2×10⁵の計算量なのでO(N²)は厳しい

5.学びポイント

問題を言い換えると、数列の中で最後の数字が最小値であれば条件を満たす
for文で前から見ていって、最小値を更新していき更新回数を数えていく

6.コードと簡単な解説

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[] P = new int[N];
        for(int i = 0; i < N; i++)
        {
            P[i] = int.Parse(input[i]);
        }
        int min = int.MaxValue;
        int ans = 0;
        for(int i=0; i < N; i++)
        {
            if (min >= P[i]) { min = P[i];ans++; }
        }
        Console.WriteLine(ans);
    }
}

7.最後に

この問題が早く解けたので成長を感じます！

2020-01-22

AtCoder Beginner Contest 152 D - Handstand 2

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

少し風邪をひいていました、ねむーです。

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

0.はじめに

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

1.問題文

正の整数 N が与えられます。 N 以下の正の整数の組 ( A , B ) であって、次の条件を満たすものの個数を求めてください。

A , B を先頭に 0 のつかない 10 進数表記で表したときに、 A の末尾の桁が B の先頭の桁に等しく、 A の先頭の桁が B の末尾の桁に等しい

2.制約

1 ≤ N ≤ 2 × 10⁵
入力はすべて整数である。

3.入力例

入力

出力

400000008

4.初見の感想

制約が2×10⁵であるのでO(N²)の計算量は難しい
最初と最後の文字を固定して、間の文字を再帰的に考える方法を最初考えた

→N以下という判定を行って個数を計算するところが少し複雑となる

→そもそも最初と最後の文字の組み合わせ分やらなければならない(9×9=81通り)

5.学びポイント

O(N)の解法を考える
1~Nまでのfor文を回して数字をそれぞれ最初と最後の文字ごとに分類する
今回は二次元配列としてtemp[最初の文字,最後の文字]といった配列を用意し、それぞれの個数を分類しています
最初の文字の出し方→数字÷(10^桁数)で求められる(小数点以下切り下げ)
最後の文字の出し方→数字%10で求められる

6.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        //入力
        int N = int.Parse(Console.ReadLine());
        int[,] temp = new int[10, 10];
        for (int i = 1; i <= N; i++)
        {
            //最初と最後の数字を出す
            int left = (int)(i / Math.Pow(10, (int)Math.Log10(i)));
            int right = (int)(i % 10);
            //数字を分類する
            if (left != 0 && right != 0)
            {
                temp[left, right]++;
            }
        }
        int ans = 0;
        for (int i = 0; i < 10; i++)
        {
            for (int j = 0; j < 10; j++)
            {
                //求めるパターンが何個か数える
                ans+=temp[i, j] * temp[j, i];
            }
        }
        Console.WriteLine(ans);
    }
}

7.最後に

この方針に行きつくまでに時間がかかってしまうのが反省点です…

2019-12-14

AtCoder Beginner Contest 147 D - Xor Sum 4

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

あったかい飲み物が離せません、ねむーです。

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

0.はじめに

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

1.問題文

N 個の整数があり、 i 番目の整数は A i です。 f:id:nemurin_blog:20191209220728p:plain

を 10⁹ + 7 で割った余りを求めてください。

2.制約

2 ≤ N ≤ 3 × 10⁵
0 ≤ A i < 2⁶⁰
入力中のすべての値は整数である。

3.入力例

入力

10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820

出力

103715602

4.初見の感想

XOR演算自体はa^bで実装できるので簡単
2⁶⁰は整数型に収まらないので工夫が必要
全パターン計算していると計算時間が終わらない

5.学びポイント

XOR演算は桁の繰り上がりがないので各桁でそれぞれ考える
XORは片方が0、片方が1の時計算結果が1になるのでそれぞれの数字で「0の個数」×「1の個数」を計算すれば何回1になるかが計算できる
個数計算は計算量O(N)なので総当たりのO(N²)より相当早い
2⁶⁰は整数型に収まらないので各桁でループを回して計算する

6.コードと簡単な解説

using System;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        //入力
        int N = int.Parse(Console.ReadLine());
        long[] A = new long[N];
        string[] str = Console.ReadLine().Split();
        for (var i = 0; i < N; i++)
        {
            A[i] = long.Parse(str[i]);
        }
        long[] D1 = new long[61];
        long[] D2 = new long[61];
        long mod = 1000000007;
        for (var i = 0; i < N; i++)
        {
            long digit = 1;
            for (var j = 0; j <= 60; j++)
            {
                //各桁で0と1の個数計算
                if (A[i] / digit % 2 == 1)
                {
                    D1[j]++;
                }
                else
                {
                    D2[j]++;
                }
                digit *= 2;
            }
        }
        long digit1 = 1;
        long ans = 0;
        for (var i = 0; i <= 60; i++)
        {
            //何回XORになるかを計算
            long temp = D1[i] * D2[i] % mod;
            temp = digit1 % mod * temp % mod;
            ans = (ans + temp) % mod;
            digit1 *= 2;
        }
        Console.WriteLine(ans);
    }
}

7.最後に

本番では解けなかったので残念でした…

2019-12-13

AtCoder Beginner Contest 147 B - Palindrome-philia

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

寒くて布団が恋しい季節です、ねむーです。

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

0.はじめに

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

1.問題文

高八士君は回文が大好きで、回文でない文字列が許せません。高八士君は文字列を 1 回ハグするごとに、文字列から 1 文字を選んで任意の文字に変えることができます。

文字列 S が与えられます。 S を回文にするために必要なハグの最小回数を答えてください。

2.制約

S は半角英小文字のみから成る文字列
S の長さは 1 以上 100 以下

3.入力例

入力

abcdabc

出力

4.初見の感想

前と後ろから順に比較して、真ん中まで異なる回数を数えます
入力の長さが奇数と偶数で真ん中の定義が少し変わります

5.学びポイント

例えば文字数が3の時は2個目までは見てほしい訳です
小数点の切り上げを行うのでCeling関数を使います

6.コードと簡単な解説

using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        string input = Console.ReadLine();
        double half = input.Length/2;
        half = Math.Ceiling(half);
        int ans = 0;
        for (int i = 0; i < half; i++)
        {
            if (input[i] != input[input.Length - i - 1])
            {
                ans++;
            }
        }
        Console.WriteLine(ans);
    }
}

7.最後に

実際は小数点切り下げでも問題ないですよ！