SRM 519 Div 1 - Problem 250 BinaryCards

問題
SRM 519 Div 1 - Problem 250 BinaryCards
TopCoder Statistics - Problem Statement

使用言語
C++

問題概要
0から63までの数字のカード(全て1枚ずつ)を使う.数字xのカードには2ˆxのドットが描かれている.
最初全てのカードは伏せられている.AからBまでの連続する整数について,カードを表にして,カードに描かれるドットの数で表す.表になったカードのドットの合計を求める.

方針
表のカード(のドットの数)について考えると,
 6: 2 4
 7: 1 2 4
 8: 8
となる.表になったドットは 1+2+4+8=15
→各数字のビット和でわかりそう

しかし,O(N)で最大10ˆ18になるので連続する整数のビット和を全て取るのは現実的でない.

ここで単純化して考える.
A = 2ˆ30 + 1, B = 2ˆ30 + 24とする.
答え(Cとする)にはもちろんA, Bが含まれる(C|A==A, C|B==B)
差分について考えると,23 = 16 + 4 + 2 + 1 = 0x10111
これの最上位ビット以下のは全て1になりそう(例 20ˆ3+8)
なのでそれ以下を1にする.

所感
・わかりにくすぎる問題文に反して,楽しい問題
・コード短すぎ問題

コード

class BinaryCards {
    public:
    long long largestNumber(long long A, long long B) {
      ll ans = A | B;
      //差分の最上位ビット以下のビットが1になるようにOR
      //どうせ最上位以下のビットは全て1になるので,最上位1つずつ左シフトしてforループ
      for (ll i = B - A; i > 0; i = i>>1) ans |= i;
      return ans;
    }
};

SRM 518 Div 1 - Problem 250 LargestSubsequence

問題
SRM 518 Div 1 - Problem 250 LargestSubsequence
TopCoder Statistics - Problem Statement

使用言語
C++

問題概要
与えられた文字列から各文字の相対的な順序は変えずに,文字列を抽出し,その中で辞書順で最も大きくなる文字列を返す.

方針
文字列 .*XY.* について,
 X>=YならXは残す
 X所感
・文字列の連結が自然にできるのはありがたい.言語仕様に感謝.

コード

class LargestSubsequence {
    public:
    string getLargest(string s) {
      string ans = "";
      int l = s.length();
      ans += s[l-1];
      for (int i = l-2; i >= 0; i--) {
        if (ans[0] <= s[i]) ans = s[i] + ans;
      }
        return ans;
    }
};

Tax Rate Changed (1192)

問題
Tax Rate Changed (1192)
税率変更 | Aizu Online Judge


使用言語
C++

方針
・一つの数式で強引に解こうとする→失敗
・素直に本来の値段で全探索

所感
・素直に生きたい

コード

#define xplice(p,q) p * (100 + x) / 100 + q * (100 + x) / 100
#define yplice(p,q) p * (100 + y) / 100 + q * (100 + y) / 100

int x, y, s, ans;

int main()
{
  while (cin>>x>>y>>s, x) {
    ans = 0;
    for (int a = 1; a <= s; a++) {
      for (int b = 1; b <= s; b++) {
        int tmp = xplice(a,b);
        if (tmp < s) {
          continue;
        } else if (tmp == s) {
          ans = max(ans, yplice(a,b));
          //cout<<a<<" "<<b<<" "<<tmp<<" "<<yplice(a,b)<<endl;
        } else {
          break;
        }
      }
    }
    cout<<ans<<endl;
  }

  return 0;
}

AtCoder Beginner Contest 111 C - /\/\/\/

問題
AtCoder Beginner Contest 111 C - /\/\/\/
C - /\/\/\/

使用言語
C++

方針
・iが奇数,偶数の時に登場する数の個数で考える.奇数,偶数でaiがどれくらい出てきたかをp1[i], p2[i]で管理.
・場合分け
 p1,p2のどちらかに複数の最頻値があるor p1,p2の唯一の最頻値が使う
  →その最頻値を使う
 上記以外
  →p1の最頻値とp2の2番目かp2の最頻値とp1の2番目のどちらかを使う(片方の最頻値ともう片方の2番目が同じ数字になることはない,上で弾かれるため)

所感
・バグ祭りで死にましたかかってしまった.無念..
・ACまでに想定していた時間の5倍くらい

