D - We Like AGC

DP 競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 122
D - We Like AGC
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

整数 N が与えられます。
次の条件を満たす長さ N の文字列の数を 10~9+7 で割った余りを求めてください。

・A, C, G, T 以外の文字を含まない。
・AGC を部分文字列として含まない。
・隣接する 2 文字の入れ替えを 1 回行うことで上記の条件に違反させることはできない。

注記

文字列 T の部分文字列とは、T の先頭と末尾から 0 文字以上を取り去って得られる文字列です。
例えば、ATCODER の部分文字列には TCO, AT, CODER, ATCODER,  (空文字列) が含まれ、AC は含まれません。

制約

・3≤N≤100

入力

入力は以下の形式で標準入力から与えられる。

N

出力

条件を満たす文字列の数を 10^9+7 で割った余りを出力せよ

解き方

以下を参考にしています。
ABC122 D - We Like AGC - ARMERIA
AtCoder ABC 122 D - We Like AGC (400 点) - けんちょんの競プロ精進記録
提出 #4704271 - AtCoder Beginner Contest 122

解き方の流れ

問題文に書かれている条件のうち
以下の2つ目と3つ目

・AGC を部分文字列として含まない。
・隣接する 2 文字の入れ替えを 1 回行うことで上記の条件に違反させることはできない。

がなければ問題がシンプルになるので
どのような場合に
この条件に引っかかるのかを考えます。

すると以下の文字の並びのとき、
条件にかかることが分かります。

AGC GAC ACG A?GC AG?C

「？」は「何でもいいので何か一文字」を指しています。

上の条件にかかってしまう部分文字列から、
3文字前、2文字前、1文字前、現在の文字を調べ
上の部分文字列と同じになっていたら
そのパターンは数としてカウントしないという方法がとれそうです。

文字列のパターンをカウントしていくには
DPを使用します。
構成要素は以下のようにします。

dp[文字の数][現在の文字から2つ前の文字][現在の文字から1つ前の文字][現在の文字]=「文字の数」でできるパターンの数

そして、
以下のようにループを回しながら
作ることのできる文字列をカウントしていきます。

問題文から文字列を構成するのは
A,G,C,Tの4文字ですが
数字に置き換えるとループの数をそのまま使えるので
A=1,G=2,C=3,T=4と各文字を数字に置き換えています。

また、DPの始点としての文字列が一つ欲しいので
ダミーの文字を一つ追加し、
数字を0と置きました。
始点を全てdummy文字にしています。
（dp[0, 0, 0, 0] = 1;）

参考：AtCoder ABC 122 D - We Like AGC (400 点) - けんちょんの競プロ精進記録

//dummy=0,A=1,G=2,C=3,T=4
var dp = new long[N + 1, 5, 5, 5];
dp[0, 0, 0, 0] = 1;
//文字数
for (int n = 0; n < N; ++n)
{
    //3文字前の文字
    for (int i = 0; i < 5; ++i)
    {
        //2文字前の文字
        for (int j = 0; j < 5; ++j)
        {
            //1文字前の文字
            for (int k = 0; k < 5; ++k)
            {
                //現在の文字
                for (int l = 1; l < 5; ++l)
                {
                    //AGC GAC ACG A?GC AG?C (i,j,k,l)のパターンをはじく
                    if (j == 1 && k == 2 && l == 3//AGC
                    || j == 2 && k == 1 && l == 3//GAC
                    || j == 1 && k == 3 && l == 2//ACG
                    || i == 1 && k == 2 && l == 3//A?GC
                    || i == 1 && j == 2 && l == 3)//AG?C
                    {
                        continue;
                    }
                    dp[n + 1, j, k, l] = (dp[n + 1, j, k, l] + dp[n, i, j, k]) % 1000000007;
                }
            }
        }
    }
}

現在の文字の「l」だけ範囲が
0～5ではなく1～5になっていますが
これは、
実際に数える際には「dummy」の数字は必要ないから
だと思います。

あと、
これはなぜか分からなかったのですが
「l」の範囲を0～5にすると
値がずれます。

dp[0, 0, 0, 0] = 1 は
1のままで変わらないで欲しいのに
i=0,j=0,k=0,l=0のとき
dp[0, 0, 0, 0] =dp[0, 0, 0, 0] +dp[0, 0, 0, 0] で
dp[0, 0, 0, 0] が2になってしまうからかもしれないです。

あとは、
dummyの0を除いた
1～4でループを回し
DPの中に保存されている
N文字のときのパターンを
足せば答えが出ます。

//パターンの個数を出す
var ans = 0L;
//dummyの0を除いた1～4でループ
 for (int i = 1; i < 5; ++i)
 {
    for (int j = 1; j < 5; ++j)
    {
        for (int k = 1; k < 5; ++k)
        {
            //N文字のときのパターンの数が知りたいので文字数はN固定
            ans = (ans + dp[N, i, j, k]) % 1000000007;
        }
    }
}

全体のコード

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

class Program
{
    static void Main()
    {
        var N = Int32.Parse(Console.ReadLine());
        //dummy=0,A=1,G=2,C=3,T=4
        var dp = new long[N + 1, 5, 5, 5];
        dp[0, 0, 0, 0] = 1;
        //文字数
        for (int n = 0; n < N; ++n)
        {
            //3文字前の文字
            for (int i = 0; i < 5; ++i)
            {
                //2文字前の文字
                for (int j = 0; j < 5; ++j)
                {
                    //1文字前の文字
                    for (int k = 0; k < 5; ++k)
                    {
                        //現在の文字
                        for (int l = 1; l < 5; ++l)
                        {
                            //AGC GAC ACG A?GC AG?C (i,j,k,l)のパターンをはじく
                            if (j == 1 && k == 2 && l == 3//AGC
                            || j == 2 && k == 1 && l == 3//GAC
                            || j == 1 && k == 3 && l == 2//ACG
                            || i == 1 && k == 2 && l == 3//A?GC
                            || i == 1 && j == 2 && l == 3)//AG?C
                            {
                                continue;
                            }
                            dp[n + 1, j, k, l] = (dp[n + 1, j, k, l] + dp[n, i, j, k]) % 1000000007;
                        }
                    }
                }
            }
        }
        //パターンの個数を出す
        var ans = 0L;
        //dummyの0を除いた1～4でループ
        for (int i = 1; i < 5; ++i)
        {
            for (int j = 1; j < 5; ++j)
            {
                for (int k = 1; k < 5; ++k)
                {
                    //N文字のときのパターンの数が知りたいので文字数はN固定
                    ans = (ans + dp[N, i, j, k]) % 1000000007;
                }
            }
        }
        Console.WriteLine(ans);
    }
}

