ABC103 - tqkoh's diary

自分(参加時茶色コーダー())の解いた方法を載せます。

A問題

A - Task Scheduling Problem
3つの整数を並べ、間の差の和を最小化する問題。意味が分かりにくい。

解法

3つの整数を小さい順に並べたとき、となるとすると、答えは

int a,b,c; cin>>a>>b>>c;
cout << max({ a, b, c }) - min({ a, b, c });

B問題

B - String Rotation
ある文字列の一番後ろの文字を一番前に持っていく、という操作を繰り返して文字列にできるか判定する問題。

解法

これは、を2つつなげた文字列の中にが含まれているかを検索するだけで判定できる。 (愚直に書いても通った。)

string s, t; cin >> s >> t; s += s;
cout << (s.find(t) != string::npos ? "Yes\n" : "No\n");

C問題

C - Modulo Summation
が与えられるので、 の最大値を求めるという問題。

解法

のとき、括弧ごとに分けて考えると、

このように、いつかはどこかで全て0になるところ(例では)があるので、そのひとつ前(例では)が最大値になる。よって答えは

int n, in, sum = 0; cin >> n;
rep(i, n) {
    cin >> in; sum += in;
}
cout << sum - n;

D問題

D - Islands War
n個の島が横1列に並んでいて、間にn-1本の橋があり、「 番目と 番目の島が行き来できないようにする」という要望をすべて叶えるために切らなければならない橋の最小値を求める問題。

解法

(ひどい解法です。)
番目と 番目の島が行き来できないようにする、という要望を から までの線分で表すと、たとえば次のようになる。

これをすべて切る縦線が求まればいいのだが、この状態だとどこを切ればいいかわからないので、（をについてソートしてあるものを）が同じもののうちでについて降順でソートする。

こうすることで、上から見ていき、右端が(次の要望の左端)以下の要望(次の図で赤い要望)さえ切ればそれより上はすべて切れることになる。

よって、(1)左端昇順でソート(2)それごとに右端降順でソート(3)右端が(次の要望の左端)以下の要望の数を数え、それ+1(最後)が答えとなる。
(クソコードは以下にありますが見ないでください。本番中にきれいなコードが書けたことはありません)

Submission #2886100 - AtCoder Beginner Contest 103

学んだことメモ

• sort()の仕組みが少しわかった。第三引数にどうやってソートするかを示した関数を渡すことで、pairのfirstを比較して並び替える、などができる。（比較関数、という。。。？）例: pair<int, int>の、secondを降順に並べるそれ

bool secgreater(const pair<int, int>& a, const pair<int, int>& b) return a.second > b.second;

• つかうときは以下のようにする

sort(a, a+n, secgreater);

• 標準の、intとかの降順ソートの比較関数？は()をつけるようだ

sort(b, b+n, greater<int>());

リンク

他にもこんな記事を書いています

qiita.com

tqk.hatenablog.jp