Web備忘録 プログラミングを中心に技術的な事柄を忘れないように書き残します。

AtCoder Beginner Contest 154 に参加した記録

AtCoder Beginner Contest 154 に参加した記録
目次

AtCoder Beginner Contest 154 に参加した記録

AtCoder Beginner Contest 154 – AtCoder

ABC154 に参加しました。

結果はABCDEの5問ACでした。前回と同じく、全体的に優しい難易度のコンテストという印象を持ちました。累積和(もしくは尺取り法)、桁DPの典型問題がありました。

E問題が桁DPで解く問題だったのですが、いつか出るかもと予習もとい類題の準備をしていたのでそれを参考にしました。

パフォーマンスはなんと、青色1600くらいでした。初の青パフォーマンスです。レーティングも水色に近づいてきました。この調子が続けばあと2,3回で水色になれそうです。まあ続かないと思いますが。

ということで問題を振り返ります。

A – Remaining Balls

A – Remaining Balls

文字列 S の書かれたボールが A 個、文字列 T の書かれたボールが B 個あります。

高橋君は、文字列 U の書かれたボールを 1 個選んで捨てました。

文字列 S,T の書かれたボールがそれぞれ何個残っているか求めてください。

if文による条件判定と四則演算が書ければ解ける問題です。

if (U == S) A--;
else B--;
Console.WriteLine(A + " " + B);

B – I miss you…

B – I miss you…

文字列 S が与えられます。S のすべての文字を x で置き換えて出力してください。

非常にシンプルな問題です。Sと同じ長さの 'x' だけで構成された文字列を生成すればOKです。

var ans = new string('x', S.Length);
Console.WriteLine(ans);

競技プログラミングだとこの string のコンストラクタを使って繰り返し文字を生成するというのをよく使う気がします。C#使いの人は覚えておくと便利です。

C – Distinct or Not

C – Distinct or Not

整数列 A1,A2,…,AN が与えられます。 この整数列のどの 2 つの要素も互いに異なるならば YES を、そうでないなら NO を出力してください。

制約

  • 2≤N≤200000
  • 1≤Ai≤109

これまたシンプルな問題です。要するに与えられた数列に重複する値が含まれているかどうかを判定すればよいです。

判定のために使える方法はぱっと2つくらい思いつきます。

  1. A をソートして隣り合う要素を比較する
  2. 全部の要素を辞書型に入れてカウントする

制約でAの要素が最大109まであるので配列に入れて数えることはできません。好きなほうで実装すればOKです。

ソートして隣り合う要素を比較するなら以下のようなコードになります。

Array.Sort(A);
var ans = "YES";
for (int i = 1; i < N; i++)
{
    if (A[i] == A[i - 1])
    {
        ans = "NO";
        break;
    }
}

ループは i=1 から初めて A[i] と A[i-1] を比較してやるとすべての隣接する要素を確認できます。一致する要素があればソートしているので必ず隣同士になってくれます。

D – Dice in Line

D – Dice in Line

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

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

制約

  • 1≤K≤N≤200000
  • 1≤pi≤1000

ぱっと見て目を引く文言は「期待値」です。この問題は期待値の求め方を知らなければそもそも解けません。ということでまずは期待値の求め方です。

期待値 – Wikipedia

期待値はある試行を行ったときの結果として得られる値の平均値です。

今回の例だと「サイコロを振る」というのが試行にあたり、「さいころの目」が結果として得られる値です。つまりここでの期待値は、「さいころを振ると平均してどれくらいの目がでるか」になります。

一般的な6面体のサイコロだと出目の期待値は以下のような計算で 3.5 になります。

  (1/6)*1 + (1/6)*2 + (1/6)*3 + (1/6)*4 + (1/6)*5 + (1/6)*6
= (1/6)*(1+2+3+4+5+6)
= 3.5

つまり1回のサイコロを振ると大体3.5くらいの出目が期待できるということです。

今回の問題では1からpiまでのpi種類の出目があり、それぞれの目が等確率(1/pi)で出るので、i番目のサイコロの期待値は以下のようになります。

(1/pi)*(1+..+pi)

piが最大1000なのでループして先にすべてのさいころの期待値を求めておくとあとは累積和(ないしは尺取り法?)を使って隣接するK個の区間の最大を求めればOKです。

// 入力省略 ...

// すべての種類のさいころの期待値を求めておく
var kitaichi = new double[1001];
var sum = 0; // 1+..+n
for (int i = 1; i &lt;= 1000; i++)
{
    sum += i;
    kitaichi[i] = (double)sum / i;
}

// 与えられたさいころの期待値
var pKitaichi = new double[N];
for (int i = 0; i &lt; N; i++)
{
    pKitaichi[i] = kitaichi[P[i]];
}

// 隣接するK個の期待値の総和の最大を求める
var ans = pKitaichi.Take(K).Sum();
var now = ans;
for (int i = K; i &lt; N; i++)
{
    now -= pKitaichi[i - K];
    now += pKitaichi[i];
    ans = Math.Max(ans, now);
}
Console.WriteLine(ans);