C - HSI

期待値 競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 078
C - HSI
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

高橋くんはプログラミングコンテストに出ていますが， YES か NO で答える問題でTLEしてしまいました。

提出の詳細を見ると，テストケースは全てで N ケースあり，そのうち M ケースでTLEしていました。

そこで高橋くんは, M ケースではそれぞれ実行に 1900 ms かかって 1/2 の確率で正解し，
残りの N−M ケースでそれぞれ実行に 100 ms かかって必ず正解するプログラムへ書き換えました。

そして，以下の操作を行います。

・このプログラムを提出する。
・全てのケースの実行が終わるまで待機する。
・もし M ケースのうちどれかで不正解だった場合，もう一度プログラムを提出する。
・これを，一度で全てのケースに正解するまで繰り返す。

この操作が終了するまでの，プログラムの実行時間の総和の期待値を X msとした時，X を出力してください。
なお，X は整数で出力してください。

制約

・入力は全て整数
・1≤N≤100
・1≤M≤min(N,5)

入力

入力は以下の形式で標準入力から与えられる。

N M

出力

実行時間の総和の期待値 X を整数で出力してください。 なお，X はこの問題の制約下で，10^9 以下の整数となることが証明できます。

解き方

以下を参考にしています。
https://img.atcoder.jp/arc085/editorial.pdf
AtCoder ARC 085 C - HSI (300 点) - けんちょんの競プロ精進記録
ARC085 / ABC078 C HSI - 足跡-sokuseki-
ABC078 C問題 : HSI - 忘れても大丈夫

解き方の流れ

問題文から

M ケースではそれぞれ実行に 1900 ms かかって 1/2 の確率で正解し，
残りの N−M ケースでそれぞれ実行に 100 ms かかって必ず正解するプログラム

を高橋君が書くことが分かるので
一回のプログラム提出の際にかかる時間は

1900×M+100×(N-M)

です。

これを全てのケースが正解するまで繰り返すので、
全体の時間は

(1900×M+100×(N-M))×(全てのテストケースが通るまでにかかる回数)

となります。

全てのテストケースが通るまでにかかる回数は
M問が全て正解するまでの回数の期待値です。

例えばMが1だとすると
正解する確率は1/2なので
2回が期待値になります。

これがMが2だとすると
正解する確率は1/2×1/2=1/4になり
4回が期待値になります。

つまり 全てのテストケースが通るまでにかかる回数は
それぞれの提出で正解する確率が(1/2)Mなので
2Mということになります。

証明は以下の記事でされていました。
AtCoder ARC 085 C - HSI (300 点) - けんちょんの競プロ精進記録

これを加えると
先程の式は以下のようになり
これで答えを出すことができます。

(1900×M+100×(N-M))×(2^M)

全体のコード

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

class Cmondai
{
    static void Main()
    {
        var nm = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray(); ;
        var N = nm[0];
        var M = nm[1];
        //Mが全て正解するまでにかかる回数の期待値
        var count = Math.Pow(2, M);
        //一回のプログラム提出にかかる時間
        var time = 1900 * M + 100 * (N - M);
        //最終的にかかる時間は　(一回のプログラム提出にかかる時間)×(Mが全て正解するまでにかかる回数の期待値)
        Console.WriteLine(count * time);
    }
}

C - Snuke Festival

競プロ 二分探索

はじめに

競技プログラミング、AtCoder Beginner Contest 077
C - Snuke Festival
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

今年もすぬけ祭の季節がやってきました。
りんごさんは、まず手始めにすぬけ君召喚の儀式を執り行おうと思っています。 
儀式には祭壇が必要で、祭壇は上部、中部、下部の 3 つのカテゴリーのパーツ 1 つずつからなります。

祭壇の 3 カテゴリーのパーツがそれぞれ N 個ずつあります。 
i 個目の上部のパーツのサイズは Ai 、i 個目の中部のパーツのサイズは Bi 、i 個目の下部のパーツのサイズは Ci です。

祭壇を作るにあたっては、中部のパーツのサイズは上部のパーツのサイズより真に大きく、下部のパーツのサイズは中部のパーツのサイズより 真に大きくなければなりません。
逆に、この条件を満たす任意の 3 つのピースを組み合わせて祭壇を作ることができます。

りんごさんが作ることのできる祭壇は何種類あるでしょうか。
ただし、2 つの祭壇が異なるとは、上部、中部、下部に使われるピースのうち 少なくとも 1 つが異なることを言います。

制約

・1≤N≤10^5
・1≤Ai≤10^9(1≤i≤N)
・1≤Bi≤10^9(1≤i≤N)
・1≤Ci≤109(1≤i≤N)
・入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N
A1 ... AN
B1 ... BN
C1 ... CN

出力

りんごさんが作ることのできる祭壇の種類数を出力せよ。

解き方

以下を参考にしています。
https://img.atcoder.jp/arc084/editorial.pdf
https://atcoder.jp/contests/abc077/submissions/4561061?lang=ja

解き方の流れ

まず、条件に
「中部のパーツのサイズは上部のパーツのサイズより真に大きく、下部のパーツのサイズは中部のパーツのサイズより 真に大きくなければなりません」
とあることから
祭壇のできるパーツの組み合わせは全て
Ai<Bi<Ciであることが分かります。

