AtCoder ABC197

ABC197参加しました。

atcoder.jp

 

A - Rotate

文字列sを読み込んで、s[1] + s[2] +s[0]するだけ

解説 - AtCoder Beginner Contest 197

B - Visibility

以下のような入力を例にして考えてみます。 二重丸の位置が(X,Y)の位置とします。空白に'.'があると思ってください。 そこから上下左右に'.'のマスを、#に当たるまで数えます。 開始位置を重複して数えたりしないようにしましょう。

f:id:umem0chi:20210328001255p:plain
ABC197B

解説 - AtCoder Beginner Contest 197

C - ORXOR

bit全探索問題です。 bit全探索はビット演算 (bit 演算) の使い方を総特集! 〜 マスクビットから bit DP まで 〜 - Qiita が詳しかったです。

今回の場合は、$ A_i $を横一列に並べて、各$ A_i $ の間にしきいを入れて区間を作ります。

f:id:umem0chi:20210328003706p:plain
ABC197C

上の図で、^が書かれている部分に敷居(0か1)を入れます。1は敷居が立っています。 なお、端は必ず敷居が入るので1です。

例えば以下の場合は、区間は[$ A_0, A_1$ ],[$A_2$]になります

f:id:umem0chi:20210328003723p:plain
ABC197C-例

この敷居が立つか立たないかをbit全探索します。探索の最大回数は、敷居の数になりますが、今回だと、両端が1で固定なので、最大でも $ 2^{19} = 524288 $ となり、十分間に合います。

bit全探索はなれるまでちょっとコードを書くのが大変です。 決まった区間のORの値は配列に入れておきます。

for (int bit = 0; bit < (1 << n - 1); ++bit)
{
    //今のしきいの位置
    int th = 0;//初期値は現在の右端。初期値は最右端(A0の右)
    for (int i = 0; i <= n - 1; ++i)
    {
        //iはA[i-1], A[i]の間の敷居
        if ((bit & (1 << i)) != 0)
        {
             //[th, i+1]までが区間なので、この区間の数値のORを取る

              //区間の右端を更新
              th = i + 1;
        }
    }
    //最後の区間[th, 最左端]の計算

    //各区間のXORを取る

    ans = Math.Min(ans, /*XOR結果*/);//答えをメモ
}

解説 - AtCoder Beginner Contest 197

D - Opposite

CGを勉強していたり、高校数学で行列の勉強をしていたら、回転行列について習ったかもしれませんが、今回はそれの練習問題みたいな感じでした。

各点は$ p_0, p_{N/2}$を結ぶ直線の中心位置$ p_c$を円の原点とした円周上に存在します。 また、点は正$N$角形なので、等間隔に配置されているため、$ \angle p_i p_c p_{i+1}$の値はすべて等しいです。

よって、$ p_0$ から一定角度($ 360/ N$ )だけ、$ p_c $を中心に回転させることで、$ p_1 $が出てきます。

回転行列はそのままだと原点(0,0)中心の回転なので、$ p_0 $が乗る円を原点まで並行移動(=$ p_c $を原点まで移動)して、回転を適用、最後に原点への平行移動分を取り消すように移動させないといけません。

以下がわかりやすかったです。
Opposite [AtCoder Beginner Contest 197(Sponsored by Panasonic) D] - はまやんはまやんはまやん

解説 - AtCoder Beginner Contest 197

まとめ

実装がめんどくさかった問題が多いですね。幾何のライブラリを作るべきか悩みます。

AtCoder ABC196

ABC196参加しました。

atcoder.jp

 

A - Difference Max

区間[A,B]の中の値x, 区間[C,D]の中の値yで$x-y$の最大値を出す問題。 各区間の端っこ同士の値を使う。 途中で考えるのが面倒になって、結局

int ans = Max(ans, C-B);
ans = Max(ans, ...);
...

みたいに全探索してやった。 解説 - AtCoder Beginner Contest 196

B - Round Down

与えられた長~い数値は文字列として受け取り、小数点の位置を検索。 小数点位置があれば、文字列の頭からその位置までを切り取って出力します。 見つからないなら、そのまま出力します。

解説 - AtCoder Beginner Contest 194

