QUESTION .1

  • 問題

    各文字列は rot13 で暗号化されている。復号し、宇宙人からのメッセージを解読せよ。
    rot13 とは、暗号化方式の1種である。詳細は wikipedia などを参照してください。
    例えば、

    と復号できます。

  • 制約

    文字列中に含まれる各文字は半角英字 a ~ z で構成されている。

  • 出力

    各文字列を復号し、改行区切りで出力せよ、与えられる文字列と同じ行数で出力してください。

  • 入力

    puvxlhwva
    fubxha
    tbxvtralb
    jnerjnerun
    xvzvgnpuvgb
    lhxban
    xnaxrvjb
    xvmhxhgnzr
    xbabubfuvav
    lnggrxvgn
    fnffbxhqntn
    lhxbab
    fuvehfuvgbfvgr
    chermragbjb
    bartnvfuvgnv
    ranwvqbevaxh
    mbar
    jb
    whaovfuvgr
    ubfuvvabqn
    xbabartnvjb
    xnanrgrxhereron
    bgbanfuvxh
    xbabubfuvjb
    ngbavfhehgfhzbevqn
    jnerjnerun
    nenfbvtbgbjb
    abmbznanv
    znrzhxvan
    urawvjb
    xvgnvfuvgrveh

  • 解説

    まず、文字列をひとつずつ、入力の最後まで受け取るという処理を行う必要があります。この方法は言語によって異なります。
    C++での例をのちほど示します。
    文字列を受け取って、各文字ごとにそれらを置き換えていく方法には色々あります。
    まず、文字列中の各文字をループを使って順に参照していきます。
    その後、各文字を実際に置き換えていくのですが、今回の問題の場合、a,b,…,mとn,o,…,zで処理を分けるのもひとつの方法です。
    前者であれば13文字後の文字を、後者であれば13文字前の文字を求めればよいです。

    実装例(C++)

    #include<bits/stdc++.h>
    using namespace std;
    char rot13(char c){
      if(c<='m'){c+=13;}
      else{c-=13;}
      return c;
    }
    int main(){
      string s;
      while(cin >> s){
        for(auto &c : s){
          cout << rot13(c);
        }cout << '\n';
      }
    }

    今回の問題の類題である ROT N が、AtCoderにあります。この問題の解法を使って今回の問題を解くことも可能です。

    以下は、復号後の文章です。

    地球人諸君、ごきげんよう。
    我々は、君達との友好な関係を築くため、この星にやってきた。
    早速だが、友好の印としてプレゼントをお願いしたい。
    エナジードリンク「ZONe」を準備して欲しいのだ。
    この願いを叶えてくれれば、おとなしくこの星を後にするつもりだ。
    我々は争いごとを望まない。 前向きな返事を期待している。

