おはやし日記

テーマ……バイク←プログラミング←旅

競プロABC問題風記事の解説

プログラミング AtCoder 雑談 C++

これの解説記事です。先に↑を見てください。ちなみに「ABC問題」は数学の難問「ABC予想」のことではありません。競技プログラミングの「AtCoder Beginner Contest」の略称です。

なお、この解説が正しいかどうかは（全文に渡って）保証しかねます。多分あってる。知らんけど（無責任）。

解説

（説明下手なのとできるだけわかりやすくしたかったのと自己満足のために長めになってます）

それぞれの人について、経験値が界隈の他の誰よりも高い趣味を持っているとき、それを「すごい趣味」とします。「すごい趣味」を1つ以上持っている人が「すごい人」です。

7 9
283  18 978  49 962 364 560  72 287
 35 920 983 101 296 868 764  58 667
 57 697  60 382 215  93 949 390 601
994  93 197 431 966 360 265 923 101
 51 240 298 247 633 868 899 665  30
250 275 764 990 173 781 544 999 630
717 513 152 479 522 478 951 417 898

これは入力例4を見やすく整形したものですが、調査する経験値を決めて縦に見ればそれが「すごい趣味」になるかどうかわかります。

具体的には、$E_{4,1} = 994$ を見ると、縦方向に$994$以上の値が無いので4番目の人は（少なくとも）趣味1が「すごい趣味」であるので「すごい人」だとわかります。

また、後述する引っ掛けのポイントですが、5番目の人は「すごい人」ではありません。$E_{5,6} = 868$ は、趣味6の"最大経験値"に等しいですが、同じく$868$の経験値を持つ人がいます（2番目の人）。また、他の趣味は明らかに「すごい趣味」ではないので、5番目の人は「すごい人」ではないです。

これを素直に実装すると実行時間が $ O(N^{2}M) $ になるので間に合いません（後述の実装例のTLE）。

$ time myQ/1-TLE < myQ/limitInput.txt > myQ/limitOutput.txt

real    1m0.887s
user    0m59.574s
sys     0m0.278s

そこで、最初の読み込み時に界隈での各趣味における最大経験値を保存しておき、それとの照らし合わせをすれば実行時間が $O(NM)$ になるので間に合います（実装例のAC）。

$ time myQ/1-AC < myQ/limitInput.txt > myQ/limitOutput.txt

real    0m3.711s
user    0m3.613s
sys     0m0.029s

ただし、最大経験値の設定において引っ掛け（？）があります。

（それぞれの趣味について）すでにある最大値$Emax$と読み込んだ経験値$E$を比較したとき、$E > Emax$のとき$Emax$を更新するのは当然ですが、$E = Emax$のときはその$Emax$を「すごい趣味」判定に使ってはいけないので、$Emax$をインクリメントしてハードルをあげることが必要です。

入出力例3を見てみましょう。

3 2
10000000 9999999
10000000 9999999
10000000 9999999

（以後擬似プログラミングなのか数式なのかよくわかんない形式でダラダラと（良く言えば丁寧に）書きます。MathJaxを使いたいだけ。すまん。）

もしも処理が

$$ E > Emax のとき Emax = E $$

だったら、1番目の人の経験値を読み込んだ段階で

\begin{align} Emax = [ 10000000, 9999999 ] \end{align}

となります。ここに2番目の人の経験値を読み込むと

\begin{align} E_{2,1} &== Emax_1 \cr E_{2,2} &== Emax_2 \end{align}

の判定により

$$ Emax = [ 10000000, 9999999 ] $$

が維持されます。これは3番目の人の経験値を読み込むときも同様です。

ここで「すごい人」判定に入ると、1番目の人について

\begin{align} E_{1,1} &== Emax_1 \cr E_{1,2} &== Emax_2 \end{align}

なので『1番目の人は「すごい人」』と判定します（もちろん誤り）。同様に『2番目、3番目の人についても「すごい人」』と判定します。



さて、最大経験値を設定する上で本来すべき処理は

\begin{align} E &> Emax のとき Emax = E \cr E &= Emax のとき Emax = Emax + 1 \end{align}

です。こうすることによって1番目の人の経験値を読み込んだ段階で

\begin{align} Emax = [ 10000000, 9999999 ] \end{align}

となったところに2番目の人の経験値を読み込むと

\begin{align} E_{2,1} &== Emax_1 \cr E_{2,2} &== Emax_2 \end{align}

の判定により（ここは先ほどと同じだが）

$$ Emax = [ 10000001, 10000000 ] $$

となります（ここが違う）。3番目の人の経験値を読み込んだ時はいずれも$E < Emax$となりますから、$Emax$の更新は行われません。

この状態で「すごい人」判定に入ると1番目の人について

\begin{align} E_{1,1} &< Emax_1 \cr E_{1,2} &< Emax_2 \end{align}

なので『1番目の人は「すごい人」ではない』と判定します（正しい！）。2番目、3番目の人についても同様の判定が行われ、正しい出力が得られます。

実装例(c++)

AC

#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, M;
  cin>>N>>M;
  vector<int> Emax(M, 0);
  vector< vector<int> > E(N, vector<int>(M));
  for(int i=0; i<N; i++)for(int j=0; j<M; j++){
    cin>>E[i][j];
    if(E[i][j] > Emax[j]){
      Emax[j] = E[i][j];
    }else if(E[i][j] == Emax[j]){
      Emax[j]++;
    }
  }

  bool great;
  for(int i=0; i<N; i++){
    great = false;
    for(int j=0; j<M; j++){
      if(E[i][j] == Emax[j]){
        great = true;
        break;
      }
    }
    cout<<(great? "Yes\n": "No\n");
  }
}

