- バチャ
- 苦手なしゃくとり法がたまたま上手く書けたため全完。
ABC036 「座圧」
考察と解法
- 出てくる数字の大小関係だけを覚えとけばいいっぽい。
- 小さい値から順番に、$0, 1, 2, 3, ...$といった感じで値を割り振っていく。これは連想配列で管理すると楽そう
- あとは入力された配列に対し、連想配列の対応通りに値を出力する
コード
# include <bits/stdc++.h>
using namespace std;
int a[111111];
int main() {
int n;
cin >> n;
map<int, int> mp;
for (int i = 0; i < n; i++) {
cin >> a[i];
mp[a[i]] = 0;
}
// 小さい値から順に番号を付けていく
int num = 0;
for (auto x : mp) {
mp[x.first] = num;
num++;
}
for (int i = 0; i < n; i++) {
cout << mp[a[i]] << endl;
}
return 0;
}
- コンテスト中はこんな感じのコードを書いた。
mapにとりあえず$0$を入れておくというのがなんか嫌だったので一度setに入れてからmapに入れた。まあ、どっちもあんま変わんない気がする。
座標圧縮
- 座標の大小関係を保ちつつ値の範囲を狭めることを座標圧縮というらしい。
- 出典
ABC037 「総和」
解法
- 累積和を取る
-
array[i] - array[i-K]の総和を取っていけば答えが求められる
コード
# include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N, K;
ll a[111111];
ll sum[111111];
int main() {
cin >> N >> K;
for (int i = 0; i < N; i++) {
cin >> a[i];
}
// 配列をひとつずらしてコピー
for (int i = 0; i < N; i++) {
sum[i+1] = a[i];
}
// 累積和
for (int i = 0; i < N; i++) {
sum[i+1] += sum[i];
}
ll ans = 0;
for (int i = K; i <= N; i++) {
ans += sum[i] - sum[i-K];
}
cout << ans << endl;
return 0;
}
- コンテスト中は、こんなコードを書いた。入力された配列をそのまま累積和の配列として使ってしまうのは余り良くない気がするため、累積和用の配列を使いようにしたいなーとか思う。
- 一気に値のコピーと累積和をする方法もあるけど、一気に操作するとよくわからなくなるので分けて書いた。
ABC038 「単調増加」
- しゃくとり法は時間をおいて今度書きます
ABC039 「ピアニスト高橋君」
考察と解法
- ある鍵盤から右に20個見るとき、その並び順に注目してみる。
- もしかして、ドからシまでの全てにおいて、右の20個の並び順はユニークになるのでは？と思う。
- ここで実験してみる。ドから始まる
WBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWみたいな文字列を用意して、要素0から20個、要素1から20個、要素3から20個, ...のように文字列を取ってきて連想配列にっこむ。そして表示すると、12通りの文字列がユニークになっていることがわかるので、パターンはユニークである事がわかる。 - それがわかれば、あとは文字列が合っているのがどの鍵盤からスタートしたものなのかを調べれば良い。
コード
# include <bits/stdc++.h>
using namespace std;
// ドから始まる適当な長さの文字列
string p = "WBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBW";
// A[i]: 左からi個目の鍵盤はA[i]となる。
string A[20] = {"Do", "Do", "Re", "Re", "Mi", "Fa", "Fa", "So", "So", "La", "La", "Si"};
int main() {
string s;
cin >> s;
for (int i = 0; i < 12; i++) {
string a = p.substr(i, s.size());
if (a == s) {
cout << A[i] << endl;
return 0;
}
}
return 0;
}
実験コード
- ちなみに、実験のコードはこんな感じ。
# include <bits/stdc++.h>
using namespace std;
string p = "WBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBW";
int main() {
map<string, int> mp;
for (int i = 0; i < 12; i++) {
string a = p.substr(i, 20);
mp[a]++;
}
// x.secondが全部1になっているので、12通りの文字列は全てユニーク
for (auto x : mp) {
cout << x.first << ", " << x.second << endl;
}
return 0;
}
感想
- ド#みたいにな#を全部考え忘れていたためWAを吐かせてしまった。
- 文字列とか数列の並びを見て、法則性があるのでは？とかユニークになるのでは？って考えるのは結構大事そう。（たぶん
ABC040 「柱柱柱柱柱」
考察と解法
- ある地点から1つ先に進むか、2つ先に進むかを決める。
- 組み合わせ的な考え方でやると面倒そう。といかTLEになりそう。
- ということでDPで解く。
コード
# include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e15;
ll N;
ll a[111111];
ll cost[111111];
int main() {
// 初期化
fill(cost, cost + 111111, INF);
// 入力
cin >> N;
for (int i = 0; i < N; i++) {
cin >> a[i];
}
// DP
cost[0] = 0;
for (int i = 0; i < N; i++) {
// 1つ先へ行くとき
if (i + 1 < N) cost[i+1] = min(cost[i+1], cost[i] + abs(a[i] - a[i+1]));
// 2つ先へ行くとき
if (i + 2 < N) cost[i+2] = min(cost[i+2], cost[i] + abs(a[i] - a[i+2]));
}
cout << cost[N-1] << endl;
return 0;
}
- コンテスト中はこんなコードを書いた。けど、僕のコードは最後の処理に無駄を感じた。なので上位陣のコードを参考にリファクタリングした。
- ループ中に
if (i + 1 < N) // 処理っていう書き方なかなか良いなーと思った。
感想
- 一次元のDPはこんな感じで発想して解くのかーといった感想。前は書けなかったのでちょっとはマシになった気がする。
- ただ、2次元のDPとかになると死ぬのでその辺なんとかしたい。