ここから、
Biを決めてしまえば
AiはBiよりも小さい値、
CiはBiよりも大きな値の個数を数えられれば
各Biに対する祭壇を作れる個数を出すことができ
全て足し合わせれば
問題の答えとなる「りんごさんが作ることのできる祭壇の種類数」を出すことができます。

解き方の流れ
①Biを１つ決める
②Biよりも小さいAi、Biよりも大きいCiの個数をそれぞれ出す
③ ②で出したAiとCiの個数をかけて、①で選んだBiを使用した際に作れる祭壇の種類数を出す
④残りの各Biに対して①～③を繰り返す
⑤ ③で出した各Biを使用した際に作れる祭壇の種類数を全て足し、問題の答えを求める

実装する

この問題を実装する際、
どのように
Biよりも小さいAiの個数、
Biよりも大きいCiの個数を
出すかが問題になります。

これは解き方の流れの
②Biよりも小さいAi、Biよりも大きいCiの個数をそれぞれ出す
にあたります。

Biよりも小さい数字の個数、
Biよりも大きい数字の個数を求めたいので
Ai、Ciの配列を小さい順に並び替えれば
二分探索を使うことができます。
二分探索 - Wikipedia

～よりも小さい数字の個数

まずは
Biよりも小さい数字の個数が欲しい
Aiの個数を出す二分探索を考えます。

コードは以下です。

//引数 value=Bi array=Aiの配列
static long LowerBound(long value, long[] array)
{
    //下は０でスタート
    var low = 0;
    //上は配列の長さでスタート
    var high = array.Length;

    //highがlow以下になるまで探索を繰り返す
    while (low < high)
    {
        //中間地点(index)
        var middle = (high + low) / 2;

        //valueが中間地点以下であれば上を中間地点に引き下げる
        if (value <= array[middle]) high = middle;
        //中間地点よりもvalueが大きければ下を中間地点に引き上げる
        else low = middle + 1;
    }
    return low;
}

まず引数は
long value = Bi
long[] array = Aiの配列
です。

呼び出し元では
返ってきた値をそのまま
Biよりも小さいAiの個数として扱っています。

中身は基本的には二分探索と同じですが
異なる部分がいくつかあります。

まず、
引数で渡されるBiと同じ数字が、
Aiの配列の中にも可能性があるので
条件式にイコールをつける必要があります。

//valueが中間地点以下であれば上を中間地点に引き下げる
if (value <= array[middle]) high = middle;

このイコールがないと
問題によってはいつまでも条件分岐の中に入ることができずに
無限ループしてしまいます。

では、等符号が入る位置を変えて

//中間地点よりもvalueが小さければ上を中間地点に引き下げる
if (value < array[middle]) high = middle;
//valueが中間地点以上であれば下を中間地点に引き上げる
else low = middle + 1;

とするのはどうかというと
WAしてしまいました。

//中間地点よりもvalueが小さければ上を中間地点に引き下げる
if (value < array[middle]) high = middle;
//valueが中間地点以上であれば下を中間地点に引き上げる
else low = middle;

としてもTLEしてしまうので
一番上で示した形でないとうまく答えが出ないようです。

このメソッドの想定としては
low=value或いはlowがvalueよりも一つ大きい値になっていると思います。
理由はlowが配列のindexだからです。

このメソッドの呼び出し元では
返ってきた値をそのまま
Biよりも小さいAiの個数として扱っているので
返ってくるlowのindexよりも
Biよりも小さい個数は一つ少ないことになります。

例えば、
low=3で返ってきた場合、
lowはindexなので個数としては0,1,2,3の4つないとおかしいですが
実際は3つで計算されるので
Aiのindexが3の値はBiよりも小さくない値であることになります。

これらを色々そろえるために
コード中の等符号の位置が決められていたり
「low = middle」だけでいいようにみえる場所に
+1の処理が入っていると思われます。

～よりも大きい数字の個数

次に
Biよりも大きい数字の個数が欲しい
Ciの個数を出す二分探索を考えます。

コードは以下です。

//引数 value=Bi array=Ciの配列
static long UpperBound(long value, long[] array)
{
    //下は０でスタート
    var low = 0;
    //上は配列の長さでスタート
    var high = array.Length;

    //highがlow以下になるまで探索を繰り返す
    while (low < high)
    {
        //中間地点(index)
        var middle = (high + low) / 2;

        //中間地点よりもvalueが小さければ下を中間地点に引き下げる
        if (value < array[middle]) high = middle;
        //valueが中間地点以上であれば下を中間地点に引き上げる
        else low = middle + 1;
    }
    return low;
}

まず引数は
long value = Bi
long[] array = Ciの配列
です。

呼び出し元では
Nから返ってきた値を引いたものを
Biよりも大きいCiの個数として扱っています。

そのため、
このメソッドから返しているのはindexなのに
呼び出し元ではBi以下の個数として扱われているので
lowに入っているindexは
Biよりも一つ大きいほうにずれたものであることが分かります。

また先の
Biよりも小さいAiの個数を求めるメソッドとは
条件式の等符号が入っている位置が違っています。

これは欲しい個数が異なるものであることに依る
違いだと思われます。

例えば
AiもCiも以下の同じ配列であるとします。

1 2 3 4 5 6 7

このときBiが「4」だとすると
Aiの個数を求めるメソッドは
4より小さい数の個数3を返しますが
（実際にはindexなのでlowが指しているのは4（low=valueのパターン））
Ciの個数を求めるメソッドは
Bi以下の値の個数を返すので4を返し、
（実際にはindexなのでlowが指しているのは5（valueよりもlowが一つ大きいパターン））
Biよりも大きい値は7－4＝3と求めることができます。

全体のコード

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

