金魚亭日常

読書,ガジェット,競技プログラミング

Imagemagick でハーフサイズの写真をいい感じに分割する

こういうやつを,

元画像

まず左右に分割して,

magick '*.jpg' -quality 100 -compress Lossless -crop 2x1@ +repage separated_%03d.jpg
分割後

分割したやつの片側(分割前に真ん中だった部分)を消す

  • -gravity West で左,East で右
  • -fuzz は同色判定の許容範囲
  • 今回はやらなかったが,本当は偶数奇数で分けて処理するのが良い
  • そもそもきちんとしたカメラならこの操作はいらないかもしれない
magick 'separated_%03d.jpg[0-55]' -gravity West -fuzz 20% -trim +repage trimmed_%03d.jpg

あとは個別に fuzz の値を増やすか,

magick separated.jpg -gravity West -fuzz 50% -trim +repage trimmed.jpg

最終手段として,何ピクセル削るかを決め打ちでやる

magick separated.jpg -gravity West -chop 30x0 trimmed.jpg
トリム後

仕上げに,Exif のサムネイルを更新した方がいいが,今回はやらなかった.

ARC#001 B. リモコン

chokudaiさんが毎日一問問題を選んでくれる #chokudai今日の一問

4日目は

ARC#001 B. リモコン

解答. 前回はRubyで解いていた.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>

using namespace std;

static int A, B;
typedef pair<int, int> P;

int bfs() {
  queue<P> que;
  que.push(P(A, 0));
  P p;
  while (!que.empty()) {
    p = que.front();
    que.pop();
    if (p.first == B) {
      break;
    }
    for (int d : {-1, 1, -5, 5, -10, 10}) {
      if (abs(p.first + d - B) < abs(p.first - B)) {
        que.push(P(p.first + d, p.second + 1));
      }
    }
  }
  return p.second;
}

void solve() { cout << bfs() << endl; }

int main() {
  cin >> A >> B;
  solve();
  return 0;
}

https://atcoder.jp/contests/arc001/submissions/7087376

ABC#112 C. Pyramid

#chokudai今日の一問

3日目は,

ABC#112 C. Pyramid

C - Pyramid

X, Y が 0から100までなので,全探索すればよさそう.

hi が全部0のときが注意,なのか? とか思ったけど,解説読むとそれはないのか.

とりあえず,hi が 0ではない組をどれか選んでおいて,そこを基準にする,という感じ.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>

using namespace std;

static int N;
static vector<int> X;
static vector<int> Y;
static vector<long long> H;

void solve(int x0, int y0, long long h0) {
  for (int cx = 0; cx <= 100; cx++) {
    for (int cy = 0; cy <= 100; cy++) {
      long long ch = h0 + abs(x0 - cx) + abs(y0 - cy);
      bool flag = true;
      for (int i = 0; i < N; i++) {
        long long temp = ch - (abs(X[i] - cx) + abs(Y[i] - cy));
        if (temp < 0) {
          temp = 0;
        }
        if (temp != H[i]) {
          flag = false;
          break;
        }
      }
      if (flag) {
        printf("%d %d %lld\n", cx, cy, ch);
        return;
      }
    }
  }
}

int main() {
  cin >> N;
  X.resize(N);
  Y.resize(N);
  H.resize(N);
  int x0 = 0;
  int y0 = 0;
  long long h0 = 0;
  for (int i = 0; i < N; i++) {
    int x, y;
    long long h;
    cin >> x >> y >> h;
    X[i] = x;
    Y[i] = y;
    H[i] = h;
    if (h > 0) {
      x0 = x;
      y0 = y;
      h0 = h;
    }
  }
  solve(x0, y0, h0);
  return 0;
}

https://atcoder.jp/contests/abc112/submissions/7088885

ABC#026 C - 高橋君の給料

#chokudai今日の一問 2日目は,

ABC#026 C - 高橋君の給料

C - 高橋君の給料

自分より数字の大きい上司はいないので,後ろから順番に給料を決めていく.

二次元vector の初期化のうまいやり方がわからんかった.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>

using namespace std;

static int N;
static vector<vector<int>> B;

void solve() {
  vector<long long> v(N + 1, 1);
  for (int i = N; i > 0; i--) {
    vector<int> x;
    for (int b = 1; b < B[i].size(); b++) {
      x.push_back(v[B[i][b]]);
    }
    if (x.empty()) {
      v[i] = 1;
    } else {
      v[i] = *max_element(x.begin(), x.end()) +
             *min_element(x.begin(), x.end()) + 1;
    }
  }
  printf("%lld\n", v[1]);
}

int main() {
  cin >> N;
  B.resize(N + 1);
  for (int i = 0; i < N + 1; i++) {
    vector<int> v(1);
    B[i] = v;
  }
  for (int i = 0; i < N - 1; i++) {
    int b;
    cin >> b;
    B[b].push_back(i + 2);
  }
  solve();
  return 0;
}

https://atcoder.jp/contests/abc026/submissions/7089830

ABC113 C - ID

いつの間にかできていた #chokudai今日の一問

記念すべき1問目は,多分これ.

ABC113 C - ID

C - ID

素直に実装する.

前回解いたときは,sprintf() とかその辺でハマった気がするけど,今回はvector 2個作って printf() すればいいということに途中で気づいた.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>

using namespace std;

static int N, M;
typedef pair<long long, int> City;
static vector<vector<City>> P;

void solve() {
  vector<int> id1(M + 1);
  vector<int> id2(M + 1);
  for (int i = 1; i < N + 1; i++) {
    sort(P[i].begin(), P[i].end());
    for (int j = 1; j < P[i].size(); j++) {
      id1[P[i][j].second] = i;
      id2[P[i][j].second] = j;
    }
  }
  for (int i = 1; i < M + 1; i++) {
    printf("%06d%06d\n", id1[i], id2[i]);
  }
}

