初回 -> はじめに
ABC113を解きました。
3完です！
D問題は難しくて解けていません。
| 問題 | 時間 | アルゴリズム | 実行時間 |
|---|---|---|---|
| A | 1min | - | 8ms |
| B | 6min | - | 7ms |
| C | 20min | 座標圧縮 | 155ms |
まとめ
先にまとめを載せます。これ自体は最後に書いてます。
C問題は座標圧縮です。解いた後に気付きましたw
入力値をソートする必要があるけれど出力時に入力の順番を使う場合は、
「ソート後の順番」→「入力の順番」に変換する用の変数を用意します。
これはchokudaiさんが記事で紹介している問題ですね。
→AtCoder（競技プログラミング）の色・ランクと実力評価、問題例
60minで解きましょうと紹介されているので、それより早く解けてうれしいです。
D問題むずかしかった。
あみだくじかー。あみだくじは実は代数学(群論)なんだよな。
「数学ガール ガロア理論」で勉強したからけっこう簡単に解けるだろうな。
って思っていたら全く解けませんでした。
動的計画法でした。代数学を使う解法はもっと数学的に複雑な問題を解く場合です。
問題の複雑さによって適切なツールを選択するスキルを身に着けたい。。。
A - Discount Fare
int x, y;
cin >> x >> y;
cout << x + y / 2;
半額になるバスの運賃は2番目の入力でもらえるので、1番目の入力と2番目入力の半分を足したものが答えになります。
B - Palace
int n, t, a, h;
cin >> n >> t >> a;
int ans = 0;
double ans_t = 1e9;
for(int i = 0; i < n; ++i)
{
cin >> h;
double temp = abs(a - (t - h * 0.006));
if (temp < ans_t)
{
ans_t = temp;
ans = i + 1;
}
}
cout << ans;
「各地点の平均気温」は入力をもらった時にわかりますね。
（過去や未来の入力値に影響しません。）
そのため、入力をもらうたびに逐次処理しています。
abs(a - (t - h * 0.006))で「平均気温との差」がわかるので、これが最小になるものが答えです。
整数ではなく実数なので型に注意です。
C - ID
using P = pair<ll, ll>;
ll n, m, p, y;
cin >> n >> m;
vector<P> a(m);
map<P, int> ump;
map<int, map<int, P> > mp;
for(int i = 0; i < m; ++i)
{
cin >> p >> y;
P ind = P(p, y);
a[i] = ind;
ump[ind] = i;
mp[p][y] = ind;
}
for(const auto& ip : mp)
{
int ind = 1;
for(const auto& im : ip.second)
{
a[ump[im.second]].second = ind;
ind++;
}
}
cout << setfill('0') << right;
for(const auto& city : a)
{
cout << setw(6) << city.first << setw(6) << city.second << endl;
}
座標圧縮という処理をする問題です。
与えられた数値を、大小関係を保ったまま小さい数字に直します。
[10,5,7,3,2] -> [5,3,4,2,1]というような操作になります。
この問題は、都市番号ごとに分けた後、誕生年でソートします。
ソート後の順番を使ってIDを生成し、元の入力順に出力します。
この「ソート後の順番」→「元の入力順」の変換が複雑でした。
std::mapは自動でソートをしてくれることを利用しました。
map[県番号][誕生年] = 「入力のPair」 となるstd::mapと、
map[入力のPair] = 「入力順」 となる変換用のstd::mapを用意すると、この問題は解けます。
tupleを使うと変数を減らせるのですが、慣れていないので使いませんでした。
以上です。ありがとうございました。