Web備忘録 プログラミングを中心に技術的な事柄を忘れないように書き残します。

AtCoder Beginner Contest 155 に参加してやらかした記録(C#の文字列比較は注意)

AtCoder Beginner Contest 155 に参加してやらかした記録(C#の文字列比較は注意)
目次

AtCoder Beginner Contest 155 に参加した記録

AtCoder Beginner Contest 155 – AtCoder

ABC155 に参加しました。

結果はABCの3問ACでした。D問題が難しくて太刀打ちできなかったのはまあ実力不足かなと思いましたが、C問題でやらかしました。

結果ACまでに何度も提出を重ね、結果順位4000位以上でパフォーマンスも灰色でした。これはこれまでの参加記録で圧倒的に最低な記録です。

前回の青パフォーマンスで得たレーティングの全部ではないですが大部分を吐き出しました。青パフォーマンスとった次の回で灰色はえぐい記録だと思いました。

とりあえず問題を振り返ります。

A – Poor

A – Poor

3 つ組の数について、ある 2 つが等しく、残りの 1 つがそれらと異なるとき、その 3 つ組を「かわいそう」であるといいます。

3 つの整数 A,B,C が与えられるので、この 3 つ組がかわいそうであれば Yes を、そうでなければ No を出力してください。

A問題は条件分岐が書ければOKです。

if (A == B && A != C)
{
    Console.WriteLine("Yes");
}
else if (B == C && B != A)
{
    Console.WriteLine("Yes");
}
else if (A == C && A != B)
{
    Console.WriteLine("Yes");
}
else
{
    Console.WriteLine("No");
}

馬鹿正直に3つのパターンを書いてあげて提出しました。

B – Papers, Please

B – Papers, Please

あなたは AtCoder 王国の入国審査官です。入国者の書類にはいくつかの整数が書かれており、あなたの仕事はこれらが条件を満たすか判定することです。

規約では、次の条件を満たすとき、またその時に限り、入国を承認することになっています。

  • 書類に書かれている整数のうち、偶数であるものは全て、3 または 5 で割り切れる。

上の規約に従うとき、書類に N 個の整数 A1,A2,…,AN が書かれた入国者を承認するならば APPROVED を、しないならば DENIED を出力してください。

注記

問題文中の条件は、「x が書類に書かれている整数のうち、偶数であるものならば、x は 3 または 5 で割り切れる。」 と言い換えられます。 ここで、「または」 「ならば」 は論理学における意味です。

普段のB問題に比べると問題文が長くて少し難しいのかもしれません。

基本的にはすべての数をループして確認し、偶数の場合のみ、3の倍数と5の倍数の判定をしてやればよいです。

偶数であり、3の倍数でも5の倍数でもない数字は条件を満たさないので、このような数字が見つかったらNGとします。

var ok = true;
for (int i = 0; i < N; i++)
{
    if (A[i] % 2 == 0)
    {
        if (A[i] % 3 != 0 && A[i] % 5 != 0)
        {
            ok = false;
            break;
        }
    }
}
Console.WriteLine(ok ? "APPROVED" : "DENIED");

C – Poll

C – Poll

件のC問題です。

N 枚の投票用紙があり、i (1≤i≤N) 枚目には文字列 Si が書かれています。

書かれた回数が最も多い文字列を全て、辞書順で小さい順に出力してください。

制約

  • 1≤N≤2×105
  • Si は英小文字のみからなる文字列 (1≤i≤N)
  • Si の長さは 1 以上 10 以下 (1≤i≤N)

基本的には何の変哲もない問題です。制約も普通です。

考えた解法手順は以下の通りです。何も変なことはしてないのですぐに思いつきました。

  1. 与えられた文字列を Dictionary に入れて回数を数えます。
  2. 最大の出現回数を求めます。
  3. 最大の出現回数の文字列をすべてリストに入れます。
  4. リストを辞書順にソートします。
  5. リストの内容を出力します。

以下、ACしたコードです。

int main() {
  int n;
  cin >> n;
  vector<string> a(n);
  rep(i, n) cin >> a[i];

  // 1, 2 の手順
  map<string, int> m;
  int maxCount = 0;
  rep(i, n) {
    m[a[i]] = m[a[i]] + 1;
    maxCount = max(maxCount, m[a[i]]);
  }

  // 3 の手順
  vector<string> list;
  for(auto p : m) {
    if(p.second == maxCount) {
      list.push_back(p.first);
    }
  }

  // 4 の手順
  sort(list.begin(), list.end());

  // 5の手順
  rep(i, list.size()) {
    cout << list[i] << endl;
  }

  return 0;
}

いきなりC++ですが、手順通りに実装してACしました。なぜC#でないかというと、この内容をC#で実装するとTLEになってしまい、それが解消できなかったからです。

以下C#のコードです。

var dic = new Dictionary<string, int>();
var max = 0;
for (int i = 0; i < N; i++)
{
    var j = 0;
    dic[S[i]] = dic.TryGetValue(S[i], out j) ? j + 1 : 1;
    max = Math.Max(max, dic[S[i]]);
}
var list = new List<string>();
foreach (var p in dic)
{
    if (p.Value == max) list.Add(p.Key);
}
var array = list.ToArray();
Array.Sort(array);
foreach (var a in array)
{
    Console.WriteLine(a);
}

最初は Linq(Enumerable.OrderBy()) で実装していたのですが、TLEしました。

Enumerable.OrderBy() が最悪ケースで O(N2) の計算量がかかってしまうというのは知っていたので、それが原因かと思い、Array.Sort() にしてみましたがやはりうまくいきませんでした。

たぶん比較関数を自力でうまいこと実装して調整しないと文字列のソート自体が効率よくできないのだろうと思い、C#での提出は諦めました。

その後C++の環境を立ち上げて手探りで書いて提出して、REおこしてなんだかんだして最終的にACはできました。

コンテスト終了後提出結果を見てみるとC#でコンテスト中にACした人は5人くらいしかいませんでした。

C# で文字列をソートするときの注意点

基本的には OrderBy() だろうが Array.Sort() だろうが辞書順ソート自体は可能です。今回の問題でもTLE以外はACしていたので。

結局のところ問題はソート時の比較が効率よくできていないせいで、最大10文字*105程度の文字列でソートするときにTLEしているようでした。

原因は、C#の文字列ソート自体がカルチャを考慮してソートするため通常のソートよりも遅くなっているのが原因でした。

ACした人の提出内容を見ると、独自で比較用の関数を実装し、これを使ってソートしているようでした。あるいは標準ライブラリ内のカルチャを考慮せずに純粋に辞書順比較する関数を使うとうまくいきます。

例えば以下のように。

var dic = new Dictionary<string, int>();
var max = 0;
for (int i = 0; i < N; i++)
{
    var j = 0;
    dic[S[i]] = dic.TryGetValue(S[i], out j) ? j + 1 : 1;
    max = Math.Max(max, dic[S[i]]);
}
var list = new List<string>();
foreach (var p in dic)
{
    if (p.Value == max) list.Add(p.Key);
}
var array = list.ToArray();

// Array.Sort(array, cmp);
Array.Sort(array, StringComparer.OrdinalIgnoreCase);

foreach (var a in array)
{
    Console.WriteLine(a);
}

// 中略 ...
// 比較用の関数を用意して比較してもいい。
static int cmp(string a, string b)
{
    for (var i = 0; i < Math.Min(a.Length, b.Length); i++)
        if (a[i] < b[i]) return -1;
        else if (a[i] > b[i]) return 1;
    if (a.Length == b.Length) return 0;
    if (a.Length > b.Length) return 1;
    else return -1;
}

変わったのは、Array.Sort() に比較用の関数wを引数で渡している点だけです。これでACします。

あるいは以下のように、独自で実装した比較関数でもいいですが、やはり標準ライブラリにカルチャを無視して純粋に辞書順比較できる比較関数があるようなのでこれを使えばよいです。

// 大文字小文字を無視して比較
Array.Sort(array, StringComparer.OrdinalIgnoreCase);
// 大文字小文字を区別して比較
Array.Sort(array, StringComparer.Ordinal);

どっちを使ってもACします。

いずれにせよデフォルトだと、カルチャの単語ベースの比較規則を使用 して比較が行われるため余計な計算量がかかってしまいます。

参考ページは以下のURLです。

.NET の文字列を使用するためのベスト プラクティス | Microsoft Docs

.NET 側でいろいろと気を使っていい感じのソートをやっているせいで余計な計算がかかってしまい、ダメっぽいですね。

いずれにせよ競技プログラミングのC#における文字列比較は必ず、比較関数(StringComparison.Ordinal または StringComparison.OrdinalIgnoreCase)を指定するようにしましょう。そうしないと今回の問題みたいにTLEに遭遇し泣きを見ます。

この問題のおかげで、レートがかなり持っていかれました。前回が+100くらいで今回が-60くらいです。

少し痛いですが、勉強代として仕方がないですね。。。本来ならレーティング微増のパフォーマンス水色くらいだったはずが、過去最高のはまり具合でした。

これを機にC++ももう少し勉強しておこうと思いました。

ちなみにD問題は無理でした。Cがやばかったので回避してDに回りもしたのですが、太刀打ちできませんでした。負の数があるのがどう処理すればよいかわからなかった感じです。

今回の学びはC#の文字列比較関数の指定です。スニペットに放り込んでおくことにします。

以上。

競技プログラミングカテゴリの最新記事