コード

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define FOR(i,a,b) for (size_t i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (size_t i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define INF 1e7
#define num 111111

int p1[num], p2[num];
vector<int> a, b;

int main()
{
  int n, m1 = 1, m2 = 1, tmp;

  cin>>n;
  REP(i,n/2) {
    cin>>tmp;
    p1[tmp]++;
    cin>>tmp;
    p2[tmp]++;
  }

  REP(i,num) {
    if (p1[i] > m1) {
      a.clear();
      a.push_back(i);
      m1 = p1[i];
    } else if (p1[i] == m1) {
      a.push_back(i);
    }

    if (p2[i] > m2) {
      b.clear();
      b.push_back(i);
      m2 = p2[i];
    } else if (p2[i] == m2) {
      b.push_back(i);
    }
  }

  if (a.size() > 2 || b.size() > 2) {
    cout<<n - m1 - m2<<endl;
  } else if (a[0] != b[0]) {
    cout<<n - m1 - m2<<endl;
  } else {
    sort(p1, p1+num);
    sort(p2, p2+num);
    int r = max(m1 + p2[num-2], m2 + p1[num-2]);
    cout<<n-r<<endl;
  }

  return 0;
}

SRM 517 Div 1 - Problem 250 CompositeSmash

お久しぶりです.

問題
SRM 517 Div 1 - Problem 250 CompositeSmash
TopCoder Statistics - Problem Statement

使用言語
C++

問題概要
Nを任意の回数(0回でも良い)分割して,targetに(どちらかの整数が)一致したらYes,一致しなければNoを返す.
分割とは,整数xを分割するとき,2以上のy,zに分割され,それらの積はxになる.


方針
・任意の回数→再帰
再帰の中身
  数値がtargetと一致→Yes
  それ以外→全ての分割した数字の組みについてtargetと一致するか判定or更に分割

所感
・動かしたら動いたのでよかった.

コード

bool smash (int a, int b)
{
  if (a == b) {
    return true;
  } else {
    //flag: 素数じゃないか(分割できるか)判定
    //rtn: 全ての分割した結果がtargetに行き着くかを返す
    bool flag = false, rtn = true;
    for (int i = 2; i * i <= a; i++) {
      if (a % i != 0) continue;
      else {
        flag = true;
        rtn = rtn & (smash(i,b) | smash(a/i,b));
      }
    }
    if (flag) return rtn;
    else return false;
  }
}

class CompositeSmash {
    public:
    string thePossible(int N, int target) {
      if (smash(N, target)) return "Yes";
      else return "No";
    }
};

SRM 516 Div 1 - Problem 250 NetworkXOneTimePad

お久しぶりです.

問題
SRM 516 Div 1 - Problem 250 NetworkXOneTimePad
TopCoder Statistics - Problem Statement

使用言語
C++

問題概要
N個のビット列のplaintextsがある.各plaintextsにXORすると全てのciphertextsになるkeyが存在する.その数を求める.

方針
・全てのN個のビット列についてplaintextsにXORしてciphertextsの全てになるか調べる
→時間がかかる(最大2ˆ50)のでダメ

・XORであれば,plaintextsとciphertextsから変換に用いられたkeyの候補をXORで導ける.ciphertextsから全てのplaintextsについてXORするとkeyの候補がある.このkeyの候補は実際のkeyの集合を含む集合である.この候補が全てのciphertextから導かれる場合は,それはkeyである.

・出てきた回数はmapで管理

ex)
{"000", "111", "010", "101", "110", "001"}
{"011", "100"}
→011: 011, 100, 001, 110, 101, 010
 100: 100, 011, 110, 001, 010, 101
両方のkeyの候補に含まれている.

所感
・諸事情で長時間プログラミングしていなかったので,さらに能力が落ちました.
・結論,mapは便利

コード

int N, lp, lc, ans = 0;
map<string, int> mp;

string myXOR (string p, string c)
{
  string tmp(N, '0');
  REP(i,N) tmp[i] = p[i] == c[i] ? '0' : '1';
  return tmp;
}

class NetworkXOneTimePad {
    public:
    int crack(vector<string> plaintexts, vector<string> ciphertexts) {
      N = plaintexts[0].length();
      lp = plaintexts.size();
      lc = ciphertexts.size();

      REP(i,lp){
        REP(j,lc){
          string key_tmp = myXOR(plaintexts[i], ciphertexts[j]);
          if (mp.find(key_tmp) == mp.end()) {
            mp[key_tmp] = 1;
          } else {
            mp[key_tmp]++;
          }
        }
      }

      for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
        if (itr->second == lc) ans++;
      }

        return ans;
    }
};

SRM 503 Div 1 - Problem 250 ToastXToast

問題
SRM 503 Div 1 - Problem 250 ToastXToast
TopCoder Statistics - Problem Statement

使用言語
C++

方針
・色々やるがぐちゃぐちゃ
→・まず,undertoastedの最{小,大}値がovertoasted の最{小,大}値を上回っているのはおかしい.なぜなら,全てのトーストのタイプは,やけなすぎとやけすぎのどちらも存在しているはずだから.
・max(u1, u2, ... , ui) < max(o1, o2, ... , oi)なら
ここの間で区切れば良い.
・その他の場合は,min(u1, u2, ... , ui)より大きく,max(u1, u2, ... , ui)より小さいところで適当にmin(o1, o2, ... , oi)未満のX1を設定してしまい,X1未満のundertoastedはタイプ1,X1より大きいのundertoastedはタイプ2としてしまえば良い.同様に,min(o1, o2, ... , oi)より大きく,max(o1, o2, ... , oi)より小さいところで適当にmax(u1, u2, ... , ui)より大きいのX2を設定してしまい,X2未満のovertoastedはタイプ1,X2より大きいovertoastedはタイプ2としてしまえば良い.(例外は上で弾いている)

ex (sample4)
1 | 2 4
3 5 | 6
(X1,2の値は|の含まれる閉区間であればどこでも良い)

所感
・下手に考えるだけ無駄だった
・マクロ楽しい

コード

#define Min(a) *min_element(a.begin(), a.end());
#define Max(a) *max_element(a.begin(), a.end());

class ToastXToast {
    public:
    int bake(vector<int> undertoasted, vector<int> overtoasted) {
      int min_u = Min(undertoasted);
      int max_u = Max(undertoasted);
      int min_o = Min(overtoasted);
      int max_o = Max(overtoasted);
      if (min_u > min_o || max_u > max_o) return -1;
      else if (max_u < min_o) return 1;
      else return 2;
    }
};