ABC128 D Lamp

問題の解き方よりも実装のほうが大変だった問題。他の人の解き方を見て、条件分岐の少ない再実装をしました。配列の実装を1から始めるのがポイントのようです。

 

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
int h, w;
cin >> h >> w;
vector<string> s(h);
for (auto&& u : s) cin >> u;

vector<vector<int>> l(h + 2, vector<int>(w + 2, 0));
vector<vector<int>> r(h + 2, vector<int>(w + 2, 0));
vector<vector<int>> u(h + 2, vector<int>(w + 2, 0));
vector<vector<int>> d(h + 2, vector<int>(w + 2, 0));

for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++) {
if (s[i - 1][j - 1] == '.') {
l[i][j] = l[i][j - 1] + 1;
u[i][j] = u[i - 1][j] + 1;
}
}

for (int i = h; i >= 1; i--)
for (int j = w; j >= 1; j--) {
if (s[i - 1][j - 1] == '.') {
r[i][j] = r[i][j + 1] + 1;
d[i][j] = d[i + 1][j] + 1;
}
}

int ret = 0;
for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++) {
if (s[i - 1][j - 1] == '.')
ret = max(ret, l[i][j] + u[i][j] + r[i][j] + d[i][j] - 3);
}
cout << ret << endl;
}

ABC128 C-Switches

典型的なbit演算の問題として自分なりに整理しました。

コンテスト時には、bitの配列として処理したものを、各bitを桁とする一つの数字にすると処理が簡単になるのが、目からウロコでした。

ただそれなりに独特の考え方をするので慣れていかなければと思います。

（特に入力時に苦労しました）

 

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)

signed main() {
int n, m;
cin >> n >> m;
vector<int> sw(n, 0);
int p = 0, ans = 0;
rep(i, m) {
int x;
cin >> x;
rep(j, x) {
int y;
cin >> y;
y--;
sw[y] |= (1 << i);
}
}

rep(i, m) {
int x;
cin >> x;
p |= (x << i);
}

rep(bit, 1 << n) {
int tmp = 0;
rep(i, n) {
if ((bit >> i) & 1) tmp ^= sw[i];
}
if (tmp == p) ans++;
}
cout << ans << endl;
return 0;
}

ARC 001 B リモコン

はじめ通貨問題のように貪欲法で解いたところ撃沈。

通貨問題では、使うコインをa,b,cと昇順に並べたときbが

aの倍数、cがbの倍数であれば、貪欲法が使えるが、この問題では

プラス・マイナス両側から近づくので使えないらしい。

回答をみてBFSで実装しました。温度に対する操作回数を保存するのは嫌だったので(温度がマイナスになる可能性もあるので)、mapを使いました。初めてBFSでmapを使いましたが、相性はいいと思います。

 

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a,b;cin>>a>>b;
    map<int,int>cnt;
    vector<int>diff={1,5,10,-1,-5,-10};
    cnt[a]=0;
    queue<int>que;
    que.push(a);

    while(!que.empty()){
        int x=que.front();que.pop();
        if(x==b)cout<<cnt[x]<<endl,exit(0);
        for(auto&& u:diff){
            int y=x+u;
            if(cnt.count(y)==0){
            cnt[y]=cnt[x]+1;
            que.push(y);
            }
        }
        }

    }
 

 

 

CODE FESTIVAL 2018 Final (Parallel) C - Telephone Charge

結構難しいlower_boundですが、面白い使い方を見つけたので、使ってみました。

 

イテレータから値を取り出す書き方は、auto x=*lower_bound(.....)といった*を使う方法しか知っていましたが、

一旦auto it=lower_bound(.....)とイテレータ自体を変数で受け取っておいてから,

it[0],it[-1],it[1]と前後の値も配列のように取り出す方法は知りませんでした。

配列の端っこのコーナケースを処理するのに便利そうです。

 

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
int inf = 1e18;
struct charge {
int a, b;
charge(){};
charge(int a_, int b_) { a = a_, b = b_; };
bool operator<(const charge& o) const { return a < o.a; }
};

