G4NP0Nのブログ

競プロとそれ以外のことについてしゃべります。

ABC198 参加記&解法メモ

f:id:G4NP0N_kyopro:20210411230853p:plain

47分2ペナ5完で271位でした。黄パフォAGCで溶かしたレートを取り返したぜ。

 

atcoder.jp

A - Div

Aくんが得るお菓子の個数が1個,2個,…,N-1個となるので、答えはN-1通りとなります。

B - Palindrome with leading zeros

先頭に0をつけることで回文にできる→末尾の0を削除することで回文にできる、という言い換えは典型っぽい。入力を反転して0の間文字を消去してできる文字列が回文かどうか判定すればいいです。

文字列の回文判定は反転した文字列が元のものと等しいかをチェックすればいいんですが、毎回忘れてて普通にfor文で前後から見てチェックしちゃう……。

C - Compass Walking

幾何に見せかけた誤差問題に見せかけた知識&コーナーケース問題。

とりあえずまっすぐ近づいていくことを考える。もし通り越してしまう場合は,途中で少し遠回りすることで目標の座標にピッタリ到着することができます。これは知識というか経験で知っていたんですが、サンプル3を見れば初見でも思いつけそう?

nR>=√X^2+Y^2を満たす最小のnを求めたいです。ABCで教育されてきたコンテスタントなら、原点から目標までの距離は小数となるので、少し誤差が怖いな~と思うのが自然ですね。両辺を2乗する式変形により、整数型のまま計算することができます。32bit整数型では収まらないので、long longなどの64bit整数型を使いましょう。

二分探索でもいいですが、R=1,X=Y=10^5のときでも高々10^5*√2歩程度でゴールできるはずなので、for文でチェックするほうが楽ちんですね。

 

ここまでコンテスト開始から7分程度。いざ提出……というタイミングで順位表をチラッと見ると、まだACが20人ちょいしかおらず、ペナ率が尋常でない。何か見落としはないか……と考えると、目標地点がRより近い時には一度遠くを経由する必要があることに気が付きます。これも似た考察を昔なんかの問題でしたことがありました。知らないと誤差を疑ってしまいそう。

場合分けを追加して提出、一発AC!この時点で33位でした。

 

実際には適切な実装をすれば誤差で落ちることはないようです。

 

D - Send More Money

算数パズルの王者、覆面算ですね(?)

まず問題文が難しい。丁寧に読みましょう。文字が別なら別の数字が割り当てられるようです。ということは、文字が11種類以上出てくるものはそもそも構築不可能なことがわかります。

文字が10種類以下であるとき、O((文字の種類)!)の順列全探索が十分間に合いそうです。

keyを文字、valueを一意なidとする辞書dictを用意しておきます。

順列を表すperm配列をNextPermutationで回していきます。Sのi文字目にperm[dict[S[i]]]が割り当てられますね。

 各文字列を数字に変換して、計算して成り立つならそれを出力して終わりです。ある程度の自信を持って提出しました。

f:id:G4NP0N_kyopro:20210412001012p:plain

うげ!?

サンプルすら落ちているのでもう一度問題を読み直します。出力する整数は対応する入力と長さが同じである必要があるとのこと。つまり先頭が0のようなものは認められないのですね。

REは、10桁の整数が出てくるのに32bit整数で計算していたため。TLEは正直予想外だったので面食らいました。ここで順位表を見て簡単そうなEを通してから戻ってきたのですが、1桁目の計算が矛盾ないときのみ最後まで計算するように改善したところ、無事1300msでACできました。だいたい10倍くらいの定数倍高速化のはず?

おそらく、整数配列を結合して文字列に変換→再度整数に変換、という処理がかなり重たかったのだと思います。面倒くさがらずにきちんと計算しよう!

E - Unique Color

シンプルな問題設定ですね。C,Dの凶悪さに比べて、E問題にしては比較的素直です。

頂点1を根とした部分木とみなします。根から下っていったときに既に使用した色を管理しておきたい気持ちになります。これは、setで使用済みの色の情報を持ちながら深さ優先探索することで解くことができます。具体的には、ある頂点に到着したときに、その頂点の色がまだ使われていないなら答えにその頂点を追加し、setに色を追加します。その頂点を根とする部分木の探索が終了したらsetから色を削除します。再帰関数での実装がわかりやすいでしょう。

    public void Solve()
    {
        var N = io.GetInt();
        var C = io.GetIntArray();
        var G = io.GetUnweightedAdjanceyList(N, N - 1, false, false);
        var ans = new HashSet<int>();
        var used = new HashSet<int>();
        void DFS(int now,int from)
        {
            var added = false;
            if (used.Contains(C[now]) == false)
            {
                used.Add(C[now]);
                ans.Add(now);
                added = true;
            }
            foreach(var next in G[now])
            {
                if (next == from) continue;
                DFS(next, now);
            }
            if (added) used.Remove(C[now]);
        }
        DFS(0, -1);
        foreach (var v in ans.OrderBy(e => e)) io.Print(v+1);
    }

F - Cube

数学オリンピックか?っつってた。数字を色とみなすことで立方体の塗分け問題として考えていましたが、場合分けがまず10通りくらいあってそれぞれについて数え上げる必要があって、不可能でした……。

ACかなり少なかったですね。こういう問題もいつか解けるようになってみたいです。

 

そんなわけで

青色復帰です。一安心。