class Cmondai
{
    static void Main()
    {
        var N = Int32.Parse(Console.ReadLine());
        //値が小さい順に並び替え
        var A = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).OrderBy(x => x).ToArray();
        var B = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).OrderBy(x => x).ToArray();
        var C = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).OrderBy(x => x).ToArray();

        //答えを格納する変数
        var ans = 0L;

        //Biに対する Biよりも小さいAiの個数と Biよりも大きいCiの個数を求めて 
        //各Biに対する祭壇の種類数を出して 足していく
        //各Biについて種類数を出したいのでN回まわす
        for (int i = 0; i < N; ++i)
        {
            //Biよりも小さいのAiの個数
            var a = LowerBound(B[i], A);
            //Bi以下のCiの個数
            var c = UpperBound(B[i], C);

            //各Biに対する祭壇の種類数を出して 足す
            ans += a * (N - c);
        }
        Console.WriteLine(ans);
    }
    
    //引数 value=Bi array=Ciの配列
    static long UpperBound(long value, long[] array)
    {
        //下は０でスタート
        var low = 0;
        //上は配列の長さでスタート
        var high = array.Length;

        //highがlow以下になるまで探索を繰り返す
        while (low < high)
        {
            //中間地点(index)
            var middle = (high + low) / 2;

            //中間地点よりもvalueが小さければ下を中間地点に引き下げる
            if (value < array[middle]) high = middle;
            //valueが中間地点以上であれば下を中間地点に引き上げる
            else low = middle + 1;
        }
        return low;
    }

    //引数 value=Bi array=Aiの配列
    static long LowerBound(long value, long[] array)
    {

        //下は０でスタート
        var low = 0;
        //上は配列の長さでスタート
        var high = array.Length;

        //highがlow以下になるまで探索を繰り返す
        while (low < high)
        {
            //中間地点(index)
            var middle = (high + low) / 2;

            //valueが中間地点以下であれば上を中間地点に引き下げる
            if (value <= array[middle]) high = middle;
            //中間地点よりもvalueが大きければ下を中間地点に引き上げる
            else low = middle + 1;
        }
        return low;
    }
}

C - Write and Erase

競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 073
C - Write and Erase
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

あなたは、joisinoお姉ちゃんと以下のようなゲームをしています。

・最初、何も書いていない紙がある。
・joisinoお姉ちゃんが一つの数字を言うので、その数字が紙に書いてあれば紙からその数字を消し、書いていなければその数字を紙に書く。これを N 回繰り返す。
・その後、紙に書かれている数字がいくつあるかを答える。

joisinoお姉ちゃんが言った数字が、
言った順番に A1,...,AN として与えられるので、
ゲーム終了後に紙に書かれている数字がいくつあるか答えてください。

制約

・1≦N≦100000
・1≦Ai≦1000000000(=10^9)
・入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
A1
:
AN

出力

ゲーム終了後に紙に書かれている数字の個数を出力せよ。

解き方

以下を参考にしています。
https://img.atcoder.jp/abc073/editorial.pdf

解き方の流れ

まず、
「joisinoお姉ちゃんが一つの数字を言うので、その数字が紙に書いてあれば紙からその数字を消し、書いていなければその数字を紙に書く」
という条件から
joisinoお姉ちゃんが
１回言った数字は紙に書かれる
２回言った数字は紙から消される
３回言った数字は紙に書かれる
４回言った数字は紙から消される
…
という流れになることが分かります。

ここから、
joisinoお姉ちゃんが
奇数回言った数字は紙に書かれ
偶数回言った数字は紙から消される
という法則を導くことができます。

そのため、
この問題は
Ai～ANで出てくる数字の出現回数を数え、
回数が奇数なら紙に書かれていると判断して答えの個数に加える、
回数が偶数なら紙に書かれていないと判断して答えの個数に加えない、
とすれば解けます。

実装する

数字の出現回数の数え方は、
Aiの範囲が「1≦Ai≦1000000000(=109)」なので
ここでは配列のindexを出現する数字とし、
配列の中身を出現回数として加算していくという方法がとれません。
（配列の添え字はint型なので溢れるindexはエラーになる）

そのため、
別の方法をとる必要があります。

配列を数字の小さい順に並び替え、
連続して出現する数字の個数を数えていき
別の数字が出てきたら
連続していた数字の出現した回数が
偶数か奇数かを求めて
奇数ならば最後に紙に書かれている数字とみなして
答えの個数に加えるという方法をとると解けます。

全体のコード

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

class Cmondai
{
    static void Main()
    {
        var N = Int32.Parse(Console.ReadLine());

        var A = new long[N];
        for (int i = 0; i < N; ++i) A[i] = Int64.Parse(Console.ReadLine());
        //数字の小さい順に並び替え
        A = A.OrderBy(x => x).ToArray();

        //答えの個数をカウントする変数
        var ans = 0;
        //現在数えている数字
        var currentNum = 0L;
        //現在数えている数字の個数
        var currentNumCount = 0;

        //数字を数える
        for (int i = 0; i < N; ++i)
        {
            //現在数えている数字と配列の中身が同じものなら
            if (A[i] == currentNum)
            {
                //現在数えている数字の個数を加算する
                currentNumCount++;
            }
            //現在数えている数字と配列の中身が違うものなら
            else
            {
                //集計をする
                //現在数えている数字の個数が奇数の場合は答えに加算
                if (currentNumCount % 2 != 0) ans++;

                //情報を次の数字に書き換える
                //現在数えている数字を次の数字にする
                currentNum = A[i];
                //現在数えている数字の個数を１にリセット
                currentNumCount = 1;
            }
            //配列の最期の要素のみ、次の数字が来ることがないのでその場で集計する
            if (i == N - 1) if (currentNumCount % 2 != 0) ans++;
        }
        Console.WriteLine(ans);
    }
}

C - Together

競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 072
C - Together
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

長さNの整数列 a1,a2,...,aN が与えられます。
各 1≤i≤N に対し、ai に 1 足すか、1 引くか、なにもしないかの三つの操作からどれか一つを選んで行います。
この操作の後、ある整数 X を選んで、ai=X となる i の個数を数えます。
うまく操作を行い、X を選ぶことで、この個数を最大化してください。

制約

・1≤N≤10^5
・0≤ai<10^5(1≤i≤N)
・aiは整数

