[C#] 三井住友信託銀行プログラミングコンテスト2019 の記録

[C#] 三井住友信託銀行プログラミングコンテスト2019 の記録

三井住友信託銀行プログラミングコンテスト2019 – AtCoder

三井住友信託銀行プログラミングコンテスト2019 に参加したのでその記録です。

AtCoder Beginner Contest (ABC) 相当の難易度のコンテストです。

結果は ABCD の4問解けて、Eは解けそうで解けませんでした。以下コンテスト中に考えてたことです。

A – November 30

A – November 30

2つの日付「M1月D1日」と「M2月D2日」が与えられ、M1月D1日が月末日であるか判定するという問題です。2つの日付は存在する日付であり、連続する日付であることが保障されます。

M1 != M2 で判定しました。

一瞬 D1, D2 いらないけどいいのか？と思いましたが気にせず提出して AC しました。D2 == 1 でもよかったですね。

B – Tax Rate

B – Tax Rate

消費税込でN円支払って商品1つを買いました。商品1つの税抜価格Xを求めます。税抜X円の商品は X * 1.08(小数点以下切捨て) で求まります。

Nが与えられるのでXを求めてください。ただしそのようなXが存在しないNが与えられる場合があります。

単純に X * 1.08 = N なので変形して X = N/1.08 じゃあないかと思いますが、入力例2の 1079 みたいに X が存在しない場合があります。

X が存在しない場合の判定に迷いましたが、X = N/1.08 でもとめた整数 X について、XとX±1 の3つくらいから N を求めて正しくなければNGと判定すればいいやと思いました。

が、制約が最大でも N=50000 なので全探索しました。

for (int x = 1; x <= 50000; x++)
{
    var n = (int)(x * 1.08);
    if (n == N)
    {
        Console.WriteLine(x);
        return;
    }
}
Console.WriteLine(":(");

こんな感じです。

C – 100 to 105

C – 100 to 105

AtCoder 商店では、以下の 6種類の品物が 1000000個ずつ売られています。

• 1 個 100 円のおにぎり
• 1 個 101 円のサンドイッチ
• 1 個 102 円のクッキー
• 1 個 103 円のケーキ
• 1 個 104 円の飴
• 1 個 105 円のパソコン

高橋君は、合計価格がちょうど X円となるような買い物をしたいです。そのような買い方が存在するか判定してください。
ただし、消費税は考えないものとします。

制約: 1≤X≤100000

DPっぽい匂いがします。ですがコンテスト中にDPを使ったことがないのであきらめました。

なのでコンテスト中の方針としては、100未満の端数と100円以上の数を分けて考えることにしました。

買う商品数を決める

全部の品が1000000個あるのでどれを何個使っても組み合わせの数で問題になることはないと思います。

また、どんな組み合わせでもN個買うと N*100 円以上の金額になります。なので買うことができる商品数は X/100 で求まります。

例えば入力例1の 615 だと6個、入力例2の 217 だと2個です。これ以上買うと、Xを超過してしまいます。

端数を作るのに買わないといけない最小の商品数を決める

次に100円未満の端数を作るために買わないといけない最小の商品数を求めます。

100円未満の端数については 1~5 を組み合わせて作る必要があります。端数は X % 100 で求めます。

端数を作るのに必要な個数は (端数+4)/5 で求まります。5を使えるだけ使ってあまりを1~4で埋める計算です。

矛盾しないか判定

買う商品数と買わないといけない最小の商品数が決まったので後は矛盾しないか判定して完了です。

ちなみに最小との差は、100円の商品を買って埋めることになります。

例えば、618円なら (105+105+105+103)+100+100 となります。

コード

var max = X / 100;
var min = (X % 100 + 4) / 5;
if (min <= max)
{
    Console.WriteLine(1);
}
else
{
    Console.WriteLine(0);
}

D – Lucky PIN

D – Lucky PIN

AtCoder 社は、オフィスの入り口に 3 桁の暗証番号を設定することにしました。

AtCoder 社には N 桁のラッキーナンバー S があります。社長の高橋君は、S から N−3 桁を消して残りの 3 桁を左から読んだものを暗証番号として設定することにしました。

このとき、設定されうる暗証番号は何種類あるでしょうか？
ただし、ラッキーナンバーや暗証番号はいずれも 0 から始まっても良いものとします。

制約: 4≤N≤30000

3つ取り出して左から並べる時の種類数を求める問題です。単純な全探索だとN^3で間に合いません。

最初に思いついたのが3桁で 000~999 までのたかだか10^3通りなので、これを全探索すればいいのではないかということでした。となると計算量が 3*10^7 程度となります。

ここで1つ勘違いしていて、10^7 は間に合わないと思ってました。なのでこの考えを却下して、どうにか 10^6 位まで計算量を落とせないか考えました。

暗証番号の真ん中の文字を固定して累積和を使う

どうせ各桁の取りうる値は10通りしかないので、これを使ってうまくできないか考えました。ということで思いついたのが累積和です。

考え方としては以下のような感じです。

1. Sの各桁時点で出現している0~9の個数を数えておく(累積和)
2. 暗証番号の真ん中の文字(2文字目, S[i])を固定して考える(N-2通りを走査する)
3. 前までに出てくる文字の個数を見て、1文字目を決める。
4. 後に出てくる文字の個数を見て、3文字目を決める。

i+1文字目以降に出現する各文字の個数は N文字目までの各文字の個数 - i文字目までの各文字の個数 で求まります。

これで N*10*10 に収まります。ということで実装しました。

コード

// i文字目の時点で出現する0~9の個数を求めておく
var counts = new int[N, 10];
for (int i = 0; i < N; i++)
{
    for (int j = 0; j < 10; j++)
    {
        if (i > 0)
        {
            counts[i, j] = counts[i - 1, j];
        }
    }
    var n = (int)S[i] - '0';
    counts[i, n]++;
}

var dic = new Dictionary<int, bool>();
// 暗証番号2文字目の取りうる値をループ
for (int i = 1; i < N - 1; i++)
{
    // 1文字目のパターン
    for (int j = 0; j < 10; j++)
    {
        if (counts[i - 1, j] == 0) continue;

        // 3文字目のパターン
        for (int k = 0; k < 10; k++)
        {
            if (counts[N - 1, k] - counts[i, k] == 0) continue;
            var key = j * 100 + ((int)S[i] - '0') * 10 + k;
            dic[key] = true;
        }
    }
}

var ans = dic.Count();
Console.WriteLine(ans);

ちなみにこのコード、キーの部分を律儀に文字列に変換していると、かなり時間がかかります。コンテスト中はそれでも ACはできましたが、おとなしく整数値なりタプルなりをキーにしましょう。

暗証番号を全探索するコード

var ans = 0;
for (int i = 0; i < 10; i++)
{
    for (int j = 0; j < 10; j++)
    {
        for (int k = 0; k < 10; k++)
        {
            var ok1 = false;
            var ok2 = false;
            var ok3 = false;
            foreach (var c in S)
            {
                var n = (int)c - '0';
                if (n == k && ok2) ok3 = true;
                else if (n == j && ok1) ok2 = true;
                else if (n == i) ok1 = true;
            }
            if (ok1 && ok2 && ok3)
            {
                ans++;
            }

        }
    }
}
Console.WriteLine(ans);

こっちの方がわかりやすかったです。

緑になりました。

パフォーマンスは 1000 ないくらいでした。BC でつまらないみすして 2WA しましたが、なんとか緑(レート800台)になりました。

E問題にも手を付けていきたいところです。

あとDPが本番で書けるようになりたいので、今回のCDについてDPでも解けるみたいなので、それぞれ解いてみようと思います。

以上。