QUESTION .2

  • 問題

    2 次元行列は自動販売機の品番を表している。
    品番が素数のときのみ、限定フレーバーが販売されている。
    2 次元行列中に存在する素数の数を求め、限定フレーバーを販売している自販機の数を答えよ。

  • 制約

    ・2 次元行列のサイズは 20 × 20 である。
    ・行列の要素は半角スペースで区切られている。
    ・この行列の要素は 999 以下の正整数である。

  • 入力

    2 3 2 5 6 6 7 4 6 2 4 4 14 8 1 9 15 17 5 19
    2 2 2 7 7 1 8 6 15 11 4 15 17 26 9 7 21 4 13 10
    4 3 2 1 16 4 8 15 26 9 19 11 31 29 9 38 24 27 21 34
    3 6 12 8 1 4 23 6 7 26 38 47 36 19 45 28 40 33 9 19
    3 5 1 15 5 3 10 20 6 19 15 33 19 27 41 12 66 59 33 35
    7 10 10 13 30 2 42 3 55 54 4 51 67 39 59 10 30 2 25 73
    4 6 14 16 2 5 48 53 45 62 32 19 26 18 95 63 112 99 112 48
    6 5 10 10 11 26 24 55 64 30 65 87 57 60 110 28 127 17 50 78
    7 2 12 1 40 22 5 27 58 16 31 15 92 63 128 5 95 159 100 161
    6 16 23 28 13 14 5 30 40 70 95 6 32 58 109 138 31 131 110 106
    2 18 12 42 40 35 72 48 33 12 112 63 122 9 118 115 187 17 164 34
    2 20 32 20 58 56 65 95 80 112 123 24 100 110 1 125 29 70 150 211
    7 17 30 10 63 69 43 41 5 84 47 124 21 60 109 65 37 97 57 258
    5 20 36 30 64 62 95 112 84 93 6 68 8 106 138 69 197 133 133 106
    14 16 7 53 28 47 52 55 7 38 143 17 62 104 61 199 235 124 166 280
    16 3 36 51 16 38 45 46 9 24 75 87 94 127 73 50 229 38 132 234
    4 12 27 25 46 61 118 55 145 80 157 129 158 218 106 185 286 64 45 147
    5 30 13 12 24 25 52 84 157 131 78 177 89 158 96 121 293 306 324 188
    9 2 7 8 52 78 107 148 49 105 192 104 116 252 202 96 227 258 211 367
    12 10 41 48 4 87 107 102 28 143 24 99 8 234 171 34 72 320 33 295

  • 出力

    素数の数を求めてください。

  • 解説

    この問題でも、前の問題と同様に、入力を最後まで受け取るという処理が必要になります。
    ある正整数Xが素数かどうかの判定は、以下のように行うことができます。
     ・X=1であった場合、Xは素数ではない。
     ・そうでない場合、2以上√X以下の整数iについて、
      次の処理を行う。
       もしXがiで割り切れるならば、Xは素数ではない。
     ・この処理が終わった時点でXが素数でないと判定されなければ、Xは素数である。
    これを実装して実行すると、求める答えが108であることが分かります。
    なお、計算誤差の関係上、正整数i,Xに対して、i≤√Xの判定はi2≤Xとして整数型で行うとより安全です。

    実装例(C++)

    #include<bits/stdc++.h>
    using namespace std;
    bool isprime(int x){
      if(x==1){return false;}
      for(int i=2;i*i<=x;i++){
        if(x%i==0){return false;}
      }
      return true;
    }
    int main(){
      int a;
      int res=0;
      while(cin >> a){
        if(isprime(a)){res++;}
      }
      cout << res << '\n';
    }