signed main() {
int n, m;
cin >> n;
vector<charge> c;
rep(i, n) {
int a, b;
cin >> a >> b;
c.push_back({a, b});
}
cin >> m;
vector<int> t(m);
for (auto&& u : t) cin >> u;
sort(begin(c), end(c));
rep(i, m) {
auto it = lower_bound(begin(c), end(c), charge(t[i], -1));

if (it == c.begin())
cout << it[0].b << endl;
else if (it == c.end())
cout << (it[-1].b + t[i] - it[-1].a) << endl;
else
cout << min(it[-1].b + t[i] - it[-1].a, it[0].b) << endl;
}
}

 

 

M-SOLUTIONS プロコンオープン　E - Product of Arithmetic Progression

最近作った剰余演算用のライブラリを試すのにうってつけの問題。

nCmは使わないけど、累乗や逆数、そしておまけで作ったnPmの計算を使っています。

計算自体はよくある手法だと思うけど、配列をコンストラクタの中で初期化するので

サンプルごとにメモリの使用量が変化するのが見ていて楽しいです。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repf(i, j, n) for (int i = (j); i < (n); i++)
#define repr(i, n) for (int i = (n)-1; i >= 0; i--)

struct modCalc {
int mod;
int n;
vector<int> fact, invfact;
modCalc(){};

modCalc(int _mod, int _n) {
mod = _mod, n = _n;
fact.resize(n + 1, 1);
invfact.resize(n + 1, 1);

for (int i = 0; i < n; i++) fact[i + 1] = fact[i] * (i + 1) % mod;
invfact[n] = modinv(fact[n]);
for (int i = n; i > 1; i--) invfact[i - 1] = invfact[i] * i % mod;
};

int modpow(int x, int n) {
int ret = 1;
while (n > 0) {
if (n & 1) (ret *= x) %= mod;
(x *= x) %= mod;
n >>= 1;
}
return ret;
}
int modinv(int x) { return modpow(x, mod - 2); }
int nCm(int x, int y) {
if (y == 0)
return 1;
else
return fact[x] * invfact[y] % mod * invfact[x - y] % mod;
}
int nPm(int x, int y ) {
return fact[x] * invfact[x - y] % mod;
}
};

signed main() {
int q;
cin >> q;
vector<int> x(q), d(q), n(q);
rep(i, q) cin >> x[i] >> d[i] >> n[i];
int mod = 1e6 + 3;
modCalc mc(mod, mod - 1);

rep(i, q) {
int x0 = x[i], d0 = d[i], n0 = n[i];
if (x0 == 0) {
cout << 0 << endl;
continue;
}
if (d0 == 0) {
cout << mc.modpow(x0, n0) << endl;
continue;
}

int dn = mc.modpow(d0, n0);
int xd = mc.modinv(d0) * x0 % mod;
if (xd + n0 - 1 >= mod) {
cout << 0 << endl;
continue;
}
int ret = mc.nPm(xd + n0 - 1, n0) * dn % mod;
cout << ret << endl;
}
}

 

 

ABC128 B Guidebook

オブジェクトを作って、それに独自の順序を与える方法を

事前に調べていたので、僕にしては爆速で解くことができました。

 

#include <bits/stdc++.h>
using namespace std;

struct Restaurant {
string s;
int p;
int i;
Restaurant(){};
Restaurant(string s_, int p_, int i_) {
s = s_;
p = p_;
i = i_;
};
bool operator<(const Restaurant& o) const {
return tie(s, o.p) < tie(o.s, p);
}
};

int main() {
int n;
cin >> n;
vector<Restaurant> r(n);
for (int i = 0; i < n; i++) {
cin >> r[i].s >> r[i].p;
r[i].i = i + 1;
}
sort(begin(r), end(r));
for (auto&& u : r) cout << u.i << endl;
}

典型問題

atcoderの問題はちょっと捻ったものが多いので、アルゴリズムを習得するために解くと良い典型問題が逆に少ない気がします。

そこで自分用のメモとして典型問題として使えるAtcoderの問題を上げておきます。

(主観的な意見なのであしからず)