LTE

一応正しい結果が出ますが重いです。

#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, M;
  cin>>N>>M;
  vector< vector<int> > E(N, vector<int>(M));
  for(int i=0; i<N; i++)for(int j=0; j<M; j++){
    cin>>E[i][j];
  }

  bool great;
  bool haveGreatHobby;
  for(int i=0; i<N; i++){
    great = false;
    for(int j=0; j<M; j++){
      haveGreatHobby = true;
      for(int k=0; k<N; k++){
        if(k==i)continue;
        if(E[i][j] <= E[k][j]){
          haveGreatHobby = false;
        }
      }
      if(haveGreatHobby)great = true;
    }
    cout<<(great? "Yes\n": "No\n");
  }
}

まとめ（感想）

  • なんとなくの思いつきからABC風の問題を作ってみました。結構勉強になった、気がします。

  • 「すごい人」の人数を求めるんでもよかったけど、それぞれが「すごい人」なのか知りたかったから、いちいち書き出すようにした。

ちなみに、limitInputについて「すごい人」の人数を書き出すようにしたら618人（1000人中）と出ました。

さらに、$ N = M = 10000 $ としたくそデカテストケースを作って人数を割り出したら1万人中6316人と出ました。テストケース生成に1分と計算に6分かかりましたが(笑)

（色々比べたところ、AtCoderの実行時間に対して俺のパソコンが5〜10倍くらい処理遅いと思う…………）

$ time myQ/1-maketest > bigInput.txt
10000 10000

real    1m7.698s
user    0m59.588s
sys     0m1.754s
$ time myQ/1-AC < bigInput.txt
6316

real    6m14.159s
user    5m59.372s
sys     0m3.062s

  • 経験値のとりうる幅が十分に大きいときNとMによって「すごい人」の割合はどの程度になるのか？←疑問に思った。意外と単純な話なのかもしれない。知らんけど。検証めんどい…………

  • ちなみにランダムに生成した経験値のとりうる幅が小さいとき、極端に0~10のときを考えればわかりますが、理論最大経験値(10)を持つ人が続出して「すごい人」はいなくなります。

  • ということで（？）、実行時間を4secとしたのも、一応僕のパソコンで $ O(NM) $ のTLEが出ず、万が一 $ O(N^{2}M) $ をAtCoderのサーバーで10倍速で処理してもTLEになる（はず）ようにとの配慮です。…………って、$ M $ を1/2倍にすれば ACとTLE両方1/2倍になって丸く収まるのでは？と単純に思ったけど今更色々書き換えるの面倒なのでやめます。timeコマンドで測定してみたらそんなに単純な話でもなかったっぽいので（そりゃそうか）。自分のパソコンでのTLEの処理は実行時間にばらつきがあるし、TLE界隈の話は正確性に欠けるな。しゃあない。$E$の桁数でも実行時間変わるしな。

  • 難易度を欲張ってCとしましたが、雑に実装したらTLEが出るのと微妙な引っ掛けがあるのでまあそんな感じかなって。

  • 最初はもうちょいめんどくさい入力方式にしようと思ってたんですけど多分pairとか使わなきゃいけなくて自分で解くのが面倒だったので単純に $ N \times M $ の配列で入力することにした。

  • time コマンドで実行時間が測れるのも収穫でした。AtCoderのサーバーが計算早いということもわかりました（僕のパソコンが遅いだけでは？）

  • あと、$\mathrm{MathJax}$を導入できてよかった。ヘッダにJS入れてるので今後の記事でも使える\(@_@)/ ただやっぱり下付き文字のアンダーバーが時々悪さしたり思うように表示できない時があるなぁ

  • もしかしてｽﾏﾋｮだとMathJax活きない？プレビューで表示死んでるので心配だ。崩れてたらごめんよ。→JavaScriptを「ブログの」ヘッダーに書いていたためと思われる。「記事の」下部にJSを入れるようにして、スマホでもPC版と同様のHTMLを使うみたいな設定にチェックを入れたらスマホプレビューでもMathJax適用されてた

おまけ1 - 最大テストケース

でかすぎてうまく表示できてないのでRawで見るとかgistからDLするとかしてください。

てかあってるかどうか判定するの面倒なので（ファイル入力で一致判定するだけだからできないことないけど）実行時間の足切りくらいにしか使えない。

あと、サイズがでかいのでAtCoderのコードテストには貼り付けられないので皆さんの環境でやってください。

myQuestion testcase

おまけ2 - テストケースのランダム生成

#include <bits/stdc++.h>
using namespace std;
#define MAX 10000000
int main(){
  int N, M;
  cin>>N>>M;
  cout<<N<<" "<<M<<endl;
  mt19937 mt{ random_device{}() };
  uniform_int_distribution<int> dist(0, MAX);

  for(int i=0; i<N; i++)for(int j=0; j<M; j++){
    cout << dist(mt);
    cout << (j==M-1 ? "\n" : " ");
  }
}

$ N $ と $ M $ を入力するとそのサイズで経験値がランダムなテストケースを書き出します。リダイレクトでファイルに書き出せば使いやすくなります。

$ time myQ/1-maketest > myQ/testInput.txt

だいたい $ \big( N \times M \times ( E の桁数 + 1 ) \big) $ バイトになります（それはそう）。

おしまい。

参考

プライバシーポリシー ・お問い合わせはこちら