入力

入力は以下の形式で標準入力から与えられる。

N
a1 a2 .. aN

出力

うまく操作を行い、X を選んだ時の ai=X なる i の個数の最大値を出力せよ。

解き方

以下を参考にしています。

https://img.atcoder.jp/arc082/editorial.pdf
https://atcoder.jp/contests/abc072/submissions/4582952?lang=ja

全体の流れ

aiに数を1足すか、1引くか、そのままにするかの操作を行い
Xとなる数字の個数を最大化する問題です。

数列の中からXを見つけ出すことに目がいきそうになりますが、
操作が3パターンしかないことに注目します。

aiからaNに対して3つの操作を行って
数字の出現回数を配列に保存しておき
その配列の中で最も数が大きいもの
（操作後に出現する回数の多い数）
がXとなるとともに
その配列に入っている数字
（操作後に出現する回数）が答えになります。

つまりこの問題は
「X」を出してから
「ai=X なる i の個数の最大値」を出すのではなく
3つの操作を行ったときの
数字の出現回数から
「ai=X なる i の個数の最大値」を出す、
という流れで解きます。
（答えを出すためにXを求める必要はない）

流れのまとめ
①aiからaNに対して3つの操作を全て行い、それぞれの数字の出現した数をカウントして配列に保存
②出現する数を保存してある配列で最も大きい数字を出力

実装する

まずは
①aiからaNに対して3つの操作を全て行い、それぞれの数字の出現した数をカウントして配列に保存
を実装してみます。

実装してみると以下のような形になると思います。

var N = Int32.Parse(Console.ReadLine());
var a = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).OrderBy(x => x).ToArray();
//操作した後の数字が出現する回数を保存する配列
//0≤ai<10^5なので1を足すことを考えて10^5+1+1
var array = new int[100002];
//操作した数をカウントする
for (int i = 0; i < N; ++i)
{
    //1を引く
    array[a[i] - 1]++;
    //何もしない
    array[a[i]]++;
    //1を足す
    array[a[i] + 1]++;
}

しかし、
ここで一つ問題があります。
0≤ai<105なので
もしaiが０だった場合

//1を引く
array[a[i] - 1]++;

をしたときに
Indexの外にはみ出てエラーになってしまいます。

これを避けるために
問題文の操作の値をそれぞれ１を足し、
「各 1≤i≤N に対し、ai になにもしないか 、1 足すか、2 足すか、の三つの操作」
というように書き換えます。

なぜこれで
元の操作をした場合と同じ答えになるのかは分からないのですが
（他の記事にも見当たらなかった）
入力例で試してみても
同じ答えになることが分かります。

入力例1
7
3 1 4 1 5 9 2
足す数 ****** ****** ****** ****** ****** ****** ******
-1 2 0 3 0 4 8 1
+0 3 1 4 1 5 9 2
+1 4 2 5 2 6 10 3
+2 5 3 6 3 7 11 4

上の表で
緑色の部分が操作を問題文通りの「-1,+0,+1」でしたときに同じ数字になる箇所、
赤色の部分が操作の数字に1を足した「+0,+1,+2」でしたときに同じ数字になる箇所です。

出現する場所は変わらず、
Xが1大きい値にはなりますが
（Xの値は問題の答えを出す上で特に必要ないので、変わっても問題ない。）
求めたい答えの値は変わらないことが分かります。

そのため、
各aiに操作を加えてカウントする部分の処理は
以下のように書き換えることができます。

var N = Int32.Parse(Console.ReadLine());
var a = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).OrderBy(x => x).ToArray();
//操作した後の数字が出現する回数を保存する配列
//0≤ai<10^5なので2を足すことを考えて10^5+2+1
var array = new int[100003];
//操作した数をカウントする
for (int i = 0; i < N; ++i)
{
    //何もしない
    array[a[i]]++;
    //1を足す
    array[a[i] + 1]++;
    //2を足す
    array[a[i] + 2]++;
}


②出現する数を保存してある配列で最も大きい数字を出力

最後に数字の出現回数を保存しておいた配列の中で
最も大きい値（＝答え）を求め、
出力すれば完了です。

全体のコード

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

class Cmondai
{
    static void Main()
    {
        var N = Int32.Parse(Console.ReadLine());
        var a = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).OrderBy(x => x).ToArray();
        //操作した後の数字が出現する回数を保存する配列
        //0≤ai<10^5なので2を足すことを考えて10^5+2+1
        var array = new int[100003];
        //操作した数をカウントする
        for (int i = 0; i < N; ++i)
        {
            //何もしない
            array[a[i]]++;
            //1を足す
            array[a[i] + 1]++;
            //2を足す
            array[a[i] + 2]++;
        }
        //出現回数が最も多い値を取り出す
        var ans = array.Max();
        Console.WriteLine(ans);
    }
}

C - Bridge

競プロ DFS

はじめに

競技プログラミング、AtCoder Beginner Contest 75
C - Bridge
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

自己ループと二重辺を含まないN頂点M辺の無向連結グラフが与えられます。
i(1≦i≦M)番目の辺は頂点aiと頂点biを結びます。

グラフから辺を取り除いたとき、グラフ全体が非連結になるような辺のことを橋と呼びます。
与えられたM本のうち橋である辺の本数を求めてください。

・自己ループ とは、ai=bi(1≦i≦M)であるような辺iのことをいいます。
・二重辺 とは、ai=ajかつ bi=bj(1≦i<j≦M)であるような辺の組 i,jのことをいいます。
・無向グラフが 連結 であるとは、グラフの任意の二頂点間に経路が存在することをいいます。

制約

・2≦N≦50
・N−1≦M≦min(N(N−1)/2,50)
・1≦ai<bi≦N
・与えられるグラフは自己ループと二重辺を含まない。
・与えられるグラフは連結である。

入力

入力は以下の形式で標準入力から与えられる。

N M
a1 b1
a2 b2
:
aM bM

出力