C - Doubled

コツは、「後半の数字だけを決めて、前半にコピーする」ことで、これで必ず前半後半の桁が一致して、全体が偶数桁になります。また、コピーしているので、前半後半が一致するのも確定。 これだと後半の桁は最大でも 106 なので、十分全探索で間に合います。 以下のような感じ。

i = 1;//後半の数
while (i <= n)
{
    s = i.ToString() + i.ToString();//後半の数値を前半にコピーして、
    check = long.Parse(s);//チェックする数を決める
    if(check > n) { break; }//チェックする数がnより大きかったら、もう見ても意味がない
    ans++;//答えが一つ決まった
    ++i;//後半の数を一つ増加
}

解説 - AtCoder Beginner Contest 194

D - Hanjo

DFS問題だということに気がつけなかった。修行が足りない... 公式の動画解説がとてもわかりやすいです。

左上のマスから開始して、そのマスに対して、

  1. 半畳を置いたと仮定する
  2. 1畳横置きしたと仮定する
  3. 1畳縦置きしたと仮定する

として、次のマスを見ていきます。 全マスを見たら、畳の敷き詰めパターンが一つ確定します。 途中で残りの畳がなくなったら、そのパターンの敷き詰めはできません。 公式動画のコードをコメント付きで実装してみたら以下の様になりました。

