どうしてこうなった・・・
そもそも色々知らなかった所があるので、まずはそこから
nC2, 2重Forループで出来るってマジ？
インデックスをうまいことやればnC2の組み合わせが出来るそうです。
例えば [0,1,2]から二つの組み合わせを取る場合、
[0,1],[0,2],[1,2]
の3通りです。
これをC++の2重Forループでやってみましょう。
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
int main() {
int A = 3;
REP(i, A) {
for (int j = i+1; j < A; j++) {
cout << i << ", " << j << endl;
}
}
return 0;
}
これが実行結果
0, 1
0, 2
1, 2
マジじゃん・・・2個選ぶ時は2重For。この記事を書き残すことによってしっかり覚えましたし・・・
閑話休題。
A問題
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a) (a).begin(),(a).end()
template<class T>
bool chmin(T &a, const T &b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
typedef long long ll;
int main() {
int A,B;
cin >> A >> B;
int ans = (A > (B * 2)) ? A - (B * 2) : 0;
cout << ans << endl;
return 0;
}
ザックリ解説。
- A > B_2 で判定、そもそもカーテンの隠せる範囲の方が大きいなら0 それ以外ならAからB_2を引く
- 出力
B問題
N個のたこ焼きから二個選んだ組み合わせについてごにょっとやる問題です。
NC2でループを回して、二つの値の掛け算した結果を足していけばよいです。
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a) (a).begin(),(a).end()
template<class T>
bool chmin(T &a, const T &b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
template<class T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
typedef long long ll;
// https://atcoder.jp/contests/abc143/tasks/abc143_b
// B - TAKOYAKI FESTIVAL 2019
int main() {
int N;
cin >> N;
int d[N];
REP(i, N) {
cin >> d[i];
}
int ans = 0;
// NC2
REP(i, N) {
for (int j = i + 1; j < N; ++j) {
ans += (d[i] * d[j]);
}
}
cout << ans << endl;
return 0;
}
C問題
左から一文字ずつ見ていって、切り替わるタイミングでcountを増やしていけばよいです。
前の文字は別途どっかの変数に保存しておくこと。
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a) (a).begin(),(a).end()
template<class T>
bool chmin(T &a, const T &b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
template<class T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
typedef long long ll;
int main() {
int N;
cin >> N;
string S;
char before = '_';
cin >> S;
int ans=0;
REP(i, N) {
if (before == S[i]) continue;
else {
before = S[i];
ans++;
}
}
cout << ans << endl;
return 0;
}
D問題
二本選んで前処理でループしといた棒の長さについて二分探索。
ここでその二本は三角形の中で最も長さの長い二本と設定するのが肝(この思考ができなくてつらい)
ずっとこんな感じのコード
https://atcoder.jp/contests/abc143/submissions/8052366
出していたのですがWAの原因が分からず・・・
友人のtunehiraさんに「助けて」ってLINEを送りコードを見ていただいたところ、さっと解決してくれました。本当にありがとうございます。
それはそうとこれが正解コード
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a) (a).begin(),(a).end()
template<class T>
bool chmin(T &a, const T &b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
template<class T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
typedef long long ll;
int main() {
int N = 0;
cin >> N;
int L[N];
REP(i, N) {
cin >> L[i];
}
sort(L, L + N);
// 選択した二本は組み合わせなので重複しない。 よって、「選択した二本は(どっちがどっちか知らんけど)三角形の棒の中で最も長い二本」
// とすれば三本の混合は起きなくなる。
// 例えば 2,3,4は三角形の組み合わせだが、 2,3がForで決まってからの4と 3,2がForで決まってからの4は組み合わせにより重複しないが、
// 3,4が決まってからの2と重複してしまう。
// これを回避するために「選択した二本は(どっちがどっちか知らんけど)三角形の棒の中で最も長い二本」という制約を設けている。
// REPで回しているインデックスの指す値がb,forで回しているインデックスの指す値をaとなり
// a >= b が成立
// また、 三角形の条件の変形より、 max(b-a,a-b) < c < a+b が成立。
// ここから条件を満たす棒の数を二分探索で求められる。
// さらに c =< b <= a が成立するため、 c < a+bは考えなくてよい。
//
int score = 0;
REP(i, N) {
for (int j = i + 1; j < N; ++j) {
int a, b;
a = L[i];
b = L[j];
if (a < b) swap(a, b);
if ((a - b) >= b) continue;
// bの立ち位置の確認
// int *pos = lower_bound(L, L + N, b);
// int last_index = (int) (pos - L);
int *pos = upper_bound(L, L + N, max(b - a, a - b));
int first_index = (int) (pos - L) - 1;
int w = i - first_index - 1;
score += w;
}
}
cout << score << endl;
return 0;
}
そもそもREPのiの方が常に低い(=b, swapいらねぇ)のと、後なぜか僕がbと同じ長さのcは選べないと錯覚してしまったのが原因。
考察が甘かった・・・
求め方が分かっても実装に起こせないとかなり悔しい・・・NKT….
参考
長く悩んでいたソースコードが文字化けしてしまう問題の解決方法が載っていました！本当にありがとうございます。