M本の辺のうち、橋である辺の本数を出力せよ。

解き方

以下を参考にしています。
※この記事ではDFSを使用して解いています

https://img.atcoder.jp/abc075/editorial.pdf
提出 #4407450 - AtCoder Beginner Contest 075


この問題で答えるものは
「与えられるM本のうち「橋」がいくつあるか」です。

これを求めるためには、
それぞれの辺が「橋」かどうかを判定し
「橋」と判定されたものの数を数えればできます。

そのため、
どのようにすれば辺を「橋」かどうか判定できるかを考えます。

まず問題文から
「橋」とは
グラフから辺を取り除いたとき、グラフ全体が非連結になるような辺のこと
である、ということが分かります。

ここから、
１つの「辺」を取り除いた場合に
全ての頂点を辺を伝って訪問することができなければ
その「辺」は「橋」である
ということが言えそうです。

例えば、
入力例１では
頂点1と頂点3を繋ぐ辺をなくしてしまうと
頂点2,3,4,5,6,7からは辺を伝って頂点1に行くことができなくなるので
頂点1と頂点3を繋ぐ辺が「橋」だということが分かります。
f:id:aoaoaoaoaoaoaoi:20190430000115p:plain
↑頂点1と頂点3を繋ぐ辺を消すと全ての頂点には行き来できなくなる図

辺を一つ取り除き
その状態で各頂点を全て訪問できるかどうかで
辺が「橋」かどうかを判定します。

以下コードを見ながら進みます。
全体のコードは以下です。

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

class Cmondai
{
    struct Connection
    {
        public List<int> list;
        public Connection(int index)
        {
            list = new List<int>();
        }
    }

    static void Main()
    {
        var nm = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
        var N = nm[0];
        var M = nm[1];
        var a = new int[M];
        var b = new int[M];
        for (int i = 0; i < M; ++i)
        {
            var ab = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
            a[i] = ab[0];
            b[i] = ab[1];
        }

        var ans = 0L;
        for (int i = 0; i < M; ++i)
        {
            var connection = new Connection[N];
            for (int j = 0; j < N; ++j) connection[j] = new Connection(j);
            for (int j = 0; j < M; ++j)
            {
                if (i == j) continue;
                connection[a[j] - 1].list.Add(b[j] - 1);
                connection[b[j] - 1].list.Add(a[j] - 1);
            }
            var hashSet = new HashSet<int>();
            Dfs(hashSet, connection, 0);
            if (hashSet.Count() != N) ans++;
        }
        Console.WriteLine(ans);
    }
    static void Dfs(HashSet<int> hashSet, Connection[] connection, int index)
    {
        hashSet.Add(index);
        foreach (var l in connection[index].list)
        {
            if (!hashSet.Contains(l)) Dfs(hashSet, connection, l);
        }
    }
}

まず入力の格納は以下のようにしています。

var nm = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
var N = nm[0];
var M = nm[1];
var a = new int[M];
var b = new int[M];
for (int i = 0; i < M; ++i)
{
    var ab = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
    a[i] = ab[0];
    b[i] = ab[1];
}

辺を一つずつ消して橋かどうか判定しているのは以下の部分です。

//橋の数を入れる変数
var ans = 0L;
//一つずつ辺を消したいのでM回まわす
for (int i = 0; i < M; ++i)
{
    //構造体の初期化
    //connectionは各頂点の繋がりの情報を入れるもの
    //頂点はN個あるのでN個
    var connection = new Connection[N];
    for (int j = 0; j < N; ++j) connection[j] = new Connection(j);
    // i 番目の辺を削除した頂点どうしの繋がりを保存
    for (int j = 0; j < M; ++j)
    {
        // i 番目の辺が繋いでいる頂点の情報は保存しない
        if (i == j) continue;
        //辺がつなぐ頂点の情報を各頂点のリストに格納する
        connection[a[j] - 1].list.Add(b[j] - 1);
        connection[b[j] - 1].list.Add(a[j] - 1);
    }
    //訪問した頂点を格納する
    var hashSet = new HashSet<int>();
    //DFS
    Dfs(hashSet, connection, 0);
    //訪問した頂点の数がNと違うなら、
    //辺を消すことによって行けなくなった頂点があるということなので橋になる
    if (hashSet.Count() != N) ans++;
}

まずループの回数は
辺を一つずつ消していって
各頂点を全て訪問できるかどうかを知りたいので
辺の数と同じM回まわします。

//一つずつ辺を消したいのでM回まわす
for (int i = 0; i < M; ++i)
{
    …
}


次に各頂点の情報を入れる
connectionを初期化しています。
頂点の数はN個あるので
ここでは、N個初期化をしています。

//構造体の初期化
//connectionは各頂点の繋がりの情報を入れるもの
//頂点はN個あるのでN個
var connection = new Connection[N];
for (int j = 0; j < N; ++j) connection[j] = new Connection(j);


中のループでは i 番目の橋を消したときの
頂点どうしの繋がりを保存しています。
そのため、M回まわしています。

//各辺の頂点の繋がりを保存したいのでM回まわす
for (int j = 0; j < M; ++j)
{
    …
}


i 番目の橋を消したときの状態が欲しいので
i 番目の橋の情報は保存しないようにcontinueしています。

// i 番目の辺が繋いでいる頂点の情報は保存しない
if (i == j) continue;


connectionは各頂点の情報を入れるようになっていて
listには頂点が辺を通じてどこと繋がっているのか？
という情報を入れるようになっています。

//辺がつなぐ頂点の情報を各頂点のリストに格納する
connection[a[j] - 1].list.Add(b[j] - 1);
connection[b[j] - 1].list.Add(a[j] - 1);


以下の入力例1を例にすると

7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7

j ( ループのindex )が 0 のとき
頂点1のconnection[0].listには2
頂点3のconnection[2].listには0
がそれぞれ入ります。

j ( ループのindex )が 1 のとき
頂点2のconnection[1].listには6
頂点7のconnection[6].listには2
がそれぞれ入ります。

