C - Neo-lexicographic Ordering

提出 #25936509 - サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）

入力された文字列群を、以下の様にソートします。
ソート中に比較される文字列が同じ長さとは限らないので、最初に短い方の長さをLENに入れておきます。
あとは、比較される文字列A,Bを頭から一文字ずつ見ていき、Xの中での登場位置をsa,sbにいれ、その位置からA,Bの比較結果を1,-1で返します。なお同じ文字列はないことが入力で保証されているので、0を返すところはありません。

Array.Sort(S, (A,B) => //S内での比較文字列A,B
{
    int LEN = Math.Min(A.Length, B.Length);
    for(int i = 0; i < LEN; ++i)
    {
        int sa = X.IndexOf(A[i]);//X内での文字A[i]のindexを返す
        int sb = X.IndexOf(B[i]);//X内での文字B[i]のindexを返す
        if(sa < sb)
        {
            return -1;
        }
        else if(sa > sb)
        {
            return 1;
        }
    }
        //"a", "ab"みたいな、前半が一致している場合
    return A.Length - B.Length;//文字列が短いほうが前に来る
});

余談ですが、「1,-1どっちで返せばいいんだっけ」というところで毎回迷います。

D - Strange Lunchbox

解説 - AtCoder Beginner Contest 219

提出 #25972807 - サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）

問題のシチュエーションが汎用的で、応用がありそうな問題だと思いました。なので、似た問題がありそうかなと思ったのですが、時間内には解けなかった...

公式解説と

【AtCoder解説】PythonでABC219のA,B,C,D問題を制する！ - Qiita

これがわかりやすかったです。なるほど...

DPを3次元で行う部分がミソだったようです。発想としては、 AtCoder ABC219 個人的メモにあるように,「たこ焼きだけ」「たいやきだけ」から考えると思いつけたかも知れません。

なお、最後にdp[N,X,Y]=INFかどうかを判定する部分ですが、自分の提出コードのように、予め弁当内の全部のたこ焼き、たい焼きの数を調べておいて、弾いておくことでもACできます。
この方がわかりやすいかと言われると、正直微妙ですが、自明な部分は予め弾いておいたほうが、コードを書く側としては安心できるかと思います。

感想

C問題がさらっと解けたせいか、Dが解けない割には、やたらパフォが高かった。 D問題は、やっぱりDPの修練が足りないようです。