int main() {
  cin >> N >> M;
  P.resize(N + 1);
  for (int i = 0; i < N + 1; i++) {
    vector<City> v(1);
    P[i] = v;
  }
  for (int i = 0; i < M; i++) {
    int p;
    long long y;
    cin >> p >> y;
    P[p].push_back(City(y, i + 1));
  }
  solve();
  return 0;
}

https://atcoder.jp/contests/abc113/submissions/7090478

AtCoder ABC #137

出場はしてない

A. +-x

問題文の通りに最大値を出力する.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>

using namespace std;

void solve(int a, int b) { printf("%d\n", max({a + b, a - b, a * b})); }

int main() {
  int a, b;
  cin >> a >> b;
  solve(a, b);
  return 0;
}

https://atcoder.jp/contests/abc137/submissions/7038126

B

範囲に気を付けて,x - k + 1 から x + k - 1 を出力する

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>

using namespace std;

void solve(int k, int x) {
  int l, r;
  l = max(-1000000, x - k + 1);
  r = min(1000000, x + k - 1);
  for (int i = l; i < r; i++) {
    printf("%d ", i);
  }
  printf("%d\n", r);
}

int main() {
  int k, x;
  cin >> k >> x;
  solve(k, x);
  return 0;
}

https://atcoder.jp/contests/abc137/submissions/7038666

C

アナグラム判定はsortでやって,同じものがいくつあるかを数えて,それぞれについて   {}_n C_2 を全部足す.

一回 int にしていて WAになった.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>

using namespace std;

void solve(map<string, long long> m) {
  long long ans = 0;
  for (auto item : m) {
    ans += item.second * (item.second - 1) / 2;
  }
  printf("%lld\n", ans);
}

int main() {
  int n;
  cin >> n;
  map<string, long long> m;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    m[s] += 1;
  }
  solve(m);
  return 0;
}

https://atcoder.jp/contests/abc137/submissions/7038666

D

最終日からさかのぼって処理する. 残り日数以下の仕事をque に全部入れて,報酬が最大のものを取り出す,ということをやっていく.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>

using namespace std;

typedef struct {
  int A;
  int B;
} Job;

bool comp(const Job &a, const Job &b) { return a.A < b.A; }

void solve(int N, int M, vector<Job> jobs) {
  priority_queue<int> que;
  int ans = 0;
  int i = 0;
  for (int m = 0; m <= M; m++) {
    while (jobs[i].A <= m && i < N) {
      que.push(jobs[i].B);
      i++;
    }
    if (!que.empty()) {
      int b = que.top();
      que.pop();
      ans += b;
    }
  }
  printf("%d\n", ans);
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<Job> jobs(N);
  for (int i = 0; i < N; i++) {
    int A, B;
    cin >> A >> B;
    Job job = {A, B};
    jobs[i] = job;
  }
  sort(jobs.begin(), jobs.end(), comp);
  solve(N, M, jobs);
  return 0;
}

https://atcoder.jp/contests/abc137/submissions/7047537

Codeforces Round #580 Div2

最近は codeforces にも頑張って出ているが,こちらも出るたびにratingが下がっていく…

しかし,codeforces 出ると AtCoder は使いやすいなぁと思う.

Cまで開けたが,わからんかった.

A. Choose Two Numbers

普通に総当たり

n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
 
 
def solve():
    for i in range(n):
        for j in range(m):
            if (a[i] + b[j] not in a) and (a[i] + b[j] not in b):
                print(a[i], b[j])
                return
 
 
solve()

https://codeforces.com/contest/1206/submission/59005861

B. Make Product Equal One

1 か -1 の近いほうにして, -1 にするのが奇数個だったら, -1 => 1 or 1 => -1 のコストが小さいほうを変更する. 解説では 0を基準にしていた. もっとすっきり書けた気がする.

n = int(input())
a = list(map(int, input().split()))
neg = []
pos = []
 
for aa in a:
    if abs(1 - aa) < abs(-1 - aa):
        pos.append(aa)
    else:
        neg.append(aa)
 
ans = 0
if len(neg) % 2 != 0:
    if len(pos) == 0:
        d = 0
        cost = 10**9 + 1
        for aa in neg:
            if cost > abs(1 - aa) - abs(-1 - aa):
                cost = abs(1 - aa) - abs(-1 - aa)
                d = aa
        ans += sum([abs(-1 - x) for x in neg])
        ans -= abs(-1 - d)
        ans += abs(1 - d)
    else:
        d1 = 0
        cost1 = 10**9 + 1
        for aa in neg:
            if cost1 > abs(1 - aa) - abs(-1 - aa):
                cost1 = abs(1 - aa) - abs(-1 - aa)
                d1 = aa
        d2 = 0
        cost2 = 10**9 + 1
        for aa in pos:
            if cost2 > abs(-1 - aa) - abs(1 - aa):
                cost2 = abs(-1 - aa) - abs(1 - aa)
                d2 = aa
 
        ans += sum([abs(1 - x) for x in pos])
        ans += sum([abs(-1 - x) for x in neg])
        if cost1 < cost2:
            ans -= abs(-1 - d1)
            ans += abs(1 - d1)
        else:
            ans -= abs(1 - d2)
            ans += abs(-1 - d2)
else:
    ans += sum([abs(1 - x) for x in pos])
    ans += sum([abs(-1 - x) for x in neg])
 
print(ans)

https://codeforces.com/contest/1206/submission/59026990