これを橋かどうか判定したい辺を除いて繰り返します。
上を見ると分かるように
indexは実際の頂点の番号とは１ずれたものを使用しています。

Dfs関数の中身は以下のようになっています。

static void Dfs(HashSet<int> hashSet, Connection[] connection, int index)
{
    //訪問した頂点をhashSetに保存する
    hashSet.Add(index);
    //connectionのlistに保存してある頂点を順番に訪問する
    foreach (var l in connection[index].list)
    {
        //hashSetに保存されていない頂点はまだ訪問していないので再帰処理をする
        if (!hashSet.Contains(l)) Dfs(hashSet, connection, l);
    }
}

Dfs関数の中でしていることは以下の２つです。
①訪問した頂点をhashSetに保存する
②connection.listから繋がりのある頂点を取り出し、順番に各頂点を訪問する

各頂点の繋がり追っていけば、
繋がりのある頂点は全てhashSetに保存されます。

Dfs関数を呼んだ後でhashSetにはいくつの頂点が保存されているのかをみれば
情報を保存しなかった辺が橋なのかどうかを判定することができます。

頂点は全部でN個あるので
hashSetにN個の値が入っていなければ
訪問できなかった頂点があるということになるので
情報を保存しなかった辺は橋であるということになります。

最後に橋の数を出力します。

全体のコード

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

class Cmondai
{
    struct Connection
    {
        public List<int> list;
        public Connection(int index)
        {
            list = new List<int>();
        }
    }

    static void Main()
    {
        var nm = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
        var N = nm[0];
        var M = nm[1];
        var a = new int[M];
        var b = new int[M];
        for (int i = 0; i < M; ++i)
        {
            var ab = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
            a[i] = ab[0];
            b[i] = ab[1];
        }

        //橋の数を入れる変数
        var ans = 0L;
        //一つずつ辺を消したいのでM回まわす
        for (int i = 0; i < M; ++i)
        {
            //構造体の初期化
            //connectionは各頂点の繋がりの情報を入れるもの
            //頂点はN個あるのでN個
            var connection = new Connection[N];
            for (int j = 0; j < N; ++j) connection[j] = new Connection(j);
            // i 番目の辺を削除した頂点どうしの繋がりを保存
            for (int j = 0; j < M; ++j)
            {
                // i 番目の辺が繋いでいる頂点の情報は保存しない
                if (i == j) continue;
                //辺がつなぐ頂点の情報を各頂点のリストに格納する
                connection[a[j] - 1].list.Add(b[j] - 1);
                connection[b[j] - 1].list.Add(a[j] - 1);
            }
            //訪問した頂点を格納する
            var hashSet = new HashSet<int>();
            //DFS
            Dfs(hashSet, connection, 0);
            //訪問した頂点の数がNと違うなら、
            //辺を消すことによって行けなくなった頂点があるということなので橋になる
            if (hashSet.Count() != N) ans++;
        }
        Console.WriteLine(ans);
    }
    static void Dfs(HashSet<int> hashSet, Connection[] connection, int index)
    {
        //訪問した頂点をhashSetに保存する
        hashSet.Add(index);
        //connectionのlistに保存してある頂点を順番に訪問する
        foreach (var l in connection[index].list)
        {
            //hashSetに保存されていない頂点はまだ訪問していないので再帰処理をする
            if (!hashSet.Contains(l)) Dfs(hashSet, connection, l);
        }
    }
}

C - Sugar Water

競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 74
C - Sugar Water
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

すぬけ君はビーカーに砂糖水を作ろうとしています。 
最初ビーカーは空です。
すぬけ君は以下の4種類の操作をそれぞれ何回でも行うことができます。
一度も行わない操作があっても構いません。

・操作 1: ビーカーに水を100A[g] 入れる。
・操作 2: ビーカーに水を100B[g] 入れる。
・操作 3: ビーカーに砂糖をC[g] 入れる。
・操作 4: ビーカーに砂糖をD[g] 入れる。

すぬけ君の実験環境下では、水100[g] あたり砂糖はE[g] 溶けます。

すぬけ君はできるだけ濃度の高い砂糖水を作りたいと考えています。

ビーカーに入れられる物質の質量 (水の質量と砂糖の質量の合計)がF[g] 以下であり、
ビーカーの中に砂糖を溶け残らせてはいけないとき、 
すぬけ君が作る砂糖水の質量と、それに溶けている砂糖の質量を求めてください。 
答えが複数ある場合はどれを答えても構いません。

水a[g] と砂糖b[g] を混ぜた砂糖水の濃度は100ba+b[%]です。 
また、この問題では、砂糖が全く溶けていない水も濃度0[%] の砂糖水と考えることにします。

制約

・1≦A<B≦30
・1≦C<D≦30
・1≦E≦100
・100A≦F≦3,000
・A,B,C,D,E,Fはすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

A B C D E F

出力

整数を空白区切りで2つ出力せよ。 
1つ目は求める砂糖水の質量、
2つ目はそれに溶けている砂糖の質量とせよ。

解き方

以下を参考にしています。
https://img.atcoder.jp/arc083/editorial.pdf

考える要素が多いことと
「制約」を見るとどれも数が小さいので
どこから手を付けていいのか分からなくなりますが
この問題では
「砂糖水の量」と「ビーカーに入れられる物質の質量の上限（F）」に
注目すると解くことができます。

まず、
ビーカーに入れる水の量を式であらわすと以下のようになります。
ビーカーにAを入れる回数（操作１をする回数）を「i」とする
ビーカーにBを入れる回数（操作２をする回数）を「j」とする

(A*100)*i+(B*100)*j


また、
ビーカーに入れる砂糖の量を式であらわすと以下のようになります。
ビーカーにCを入れる回数（操作３をする回数）を「k」とする
ビーカーにDを入れる回数（操作４をする回数）を「l」とする

(C*100)*k+(D*100)*l


そして、
「ビーカーに入れる水の量」と「ビーカーに入れる砂糖の量」は
「ビーカーに入れられる物質の質量の上限（F）」を超えることはないので
以下の式が成り立ちます。

