ABC291参加記録 ~ DPお前もう船降りろ ~

はじめに

今週もAtCoder Beginners Contest 291に参加してきましたので、軽く参加記録です。

戦績

今回の戦績は以下の通りです。

A, B, Cの3完で、パフォーマンス439でした。レート変動は571→557です。

D問題ゆ゛る゛さ゛ん゛(大迫真)

問題とか

出た問題紹介します。

A - camel Case

大文字が出現する位置を答える問題です。私の解法では、asciiにおいて小文字を数値表現したときに90を上回ることを利用して判定するというものです。

以下ACコードです。

#include <stdio.h>

int main (void) {
    char s[101];
    scanf("%s", s);

    for (int i = 0; s[i] != '\0'; i++) {
        if (90 >= s[i]) {
            printf("%i", i + 1);
        }
    }

    return 0;
}

B - Trimmed Mean

バラバラに渡される数値の上からと下からN個を抜いて平均を取るという問題です。おそらく出題意図としては、O(N^2)でもいいからソートを実装してみてというものだと思います。

何らかの手段でソートをかけて、真ん中の3N個のデータについて平均を取ることでACをとれます。私はC言語の標準関数(qsort())を使わずに、自作関数でやってみました。

ACコードはやたらと長いので、実際の提出を載せます。

提出

C - LRUD Instructions 2

二次元座標平面のグリッド上を動き回る人が、二回以上同じ座標に来ることがあるかを判定する問題です。

正直結構悩みました。一番先に思いついたのは、訪れた座標をキーにして、連想配列に入れることです。pythonなどの組み込みのデータ構造がリッチな言語なら多分この方法でやっていました。

残念なことに、現状C言語で私がすぐに利用できる連想配列はないため、他の方法を取りました。

しばらく唸っていると、同じ座標を訪れるということは、訪れた座標をすべて記録しておき、ソートをかけることですぐに判定できるのではないかという天啓が訪れます。早速実装しましたが...

座標のxとyでソートをかけると、片方のソート結果までぐちゃぐちゃにされることを忘れていました。対策として、一旦xでソートをかけてから、xが同じ奴らに対してyソートをかけるように修正したら通りました。というわけで以下AC提出です。(やたら長いのでこちらも提出で)

提出

D - Flip Cards

2^Nの組み合わせの中から条件を満たすものの数を考える問題です。制約から明らかに全探索したら間に合いません。(原理的にはbit全探索すれば解けますが)というわけで何らかの簡略化を行う必要が出てきます。

組み合わせ + 全探索だと不可能 ← これ大体DP説 というわけでDPの線を疑いながら考えました。結果...

典型dpの攻略は春休み中の課題の一つです。がんばります...

解説に「配るDP」とか書いてあってビビっちゃいました。くやしいので解けたら別記事建てるかもしれません。

終わりに

参加記録は以上です。ここまで読んでいただきありがとうございました。

レートはモチベーションの一つではありますが、レートによってモチベーションが下げられるのはもったいない気がするので、今回の失敗はなかったことにしときます。春休み中に緑行けるといいなぁって思っています。それでは次のエントリで。