QUESTION .3

  • 問題

    このグラフは、惑星同士の文化的交流を表している。星は N 個で、文化的交流は M 種類あります。
    ある星に見学に行くと、その星と文化的交流のある星で使われているプログラミング言語が手に入ります。
    3 つの星を選び、最も多くの言語を習得できる組み合わせを列挙せよ。
    例えば、

    15 23
    0 3
    0 4
    0 13
    1 5
    1 8
    1 9
    1 12
    2 6
    2 7
    2 10
    2 11
    2 12
    3 5
    3 8
    4 5
    4 9
    6 7
    6 9
    6 12
    8 10
    10 11
    10 12
    11 14

    というグラフ(星の数 15、文化的交流の数 23)に対して、
    最も多くのプログラミング言語を習得できる 3 つの星の組み合わせは

    0 1 2

    を選んだときで、このとき、星 14以外で使用されているプログラミング言語を取得できます。
    星 12 は星 1 と星 2 の両方と文化的交流があるものの、この図では星 1 と文化的交流があるとして便宜的に色分けしています。

  • 入力形式

  • 制約


  • 入力

    50 500
    12 18
    0 23
    15 43
    10 33
    5 18
    2 36
    25 36
    5 44
    9 44
    15 17
    26 43
    29 33
    32 37
    5 23
    6 24
    21 22
    4 32
    27 29
    1 20
    1 34
    12 21
    20 37
    18 38
    14 30
    0 30
    22 37
    5 42
    21 22
    41 44
    35 47
    12 47
    5 43
    41 49
    22 27
    7 27
    3 31
    18 36
    9 37
    19 38
    7 37
    9 23
    40 45
    15 35
    23 31
    32 33
    15 47
    10 24
    1 27
    32 49
    26 39
    13 32
    3 17
    14 39
    39 46
    4 30
    3 18
    4 10
    30 33
    12 25
    41 45
    5 19
    4 38
    10 20
    27 45
    6 9
    22 29
    12 18
    4 20
    10 46
    33 38
    30 33
    14 25
    19 46
    34 49
    0 35
    35 37
    25 29
    43 49
    24 48
    10 22
    4 5
    45 49
    3 29
    18 31
    2 16
    26 41
    15 24
    12 32
    8 13
    35 44
    21 47
    8 14
    10 24
    28 43
    27 41
    1 42
    32 47
    8 47
    7 8
    23 43
    34 46
    9 34
    12 32
    21 28
    36 44
    17 27
    0 19
    4 40
    22 34
    8 40
    15 44
    1 49
    11 23
    28 30
    31 41
    8 28
    7 26
    28 43
    0 45
    8 31
    16 23
    0 19
    6 25
    27 34
    9 39
    8 38
    11 42
    1 18
    13 33
    35 39
    28 43
    11 49
    5 36
    2 4
    12 24
    32 42
    21 36
    6 15
    16 26
    7 33
    27 35
    15 19
    0 23
    20 42
    34 45
    42 43
    2 6
    20 37
    3 9
    12 22
    11 23
    6 41
    6 42
    14 22
    24 45
    12 38
    3 25
    6 11
    14 19
    2 13
    8 11
    12 17
    11 23
    30 45
    17 22
    1 38
    9 31
    32 42
    7 46
    10 21
    26 32
    26 39
    5 16
    9 32
    18 43
    19 29
    28 33
    12 36
    6 10
    1 42
    22 29
    32 37
    13 20
    1 20
    4 36
    11 34
    5 15
    0 33
    1 19
    1 15
    32 37
    17 31
    21 35
    9 26
    5 40
    10 34
    28 43
    2 49
    10 28
    35 40
    7 40
    11 44
    21 28
    34 47
    31 37
    21 35
    4 38
    27 29
    11 40
    5 34
    4 20
    27 49
    1 8
    5 35
    34 39
    2 24
    3 47
    40 43
    8 32
    18 44
    13 42
    18 49
    11 24
    9 11
    3 47
    37 38
    29 44
    36 42
    12 32
    11 24
    33 48
    2 44
    14 41
    10 36
    0 35
    24 27
    12 48
    2 13
    0 4
    30 48
    29 36
    6 31
    5 41
    7 13
    3 11
    13 30
    11 40
    33 39
    4 43
    2 24
    0 20
    35 41
    29 38
    2 32
    11 25
    4 24
    46 47
    27 30
    9 20
    7 21
    16 24
    12 23
    12 31
    4 5
    41 47
    13 46
    1 8
    10 36
    2 31
    34 37
    31 33
    17 48
    3 22
    4 37
    2 46
    22 34
    17 41
    20 47
    10 45
    12 30
    9 45
    6 16
    7 23
    9 39
    6 39
    3 36
    30 43
    12 17
    23 31
    7 14
    8 38
    26 43
    12 26
    7 16
    39 46
    3 41
    9 46
    39 46
    18 30
    20 41
    40 41
    10 48
    17 36
    16 23
    2 43
    14 19
    25 38
    3 47
    27 48
    13 47
    2 39
    31 34
    26 31
    0 47
    40 46
    14 28
    12 49
    20 45
    2 9
    31 39
    2 46
    20 49
    24 37
    16 29
    1 13
    33 40
    6 38
    9 40
    5 32
    18 44
    22 29
    17 21
    38 42
    17 41
    20 40
    29 34
    3 29
    3 36
    36 39
    1 48
    15 32
    21 44
    3 40
    3 4
    9 26
    6 29
    10 37
    3 41
    17 32
    19 48
    12 14
    36 49
    35 44
    11 39
    2 43
    19 39
    6 49
    29 34
    31 45
    22 31
    0 3
    6 16
    26 37
    28 42
    13 24
    36 42
    0 5
    29 38
    46 49
    22 37
    3 43
    9 25
    42 44
    11 30
    5 33
    36 47
    1 23
    10 11
    43 46
    15 33
    27 30
    4 22
    12 20
    3 34
    4 37
    36 49
    3 36
    31 38
    25 37
    20 35
    16 18
    21 23
    7 40
    20 35
    16 20
    29 49
    28 33
    15 43
    26 46
    2 35
    11 44
    1 3
    16 42
    22 25
    9 45
    3 36
    29 34
    0 33
    47 49
    23 35
    6 16
    18 23
    9 39
    41 49
    22 46
    16 45
    23 43
    6 39
    15 35
    13 30
    28 44
    4 27
    7 25
    0 5
    24 27
    16 21
    8 12
    9 38
    16 35
    9 39
    30 32
    14 43
    34 49
    14 42
    39 40
    4 12
    15 37
    0 25
    10 37
    29 40
    2 10
    1 29
    12 14
    16 46
    9 38
    24 29
    21 46
    2 17
    6 42
    24 28
    17 22
    30 46
    6 39
    5 19
    9 24
    19 39
    20 30
    10 43
    41 45
    16 22
    21 25
    36 40
    12 14
    3 24
    8 14
    8 36
    7 18
    7 18
    27 42
    7 11
    38 49
    26 38
    32 38
    8 18
    7 25
    8 19
    15 31
    0 10
    33 45
    27 36
    24 43
    1 20
    16 26
    2 46
    15 30
    9 19
    28 36
    23 41
    3 14
    0 31
    41 45
    35 48
    23 42
    25 37
    3 27
    27 28
    30 42
    3 25
    13 14
    29 39

  • 出力

    最も多くのプログラミング言語を習得できる星の組み合わせを列挙してください。

    ※ 頂点番号の小さい順に半角スペース区切りで出力してください

  • 解説

    この問題の実装方針は色々とありますが、mad_hackerの名にふさわしい、一番カッコいい実装方針を紹介します。

    まず、3つの惑星を選んだ場合に習得できる言語はどのような集合になるか考えてみましょう。
    その答えは、3つの惑星のそれぞれについて、以下の集合を求めると、それらの集合の和集合となります。
     ・選んだ惑星自身。
     ・その惑星と文化的交流がある惑星全体の集合。
    求めるものは、いくつかの集合の和になります。集合の和を扱う時に、
    bit演算はとても強力です。
    まず、各惑星について、以下のような64bit符号なし整数型(等)の配列を求めておきます。
     ・G[k]=(惑星kと惑星iの間に文化的交流があるか
      k=iであればibit目は1、そうでなければ0)
    すると、惑星(i,j,k)を選んだ時に、S=G[i]|G[j]|G[k](|はbitごとのor演算(論理和))とすると、以下が成り立ちます。
     ・Sのibit目が1である、かつその時に限って、i番目の惑星の言語を習得できる。
    何種類の異なる言語を習得できるかを求めるためには、Sのうちの立っているbitの数を求めればよいです。これを実現するためには、popcountという有名なアルゴリズムを使用します。
    実装は何通りかありますが、そのうちのひとつを実装例に示します。

    結局、各(i,j,k)の組についてそのときに習得できる言語の数を定数時間で計算でき、全体計算量O(N3)が達成できます。

    #include<bits/stdc++.h>
    
    using namespace std;
    
    const uint64_t m1  = 0x5555555555555555;
    const uint64_t m2  = 0x3333333333333333;
    const uint64_t m4  = 0x0f0f0f0f0f0f0f0f;
    const uint64_t m8  = 0x00ff00ff00ff00ff;
    const uint64_t m16 = 0x0000ffff0000ffff;
    const uint64_t m32 = 0x00000000ffffffff;
    
    int popcount(uint64_t x){
      x = (x & m1 ) + ((x >>  1) & m1 );
      x = (x & m2 ) + ((x >>  2) & m2 );
      x = (x & m4 ) + ((x >>  4) & m4 );
      x = (x & m8 ) + ((x >>  8) & m8 );
      x = (x & m16) + ((x >> 16) & m16);
      x = (x & m32) + ((x >> 32) & m32);
      return x;
    }
    
    typedef struct{
      int p;
      int q;
      int r;
    }sol;
    
    int main(){
      int n,m;
      cin >> n >> m;
      vector<uint64_t> g(n,0);
      for(int i=0;i<n;i++){g[i]|=(1ul<<i);}
      for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        g[a]|=(1ul<<b);
        g[b]|=(1ul<<a);
      }
    
      int rval=0;
      vector<sol> res;
      for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
          for(int k=j+1;k<n;k++){
            int cur=popcount(g[i]|g[j]|g[k]);
            if(rval<cur){
              res.clear();
              rval=cur;
            }
            if(rval==cur){
              res.push_back({i,j,k});
            }
          }
        }
      }
      
      for(auto &nx : res){
        cout << nx.p << ' ';
        cout << nx.q << ' ';
        cout << nx.r << '\n';
      }
      return 0;
    }
    

    今回の入力の場合、以下の組み合わせである場合、46個の言語を習得でき、これが最善です。

    5 12 24

SNS SHARE

シェアはこちら

0123456789SUVdgo、。々「」あいうえおかがきくけげこごさざしじすずせそただちっつてでとどなにねのはびふへぽまみむめもゃやゆょよらりるれわをんァアィイウカキクグケコシスズセッツテトドニノバパビピフブプベボポマミムャュラリルレワンー一両並乗人仲低何余供便倉像優元先入全具内冬出分切初利動十友合品員団地場増夜大女子安室家寝小少山川布帰広床座心性悩想愛感慢所手抱数敷旅族日時景晴替末来楽歳母毎気沢泊海激父牧物犬狭由男疲目着祖私移積立端緒者自良色荷行街裕見買超越足距路車転載近連週遊運過道達違選釣鎌長閉開間降離雨食駐!159:CLOPT~