ABC163自分的振り返り

ABC163に出題された問題を自分なりにまとめました。

A - Circle Pond

2 * pi * rを出力すれば良い。
精度に注意

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

#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 r;
  cin >> r;
  cout << fixed;
  cout << setprecision(3) << r * 2 * M_PI << endl;
}

B - Homework

特に制限もないので宿題にかかる日数を計算して夏休みの日数から引けばよい。
結果が負になったら終わらせられない。

#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, m;
  cin >> n >> m;
  ll total = 0;
  rep(i, m)
  {
    ll temp;
    cin >> temp;
    total += temp;
  }
  total = n - total;
  if(total < 0) {
    cout << -1 << endl;
  }else{
    cout << total << endl;
  }
}

C - management

入力文字列中に現れたAiの数が直属の部下の人数

#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;
  cin >> n;
  v a(n, 0);
  rep(i, n - 1)
  {
    int temp;
    cin >> temp;
    a[temp - 1]++;
  }
  rep(i, n)
  {
    cout << a[i] << endl;
  }
}

D - Sum of Large Numbers

和についてもmodを取ると勘違いして、一生無理だろって思ってた。
まず最初に気づくのは、1からNまでの総和が絶対に10¹⁰⁰を超えることはないこと。
これによって、選んだ数にが異なる場合に和が等しくなることはないと分かる。
あとは、1からNの中からK個以上選んだときに、一意な和が何種類あるかを考えれば良い。
これは、小さい順にK個選んだ総和と大きい順にK個選んだ総和の差と等しくなる。
(最小の総和をSmin, 最大の総和をSmaxとしたとき、この間の値は自由に作り出すことができるため)
よってKから順番にNまでありえる総和の個数を足し合わせていけば良い。

#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>;


ll mod = 1e9 + 7;

ll calc(ll i, ll n) {
  ll smallest = (i - 1) * i / 2;
  ll largest = (n * (n + 1) / 2) - ((n - i) * (n - i + 1) / 2);
  return (largest - smallest) + 1;
}

int main()
{
  ll n, k;
  cin >> n >> k;
  ll ans = 0;
  for(int i = k; i <= n + 1; i++)
  {
    ans += calc(i, n);
    ans %= mod;
  }
  cout << ans << endl;
}

E - Active Infants

難しい。
解法に至るまでの道筋があっているかはわからないが、自分なりのまとめ。
まず最初に幼児の中から2人を取ってきたときどの様に並べ替えるのが良いかを考える。
左詰めにすると仮定し、それぞれの活発度をA, BとしA > Bとすると、大きい方をなるべく外側に持っていったほうが良いことが分かる。
これはBの増加分がAの減少分より小さいためである。
例えば
A, B,,,,,,
と並んでいるとき
B, A,,,,,,と並べ替えると
全体の嬉しさの合計は-A + Bとなる。
右詰めの場合も同様である。
よって、活発度が高い順から左右に振り分けていけばうれしさを最大化することができる。
あとは状態の更新方法を考えていけば良い。
N * Nの二次元配列dpを定義し、dp[i][j]に左側からi人、右側からj人詰めたときの嬉しさの総和の最大値を格納する。
状態遷移は

dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 増加分)
dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + 増加分)

maxを取る必要があるのは、それぞれのi, jの組に対して2通り到達する経路があるから。
ちなみに、これは有名なdpらしいです。

#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;
  cin >> n;
  vector<pl> a(n, {0, 0});
  rep(i, n)
  {
    ll temp;
    cin >> temp;
    a[i] = {temp, i};
  }
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  vector<vl> dp(n + 1, vl(n + 1, 0)); //dp[i][j] 左からi番目と右からj番目まで並べたときの嬉しさの合計の最大
  ll result = 0;
  rep(i, n + 1)
  {
    rep(j, n + 1)
    {
      if(i + j == n) {
        result = max(result , dp[i][j]);
        break;
      }
      int index = i + j;
      //左側に追加
      dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + abs(a[index].second - i) * a[index].first);
      //右側に追加
      dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + abs(a[index].second - (n - 1 - j)) * a[index].first);
    }
  }
  cout << result << endl;
}

盆栽エンジニアリング日記

勉強したことをまとめるブログ

ABC163自分なりのまとめ