最初の区間(0からk-1)をLinqで求めておいて、次の区間からループで求めています。こうすれば配列外参照もしなくてわかりやすいです。

[1, 2, 3, 4, 5]
 -------        最初の値
    -------     ループ1回目
       -------  ループ2回目

例えば5個の配列から連続する3個の和を求める順番は上のような感じです。これは尺取り法になるんですかね。最初は累積和だと勘違いして書いていたのですが、尺取り法かもしれません。

累積和だと先に累積和を求めておいて後で利用するようにしないとですね。累積和で実装すると以下のような感じです。期待値の先計算は同じです。

// ここまでは一緒 ...

// 累積和を計算しておく
var sumlist = new double[N];
sumlist[0] = pKitaichi[0];
for (int i = 1; i < N; i++)
{
    sumlist[i] = sumlist[i - 1] + pKitaichi[i];
}

// 累積和でK個の区間合計の最大を求める
var ans = 0.0;
for (int i = K - 1; i < N; i++)
{
    var now = sumlist[i];
    if (i - K >= 0) now -= sumlist[i - K];
    ans = Math.Max(ans, now);
}
Console.WriteLine(ans);
[1, 2, 3, 4, 5]
 ----------     この区間の合計から
 --             この区間の合計を引くと
    -------     この区間が求まる

累積和のイメージです。

累積和でも解きなおしてACしました。

E – Almost Everywhere Zero

E – Almost Everywhere Zero

1 以上 N 以下の整数であって、 10 進法で表したときに、0 でない数字がちょうど K 個あるようなものの個数を求めてください。
制約

  • 1≤N<10100
  • 1≤K<3

これまたシンプルな問題です。桁DPの問題であることはすぐにわかりました。

桁DPの問題の特徴は A以上B以下の整数 … みたいな文言とやたらでかい整数Nの制約です。ただの印象論ですが。

ようするに全探索は桁がでかすぎて明らかに不可能なので、桁ごとに独立して計算していこうというのが桁DPです。

過去、似たような問題だと以下のようなものがABCで出題されています。

「禁止された数字」はかなり似ている問題です。そして私はこの問題を予習していたので同じように解けました。

桁DPの解説は参考になる記事がたくさんあります。

桁DPを知らない人はぜひこの機会に覚えておくといいです。解けるとうれしいです。

桁DPはつまるところDPの一種なので、ループでも解けるしメモ化再帰でも解けます。ただ、私個人としては桁DPをループで解くのがイメージしづらいのでおとなしくメモ化再帰を使って解きます。

こっちのほうが何をやっているか個人的にイメージしやすいだけです。

static long[,,] Memo;
static int K;
static string N;
static void Main(string[] args)
{
    N = sc.ReadStr();
    K = sc.ReadInt();

    // 桁数、最大フラグ、0以外の個数
    Memo = new long[N.Length, 2, N.Length + 1];

    for (int i = 0; i < N.Length; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            for (int k = 0; k < N.Length + 1; k++)
            {
                // まだ計算されていない箇所は-1にしておく
                Memo[i, j, k] = -1;
            }
        }
    }
    var ans = Rec(0, true, 0);
    Console.WriteLine(ans);
}
static long Rec(int n, bool maxFlag, int count)
{
    // 最終桁まで見たとき、0以外の個数がK個なら1、それ以外は0
    if (n == N.Length) return count == K ? 1 : 0;

    // 計算済であればそれを返す
    var imax = maxFlag ? 1 : 0;
    if (Memo[n, imax, count] >= 0) return Memo[n, imax, count];

    // 現在の桁の最大値分ループ
    long res = 0;
    var end = maxFlag ? N[n] - '0' : 9;
    for (int i = 0; i <= end; i++)
    {
        // 最大フラグが立っていて、現在の桁も最大の場合は true
        var nextMaxFlag = maxFlag && i == end;
        // ゼロ以外の数字の場合は+1しておく
        var nextCunt = count + (i != 0 ? 1 : 0);
        // 次の桁の計算をする
        res += Rec(n + 1, nextMaxFlag, nextCunt);
    }
    // メモをしておく
    Memo[n, imax, count] = res;
    return res;
}

AtCoder Problems によると Difficulty 1200 くらいの問題でした。典型なのでおいしい問題でした。解けてよかったです。

解説PDF 見るともっとスマートに O(LK) で計算できるみたいです。Lが桁数です。

まあACしたのでOKです。たぶん個のコードもあってるでしょう。DPのMemoの3つ目の N.Length+1 はでかく確保しすぎですが、制約的に問題ないのは一応把握して実装しています。提出時の実行時間も20ms程度なので問題ないです。

F – Many Many Paths

F – Many Many Paths

F問題は1時間以上時間があったのですが、結局何もわかりませんでした。いい感じに計算量を減らす方法を考えましたが無理でした。

以上。

競技プログラミングカテゴリの最新記事