//見たいマス(h,w), 残りの畳枚数(a,b)
public int dfs(int h, int w, int a, int b)
{
    int res = 0;//敷き詰めパターン数
    if(a < 0 || b < 0) { return 0; }//畳がない。。。このパターンの敷き詰め失敗
    if(w == W){//右端まで見たら、次の段に
        w = 0;  h = h + 1;
    }
    if(h == H) {//全マス見た
        return 1;//全マス埋める置き方が1パターン確定した
  }
    if(Masu[h,w] == true){//もう置いてある
        //次のマスにいく
        return dfs(h, w + 1, a, b);
    }

    //とりあえず今見ているマスは畳をおく
    Masu[h, w] = true;
    //半畳
    res += dfs(h, w + 1, a, b - 1);//右隣の畳を探索していく
    //1畳を横に置く場合
    if(w + 1 < W && Masu[h,w+1] == false){
        Masu[h, w + 1] = true;//とりあえず横置きしてみて
        res += dfs(h, w + 1, a - 1, b);//次のマスへ
        //残りのマスの置き方はこのコードに来たときに確定しているので
        Masu[h, w + 1] = false;//未確定に戻す
    }
    //1畳を縦に置く場合
    {
        //横とほぼ同じなので省略
    }
    
    Masu[h, w] = false;//未確定に戻す
    return res;

DFSは慣れないと書きにくいですが、メインの処理(今回なら半畳を置くパートから)を書いて、例外処理やエラー処理、終了処理をメソッドの頭に後で置くとやりやすい気がします。

まとめ

DFSがさっと書けたら、多分もっとレート上がるはず。

AtCoder ABC194

ABC194参加しました。

atcoder.jp

 

A - I Scream

似たような用語がたくさんあってややこしいですね... ただ、問題自体はifを列挙すればいいだけです。

解説 - AtCoder Beginner Contest 194

B - Job Assignment

タスクAに挑む人を一人仮で決めた状態でタスクBに挑む人を選んで、かかる時間を計算していく総当り法

解説 - AtCoder Beginner Contest 194

C - Squared Error

素直に解いたら, forの二重ループになります。これは$\mathcal{O}{(N^{2})} $ オーダーで間に合いません。 この手の数式の値を求めろ、のようなシンプルな問題は、まず式変形を考えてます(それ以外にヒントもないので...)。 N=4の場合は

$$ \begin{align} \sum_{i=2}^{4} \sum_{j=1}^{i-1} { (A_{i}-A_{j})^{2}} &= (A_{2} - A_{1})^{2}\\ &+ (A_{3} - A_{1})^{2} + (A_{3} - A_{2})^{2} \\ &+ (A_{4} - A_{1})^{2} + (A_{4} - A_{2})^{2} + (A_{4} - A_{3})^{2}\\ &= A_{2}^{2} -2A_{2}A_{1} + A_{1}^{2}\\ &+ A_{3}^{2} -2A_{3}A_{1} + A_{1}^{2} + A_{3}^{2} -2A_{3}A_{2} + A_{2}^{2}\\ &+ A_{4}^{2} -2A_{4}A_{1} + A_{1}^{2} + A_{4}^{2} -2A_{4}A_{2} + A_{2}^{2} + A_{4}^{2} -2A_{4}A_{3} + A_{3}^{2}\\ &= 3(A_{1}^{2} + A_{2}^{2} + A_{3}^{2} + A_{4}^{2}) - 2(A_{1}(A_{2} + A_{3} + A_{4}) + A_{2}(A_{3} + A_{4}) + A_{3}A_{4}) \end{align} $$

となります。 式の最後に着目すると、第一項目は$\mathcal{O}(N) $ です。第二項目は

long diff = 0;
long sum = Aの総和
for(int i = 0; i < Aのサイズ-1; ++i)
{
    t -= A[i];
    diff += A[i] * t;
}

みたいに計算します。最初に累積和を取ると、計算が早いです。一般化すれば $$ (N-1)(A_{1}^{2} + A_{2}^{2} + ...) - 2(A_{1}(A_{2} + ... + A_{N}) + A_{2}(A_{3} + ... + A_{N}) + ... + A_{N-1}A_{N}) $$ となるでしょうか。

公式解説のように、出てくる値の制約条件を使って解く方法もあるようです。 解説 - AtCoder Beginner Contest 194

D - Journey

コンプガチャ問題。 マス目をガチャの景品と置き換えると、景品を全部手に入れるまでの期待値を計算することになります。(最初から景品は一つ入手済み、かつ、全景品は等確率で排出される)

コンプガチャに必要な回数の期待値の計算 | 高校数学の美しい物語にありますが、ここと違うのは、最初から一つ景品を入手済みであること。

公式解説にもある通り「確率 $p(p≠0)$ で成功する試行を、成功するまで行うときの試行回数(最後の成功した回も含む) の期待値は $1/p$ である。」を利用します。なんでこうなるかは後ほど説明。

このとき、結局全部の景品を取るまでの期待値なので、景品数4つの場合は

  1. 1回目は$3/4$ の確率で新しいのがでる。逆に、$ 1/4 $の確率で外れ(いままで入手したのと同じもの)
  2. 2回目は$2/4$ の確率で新しいのがでる。逆に、$ 2/4 $の確率で外れ(いままで入手したのと同じもの)
  3. 最終回は$1/4$ の確率で新しいのがでる。逆に、$ 3/4 $の確率で外れ(いままで入手したのと同じもの)

となります。つまり一般化すると、

  1. 1回目は$(N-1)/N$ の確率で新しいのがでる。逆に、$ 1/N $の確率で外れ(いままで入手したのと同じもの)
  2. 2回目は$(N-2)/N$ の確率で新しいのがでる。逆に、$ 2/N $の確率で外れ(いままで入手したのと同じもの)
  3. (繰り返し)
  4. 最終回は$1/N$ の確率で新しいのがでる。逆に、$ (N-1)/N $の確率で外れ(いままで入手したのと同じもの)

です。i回目の期待値は最初に書いたとおり、成功する確率の逆数になるので、$(N-i)/N$です。これをforで足し合わせていきます。

double ans = 0.0;
for(int i = N-1; i >= 1; --i)
{
   ans += 1.0 / ((double)i / (double)N);
}

Journey [AtCoder Beginner Contest 194 D] - はまやんはまやんはまやん

冒頭の定理(あたり確率の逆数が期待値になる)ですが、「幾何分布の期待値」になります。

公式解説動画でも解説してますが、Python で解く AtCoder M-SOLUTION プロコンオープン C - owlogとか、幾何分布とは?期待値(平均)や分散の証明はどうなってる?|いちばんやさしい、医療統計でも解説してます。

備忘録がてら書いておきます。期待値を$E$とすると、以下が成立します(成立過程はここから)

$$
\begin{align} E &= \sum_{n=1}^{\infty}{np(1-p)^{n-1}}\\ &= p \sum_{n=1}^{\infty}{n(1-p)^{n-1}}\\ &= p (1 + 2(1-p) + 3(1-p)^{2} + ... ) \end{align} $$

ここで$E$に$1-p$を掛けて

$$ (1-p)E = p ((1-p) + 2(1-p)^{2} + ... ) $$

なので、

$$ \begin{align} E-(1-p)E &= p (1+(1-p) + (1-p)^{2} + ... )\\ pE &= p \sum_{n=1}^{\infty} {(1-p)^{n-1}} \\ E &=\sum_{n=1}^{\infty} {(1-p)^{n-1}} \end{align} $$

あとは無限等比級数の公式から

$$ \begin{align} E &= \frac{1}{1-(1-p)} \\ E &= \frac{1}{p} \end{align} $$

となります。

まとめ

今回は結果さえ知っていれば解けましたが、やっぱり確率は苦手。

AtCoder ABC191

ABC191参加しました。

atcoder.jp

 

A - Vanishing Pitch

特に難しくもないでしょう。消える区間をV,Tから計算して、Dと比較すればいいです。
解説 - AtCoder Beginner Contest 191

B - Remove It

大抵の言語にはList.RemoveAll()みたいなメソッドが実装されていると思うので、入力を受け取ったら後はそれを呼ぶだけ。

解説 - AtCoder Beginner Contest 191 

C - Digital Graffiti

問題文がちょっと読み解けなかったです。

T字型なら何角形なのか? G(うずまき)型なら?

で、chokudaiさんがtwitterでも述べておりますが、T字は8角形とのこと。

つまり、グリッドの中心だけではなく、その角や辺まで考えないといけないという問題でした。

ここでは、他にも例があったことが書かれています。
この2例があったら、たしかに分かりやすかった。

結局、問題は、図形での頂点の数を数えるということになり、さて頂点とはなにか、を考える必要が出てきます。

これは公式の回答がもうずばりなのですが、あるマスの周囲4マスにある黒マスの数が1,3だったら、頂点となります。

解説 - AtCoder Beginner Contest 191  

D - Circle Lattice Points

鬼門。コンテスト後も延々と計算誤差に苦しめられた。

作問側でもいろいろあったんですね。

f:id:umem0chi:20210211153835p:plain

ナイーブな解き方だと、単純に円に外接する正方形に対してfor文でy方向にぶん回して、正方形内部の格子点が円の内部にあるかを計算する方法があります。
もう少しスマートに考えると、円に外接する正方形に対してfor文でy方向にぶん回して、上のように外接する矩形の矩形の両端から回していって、円の両端を求める方法があります。両端がわかればその点の間の格子点も $ X_r - X_l$ で出せます。 ただ円の半径がお大きい場合にTLEになる可能性があります。

私は円と直線 $ y=d $ の交点を連立方程式で解く方法を選びました。 f:id:umem0chi:20210211154316p:plain

なお公式の回答だと、三平方の定理で解いてますが、どっちでも式が似通って同じ結果になります。

f:id:umem0chi:20210211154319p:plain

なお上の方法は、交点は格子点ではなく小数付きで厳密に出てくるので、丸めも必要です。

何が鬼門かというと、この問題は計算誤差の取り扱いが大変で、公式回答でも言われているように、入力を104倍して整数にしないと計算誤差で苦しめられる恐れがあります。

私はC#で解いていましたからdecimal型を使えてちょっとは楽だったかもしれません が、それでも円と直線の交点を小数で求めた後、格子点に丸めていくときのceil,floorの整数点への丸めを考えるのが面倒だったり、あとMath.Sqrt()を使ったんですが、Math.Sqrt()はdecimal -> doubleに直さないと使えないので、decimalを使って高精度な計算をしていた意味がdoubleへの変換でなくなってしまったためか、提出後にサンプルが2つだけ通らないという最悪なパターンになりました。(これはめんどくさいやつ...)

余談ですが、decimalのMath.Sqrt()に対する以下のような記事が。
Performing Math operations on decimal datatype in C#? - Stack Overflow
まずそもそもSqrt()はdecimalには使えず、使いたいならdoubleにキャストして無理やり使うこともできますが、そもそもそれだとdecimalからdoubleに直したせいで精度が下がるので、decimalを使っていた意味が薄れます。よりよい求め方として、求めた解を更にNewton法で高精度に解を洗練させていくことで、decimal->doubleに直したときの精度低下を補っていくほうがいいですね。

参考までに比較してみました。 Newton法のコードは上のサイトのものを使用。
環境は C#.Net Core 3.1です。

$ \sqrt {2} $ を計算してみます。

    public static void calcSqrt2()
    {
        //例: Sqrt(2)= 1.414213 562373 095048 801688 724209 698078 569671 875376...
        double input = 2.0;

        //1. 通常のSqrt
        Console.WriteLine(Math.Sqrt(input));//1.414213 562373 1 

        //2. 初期値として上の数をdoubleで与えて、Decimalに直してNewton法で高精度化した
        Console.WriteLine(Sqrt((decimal)input));//1.414213 562373 095048 801688 7242

        //2-a. Newton法の部分を全部doubleでやっても、まず変わらない
        Console.WriteLine(Sqrt_double(input));//1.414213 562373 09
    }

    /// <summary>
    /// Sqrtの計算
    /// Newton法で高精度化
    /// </summary>
    /// <param name="x"></param>
    /// <param name="epsilon"></param>
    /// <returns></returns>
    public static decimal Sqrt(decimal x, decimal epsilon = 0.0M)
    {
        if (x < 0) throw new OverflowException("Cannot calculate square root from a negative number");
        decimal cur = (decimal)Math.Sqrt((double)x);//初期値
        decimal prev;
        do
        {
            prev = cur;
            if (prev == 0.0M) return 0;
            cur = (prev + x / prev) / 2
        }
        while (Math.Abs(prev - cur) > epsilon);//更新しても変化が十分なくなるまですすめる
        return cur;
    }
    /// <summary>
    /// 上を全部doubleでしてみる版
    /// </summary>
    /// <param name="x"></param>
    /// <param name="epsilon"></param>
    /// <returns></returns>
    public static double Sqrt_double(double x, double epsilon = 0.0)
    {
        if (x < 0.0) throw new OverflowException("Cannot calculate square root from a negative number");
        var cur = Math.Sqrt(x);//初期値
        var prev = 0.0;
        do
        {
            prev = cur;
            if (prev == 0.0) return 0;
            cur = (prev + x / prev) / 2;
        }
        while (Math.Abs(prev - cur) > epsilon);
        return cur;
    }

Newton法の部分でdecimalを使用することで、結果はより高精度になります。

また、

Mathクラス(C#) - 超初心者向けプログラミング入門

にあるように、負の数に対するMath.Floor(), Math.Ceilingの取り扱いをあまりしたことがなかったので、勉強になりました。C#の場合ですが、ちょっとまとめてみましょう。

    public static void compareRounding()
    {
        //切り捨て(現在の値以下で最大の整数, よって常に数値は小さくなる)
        Console.WriteLine("Math.Floor");
        Console.WriteLine(Math.Floor(3.14));//3
        Console.WriteLine(Math.Floor(-3.14));//-4

        //切り上げ(現在の値以上で最小の整数, よって常に数値は大きくなる)
        Console.WriteLine("Math.Ceiling");
        Console.WriteLine(Math.Ceiling(3.14));//4
        Console.WriteLine(Math.Ceiling(-3.14));//-3

        //小数点以下を捨てる
        Console.WriteLine("Math.Truncate");
        Console.WriteLine(Math.Truncate(3.14));//3
        Console.WriteLine(Math.Truncate(-3.14));//-3

        //切り捨て(0に近づける) => Math.Truncateと同じ
        Console.WriteLine("FloorTowardsZero");
        Console.WriteLine(FloorTowardsZero(3.14));//3
        Console.WriteLine(FloorTowardsZero(-3.14));//-3

        //切り上げ(0から遠ざける)
        Console.WriteLine("CeilingAwayFromZero");
        Console.WriteLine(CeilingAwayFromZero(3.14));//4
        Console.WriteLine(CeilingAwayFromZero(-3.14));//-4
    }

    /// <summary>
    /// 切り捨て(原点に近づくように)
    /// </summary>
    public static double FloorTowardsZero(double a)
    {
        //return a > 0 ? Math.Floor(a) : -Math.Floor(-a);
        return Math.Truncate(a);
    }

    /// <summary>
    /// 切り上げ(原点から離れるように)
    /// </summary>
    public static double CeilingAwayFromZero(double a)
    {
        return a > 0 ? Math.Ceiling(a) : -Math.Ceiling(-a);
    }

ここで自作したのは、今回のコンテストで使ったもの。てっきりMath.Ceiling(), Math.Floor()の負数の挙動は自作した方の挙動になると思ってました...

解説 - AtCoder Beginner Contest 191

動画の解法のほうが計算誤差に悩まされないかもしれない。

まとめ

ABCにしては難しかった気がします。
が、まあ、勉強にはなった。

AtCoder ABC190

ABC190参加しました。

atcoder.jp

atcoder.jp

 

A - Very Very Primitive Game

いつものAにしてはややこしかった気がする。条件をしっかり場合分けして解く必要があります。
詳しくは公式の解説をどうぞ。

Editorial - AtCoder Beginner Contest 190

B - Magic 3

ゲームみたいですね。与えられた条件からして、それぞれの呪文をfor文で回して

  • 詠唱時間S以下
  • 威力Dより上

のものが存在すればダメージが与えられます。それを実装するだけ。

 

C - Bowls and Dishes

絵に書いて考えてみると、お皿の上にボールを載せていって、条件に当てはまるものの数を数えていく必要があります。

このときボールを乗せるK人の人は、それぞれの人が2枚の皿のうちどちらかを選んで載せていきます。

与えられた数値の上限が小さいので、K人の人がボールをさらに乗せる組み合わせは,

 1 \le K \le 16なので、最大でも $2^{16} = 65536 $ です。

bit全探索で、まずボールの組み合わせを決定し、ボールをお皿においたら、そのとき満たされる条件がいくつあるかを調べればいいです。
ビット演算 (bit 演算) の使い方を総特集! 〜 マスクビットから bit DP まで 〜 - Qiita  

D - Staircase Sequences

問題文が短くてきれいですね。こういうのは難問な気がする。 与えられた入力例を見てみると、どうも約数が決め手になる気がしてきます。入力例1の12とか、(3,4,5)はまさにそれですね。

公式回答や、その他いろんなブログを見ていったりした結果を解説してみます。

まず、等差数列で公差1の場合を考えてみると、初項$a$, 項数$L$ とすると、総和$ N $は

$$ N = \frac{L(2a+L - 1 ) }{2} $$

となります。式変形して、

$$ L(2a+L - 1 )=2N $$ です。このことから、$2N$の約数の中に、答えとなる数列の項数$L$の情報が入っていることがわかります。

つまり、この$L$に対応する初項$a$を決定すれば、答えの数列が一つ決定することになります。実際に上の式を$a$について求めてみると

$$ a=\frac{ \frac{2N}{L}-L+1}{2} $$

となります。このとき重要なこととして

  1. $\frac{2N}{L}-L+1$は偶数である
  2. $\frac{2N}{L}$は割り切れる

という条件があります。
1.は$a$は整数という性質があるためです。となると1.の分子は偶数でないといけません。
2.は、$\frac{2N}{L}$が割り切れない場合は、そもそも$L$は$2N$の約数ではないですね。
なので、2は$2N$の約数として$L$を算出すると明らかに満たされています。

つまり、求めた$2N$の約数の中(これは$L$の候補)に、条件1を満たすものがあれば、初項$a$も自動的に決定される(初項$a$が何なのかは知る必要がなく、決定されたことが大事です)ため、答えの数列が1つ決定されます。

大雑把には以下のような感じ? 約数列挙のメソッドがあると早いです。

long n2 = 2 * n;
Action<long> check = (l) =>
{
    //条件1の判定
    long t = n2 / l - l + 1;
    if(Math.Abs(t) % 2 == 0){ ans++; }
};
var ls = calcDivisor(n2);//約数列挙メソッド
foreach(var x in ls) { 
    check(x);//xが回答候補の数列の長さ
}

まとめ

全般的に難しかった気がします。