(A*100)*i+(B*100)*j+(C*100)*k+(D*100)*l<=F


この式を利用して４重のループを回します。
一番外側のループをA、
二番目のループをB、
三番目をC、
四番目をDとすると以下のようになります。

・A（ループのindexは「i」）
「i」が取り得る値は「０～( F / ( A×100 ))」

「( F / ( A×100 ))」は
ビーカーに入れられる物質の質量の中で
Aを最大まで入れようとした時の値


・B（ループのindexは「j」）
「j」が取り得る値は「０～( F - ( A × i × 100 )) / ( B × 100 )」

「(F - ( A × i × 100 )) / ( B × 100 )」は
ビーカーに入れられる物質の質量の中から
Aが入っている量を除いて
Bを最大まで入れようとした時の値


・C（ループのindexは「k」）
「k」が取り得る値は「０～( F - ( A × i × 100 + B × j × 100 )) / C」

「( F - ( A × i × 100 + B × j × 100 )) / C」は
ビーカーに入れられる物質の質量の中から
AとBが入っている量を除いて
Cを最大まで入れようとした時の値


・D（ループのindexは「l」）
「l」が取り得る値は「０～ ( F - ( A × i × 100 + B × j × 100 + C )) / D」

「( F - ( A × i × 100 + B × j × 100 + C )) / D」は
ビーカーに入れられる物質の質量の中から
AとBとCが入っている量を除いて
Dを最大まで入れようとした時の値

これをコードにすると以下のようになります。

//A
//AがFを上限として最大まで入れられる回数
var waterAmax = F / (A * 100);
for (int i = 0; i <= waterAmax; ++i)
{
     //B
     //BがFを上限として最大まで入れられる回数
    var bCount = (F - (A * i * 100)) / (B * 100);
    for (int j = 0; j <= bCount; ++j)
    {
        //水が入っていないことはあり得ない(砂糖が溶け残る場合はNG)ので「i」と「j」がどちらも０だった場合はcontinueする
        if (i == 0 && j == 0) continue;

        //C
        //CがFを上限として最大まで入れられる回数
        var cCount = (F - (A * i * 100 + B * j * 100)) / C;
        for (int k = 0; k <= cCount; ++k)
        {

            //D
            //DがFを上限として最大まで入れられる回数
            var dCount = (F - ((A * i * 100 + B * j * 100) + C * k)) / D;
            for (int l = 0; l <= dCount; ++l)
            {
                //処理
            }
        }
    }
}

Bのループの中で
Aのループのindexである「i」と
Bのループのindexである「j」が
どちらも「０」だった場合に
continueをしています。

これは、
問題文から
砂糖を溶け残るパターンは省かなければいけないからです。
（水がなければ必ず砂糖だけになってしまう）

コードの中の「//処理」の部分に到達するものは
「ビーカーの中の物質の質量」がF以下のものなので
この中からさらに
砂糖が溶け残るパターンを除いて、
濃度を出し
保存していた濃度よりも高ければ
値を書き換えるということを
行えば問題の答えがでます。

//砂糖が溶け残らないかどうか
 if ((C * k + D * l) <= (i*A + j*B) * E)
{
     //砂糖水の量
     var sugarWater = (A * i)*100 + (B * j)*100 + C * k + D * l;
    //砂糖の量
    var sugar = C * k + D * l;

    //濃度
    var concentration = sugar == 0 ? 0 : sugar / sugarWater * 100;

    //濃度が保存してあるものよりも高ければ情報を書き換える
    if (max < concentration)
    {
        max = concentration;
        maxSugarWater = sugarWater;
        maxSugar = sugar;
        }
    }

全体のコード

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

class Cmondai
{
    static void Main()
    {
        var line = Console.ReadLine().Split(' ').Select(x => decimal.Parse(x)).ToArray();
        var A = line[0];
        var B = line[1];
        var C = line[2];
        var D = line[3];
        var E = line[4];
        var F = line[5];

        //濃度（濃度を保存しておく変数）
        decimal max = -1;
        //砂糖水の量（砂糖水の量を保存しておく変数）
        decimal maxSugarWater =0;
        //砂糖の量（砂糖の量を保存しておく変数）
        decimal maxSugar = 0;

        //A
        //AがFを上限として最大まで入れられる回数
        var waterAmax = F / (A * 100);
        for (int i = 0; i <= waterAmax; ++i)
        {
            //B
            //BがFを上限として最大まで入れられる回数
            var bCount = (F - (A * i * 100)) / (B * 100);
            for (int j = 0; j <= bCount; ++j)
            {
                //水が入っていないことはあり得ない(砂糖が溶け残る場合はNG)ので「i」と「j」がどちらも０だった場合はcontinueする
                if (i == 0 && j == 0) continue;

                //C
                //CがFを上限として最大まで入れられる回数
                var cCount = (F - (A * i * 100 + B * j * 100)) / C;
                for (int k = 0; k <= cCount; ++k)
                {

                    //D
                    //DがFを上限として最大まで入れられる回数
                    var dCount = (F - ((A * i * 100 + B * j * 100) + C * k)) / D;
                    for (int l = 0; l <= dCount; ++l)
                    {

                        //砂糖が溶け残らないかどうか
                        if ((C * k + D * l) <= (i*A + j*B) * E)
                        {
                            //砂糖水の量
                            var sugarWater = (A * i)*100 + (B * j)*100 + C * k + D * l;
                            //砂糖の量
                            var sugar = C * k + D * l;

                            //濃度
                            var concentration = sugar == 0 ? 0 : sugar / sugarWater * 100;

                            //濃度が保存してあるものよりも高ければ情報を書き換える
                            if (max < concentration)
                            {
                                max = concentration;
                                maxSugarWater = sugarWater;
                                maxSugar = sugar;
                            }
                        }
                    }
                }
            }
        }
        Console.WriteLine($"{maxSugarWater} {maxSugar}");
    }
}