ABC171振り返り

んぐです。最近緑に持ち直しました。精選100問を解くなどしてさらに精進していきたいと思います。 それでは振り返りです。

結果

atcoder.jp

早解き回でしたがなんとか許してもらえたようです。DのWAがまじで悔しいです。

解答

A問題

指示通りに実装するのみです。Pythonで簡単に書けそうだったのPythonを選択しました。最初「小文字を大文字に、大文字を小文字に変換せよ」と誤読して input().swapcase() してました。こんなメソッドあるんだ…と感動していてたのに……

if input().isupper():
    print('A')
else:
    print('a')

B問題

愚直に個選ぶ方法を全探索していたら組み合わせ爆発を起こして間に合いません。この問題は超簡単な貪欲法で、最も安い果物を個選べばよいですね。これもPythonで書きました。コード量少なく書けるのが魅力的ですね。ところで解答コードめっちゃPythonっぽい書き方できてません？ちょっと興奮しながら提出しました。

N, K = map(int, input().split())
p = list(map(int, input().split()))
p.sort()
print(sum(p[0:K]))

C問題

問題を解釈すると、26進数変換しなさい、という問題ですね。 ただし、0に対応するアルファベットがないのがややこしいですね。僕の場合はなんか適当にこねくり回したら解けちゃいました（） しっかりとした論理付けは後でしたいと思います。コンテスト中感満載のコードですがお許しください。

ちなみにC++だと1000000000000001がオーバーフローしちゃうと思ってPython選んだんですが、long longなら十分収まるんですね。 文字コード周りの操作がPythonだと面倒なのでC++にしときゃよかったなぁと後悔。

N = int(input())-1
l = len(str(N))

ans = ''

if N == 0:
    print('a')
    exit(0)

cnt = 0
while N >= 26:
    d = N % 26
    ans = chr(ord('a') + d) + ans
    N //= 26
    N -= 1
ans = chr(ord('a') + N) + ans

print(ans)

D問題

クエリを次々と消化していく系ですね。PASTっぽい問題。いちいち和を求めていたら時間が足りないので工夫します。まず、なにも操作していない状態のの総和を求めます。そして、任意の数が数列に何個あるかをカウントする変数を用意します。C++だと map が便利だと思います。次にクエリを消化していくわけですが、操作により数列の総和が操作前と比べてどれだけ減るかが瞬時に計算できれば良さそうと考えます。操作される数字を、操作されたあとの数字を、数列にあるの数をとすると、で操作後の数列の総和求めることができます。これはを求めるためのデータ構造が適切なものであれば十分小さい計算量で求めることができます。累積和を知っていれば、発想はそれに近い感じのアルゴリズムなので思いつきやすいかな。

ここまで考察できればあとは実装するのみです。ところどころメタプロっぽいのは気にしないでください（） ちなみに long longにしてなかったせいでWA取られました。この件についてはまた別記事にします。

int main()
{
    Cin(lint, N);
    vector<lint> A(N);
    map<lint, lint> mp;
    lint sum = 0;
    rep (i, N)
    {
        cin >> A[i];
        mp[A[i]]++;
        sum += A[i];
    }

    Cin(lint, Q);
    while (Q--)
    {
        Cin(lint, B, C);
        lint dist = C - B;
        lint rep_num = mp[B];
        sum += rep_num * dist;
        mp[B] = 0;
        mp[C] += rep_num;

        Print(sum);
    }

    return 0;
}

E問題

E問題にしては簡単でした。Xorでビビってたんですが基本的な性質を知っていれば簡単に解けちゃうと思います。 ただし、僕はテストケースの次元なら確実に求められることを理解していましたが、一般の場合で成り立つことは証明できてません。まあ、でも、あってるでしょって感じだったので速攻提出しました。

知っておきたい性質

• 
• 
• 移項は符号など一切気にせず愚直に行える
• 結合性や可換性などは成り立つ

あとは頑張って式変形をして、D問題と似たような工夫をすれば十分高速に求まります。

int main()
{
    Cin(lint, N);
    Cinv(lint, a, N);

    lint sum = a[0];
    for (int i = 1; i < N; ++i)
    {
        sum ^= a[i];
    }

    rep (i, N)
    {
        cout << (sum ^ a[i]);
        if (i < N - 1) cout << " ";
        else cout << "\n";
    }



    return 0;
}

F問題

難しさは緑コーダー並に理解しました。けど、競プロそのものの勉強量は少なくても、数学得意だったら解けそうだなって印象を受けました。 (全体) - (被り)みたいな感じで考えてましたが、、、てんでだめでした。

総括

Pythonを使うとタイプ量少なく早く解けますね。Pythonに対する「慣れてない感」は大分なくなってきたので、今後はABCの主戦力として活躍してもらおうかなと思います。