ABC161自分なりのまとめ

ABC161自分なりのまとめ

ABC161に出題された問題について、自分なりの理解をまとめます。

A-ABC Swap

x, y, zを受け取り、z, x, yの順番で出力すれば良い。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{
  int x, y, z;
  cin >> x >> y >> z;
  cout << z << " " << x << " " << y << " " << endl;
}

B-Popular Vote

商品がN個あり、各商品iはAi表を得ている。
この中から人気商品をM個選ぶ。(人気商品は得票数が1/4M以上)
Aiの総和を取った総得票数をTとしたとき、Ai * 4M >= Tを満たす商品をM個選べるか試せば良い。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{
  int n, m;
  cin >> n >> m;
  v a(n, 0);
  int total = 0;
  rep(i, n)
  {
    cin >> a[i];
    total += a[i];
  }
  int cnt = 0;
  rep(i, n)
  {
    if(a[i] * 4 * m >= total) cnt++;
  }
  if(cnt >= m) {
    cout << "Yes" << endl;
  }else {
    cout << "No" << endl;
  }
}

C-Replacing Integer

twitterで話題になってたのかな？
個人的にはいつものC問題という感じがした。
xをxとkの差の絶対値で置き換えるため、xがkよりも大きい間は単調減少する。
xがkよりも小さくなると、その一つ手前の値と振動するようになる。
よって、kよりも大きい最小のxとkよりも小さいxとを比べて小さくなる方を出力すれば良い。
最初に与えられる整数をx_0として、x_i = x_(i-1) - kという漸化式をたてる。
すると、x_i = x_0 - ikという式が得られる。
この式からx_iがkより大きい最小のiを求めて、i + 1とiの場合で整数が小さいものを答えとする。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{
  ll n, k;
  cin >> n >> k;
  ll i = -1 + (n + (k - 1)) / k;
  ll c1 = (n - i * k);
  ll c2 = abs(n - (i + 1) * k);
  cout << (c1 < c2 ? c1 : c2) << endl;
}

D-Lunlun Number

解けなかった。悔しい。
この問題で重要だと思うのは

• ある整数xが与えられたら、xより1桁大きいLunlun Numberを作ることができる
• 数の大小は辞書順であるため、xとyから作ったLunlun Numberはxとyの順序関係を維持する

の2つだと思う。
上記より、最初に1~9までをキューに入れておき

• 取り出した値numのmod 10をlastとする(最後の桁)
• 取り出した値numが10で割り切れなかったら、num * 10 + last - 1をキューに入れる
• num * 10 + lastをキューに入れる
• lastが9で無かったら、num * 10 + last + 1をキューに入れる

この手順を繰り返し、k回目に取り出した値が答えとなる。 うーん、シンプルですね。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{  
  int k;
  cin >> k;
  queue<ll> q;
  for(int i = 1; i < 10; i++)
  {
    q.push(i);
  }
  for(int i = 0; i < k; i++)
  {
    ll num = q.front(); q.pop();
    if(i == k - 1) {
      cout << num << endl;
      break;
    }
    ll last = num % 10;
    if(last != 0) q.push(num * 10 + last - 1);
    q.push(num * 10 + last);
    if(last != 9) q.push(num * 10 + last + 1);
  }
}