AtCoderチャレンジまとめ（6） - AtCoder Beginner Contest 119
やりたいこと
そんなわけでAtCoderにチャレンジ ！
チャレンジコンテスト
変数名が適当なのはご愛嬌
A問題: Still TBD
文字列 S が入力されます。これは、西暦 2019 年の実在する日付を yyyy/mm/dd の形式で表したものです。(例えば、2019 年 4 月 30日は 2019/04/30 と表されます。)
Sが表す日付が 2019 年 4 月 30 日またはそれ以前なら Heisei、そうでなければ TBD と出力するプログラムを書いてください。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S が表す日付が 2019 年 4 月 30 日またはそれ以前なら Heisei、そうでなければ TBD と出力せよ。
自分の回答
#include <iostream> using namespace std; int main() { std::string s; cin >> s; char cary[10]; s.copy(cary, 10); std::string sn(""); for (int i=0;i<10;i++){ if (i != 4) { if (i != 7){ sn += cary[i]; } } } int num = atoi(sn.c_str()); if(num>20190430){ cout << "TBD" << endl; } else { cout << "Heisei" << endl; } return 0; }
B問題:
高橋くんは N人の親戚からお年玉をもらいました。
N個の値 x1,x2,...,xN と N 個の文字列 u1,u2,...,uN が入力されます。各文字列 ui は JPY または BTC であり、xi と ui が i人目の親戚からのお年玉の内容を表します。
例えば、x1=10000, u1= JPY であれば 1 人目の親戚からのお年玉は 10000 円であり、x2= 0.10000000, u2= BTC であれば 2 人目の親戚からのお年玉は 0.1ビットコインです。
ビットコインを 1.0BTC あたり 380000.0 円として換算すると、高橋くんがもらったお年玉は合計で何円に相当するでしょうか？
入力
入力は以下の形式で標準入力から与えられる。
N
x1 u1
x2 u2
:
xN uN
出力
高橋くんが受け取ったお年玉が合計で Y 円に相当するとき、値 Y(整数とは限らない) を出力せよ。
出力は、ジャッジの出力との絶対誤差または相対誤差が 10−5以下のとき正解と判定される。
自分の回答
#include <iostream> using namespace std; int main() { int n; cin >> n; double x; std::string u; std::string str="JPY"; double ans; for (int i; i<n;i++){ cin >> x >> u; if (std::string(u)==str){ ans += x; } else { ans += x * 380000.0; } } cout << ans << endl; return 0; }
C問題: Synthetic Kadomatsu
あなたは N 本の竹を持っています。これらの長さはそれぞれ l1,l2,...,lNです (単位: センチメートル)。
あなたの目的は、これらの竹のうち何本か (全部でもよい) を使い、長さが A,B,Cであるような 3本の竹を得ることです。そのために、以下の三種類の魔法を任意の順に何度でも使うことができます。
延長魔法: 1 MP (マジックポイント) を消費し、1 本の竹を選んでその長さを 1増やす。 短縮魔法: 1 MP を消費し、1 本の長さ 2 以上の竹を選んでその長さを 1減らす。 合成魔法: 10 MP を消費し、2 本の竹を選んで接続し 1 本の竹とする。この新たな竹の長さは接続した 2本の竹の長さの合計に等しい。(以後、この竹に対してさらに魔法を使用することもできる。)目的を達成するには、最小でいくつの MP が必要でしょうか？
入力
入力は以下の形式で標準入力から与えられる。
N A B C
l1
l2
:
lN
出力
目的の達成に必要な MP の最小量を出力せよ。
自分の回答
時間以内に解けなかった...Cが解けないのは辛い。
全探索大事。
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; int N; int A,B,C; long long brute_force_search(int cnt, int a, int b, int c, int L[]) { long long INF = std::pow(10, 9.0); if (cnt==N) { if ((a!=0)&&(b!=0)&&(c!=0)){ return std::abs(a-A)+std::abs(b-B)+std::abs(c-C)-30; } else { return INF; } } vector<long long> ansc(4); ansc[0] = brute_force_search(cnt+1, a, b, c, L); ansc[1] = brute_force_search(cnt+1, a+L[cnt], b, c, L)+10; ansc[2] = brute_force_search(cnt+1, a, b+L[cnt], c, L)+10; ansc[3] = brute_force_search(cnt+1, a, b, c+L[cnt], L)+10; int min = *std::min_element(ansc.begin(), ansc.end()); return min; } int main() { cin >> N >> A >> B >> C; int len[N]; for (int i; i<N;i++){ cin >> len[i]; } long long ans; ans = brute_force_search(0, 0, 0, 0, len); cout << ans << endl; return 0; }
ちょっとだけ解説
a,b,c=0の状態から始まり初期の１本追加するときに10を足しているので、
最後にABC3本分の30を引いているのと、
一本も追加しない場合は成り立たないのでINFとしてる。
D問題: Lazy Faith
東西方向に伸びる道路に沿って A 社の神社と B 軒の寺が建っています。 西から i 社目の神社は道路の西端から si メートルの地点に、西から i 軒目の寺は道路の西端から tiメートルの地点にあります。
以下の Q個の問いに答えてください。
問 i (1≤i≤Q): 道路の西端から xi メートルの地点から出発して道路上を自由に移動するとき、神社一社と寺一軒を訪れるのに必要な最小の移動距離は何メートルか？ (必要数を超えた数の寺社を通過してもよい。)
入力
入力は以下の形式で標準入力から与えられる。
A B Q
s1
:
sA
t1
:
tB
x1
:
xQ
出力
Q 行出力せよ。i 行目に問 i への答えを出力すること。
自分の回答
これも時間以内にとけなかった。二分探索がポイント。
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { int A,B,Q; cin >> A >> B >> Q; vector<long long> jin(A+2); vector<long long> tera(B+2); long long INF = std::pow(10, 18); jin[0] = -INF; jin[A+1] = INF; tera[0] = -INF; tera[B+1] = INF; for (int i=1; i<A+1;i++){ cin >> jin[i]; } for (int i=1; i<B+1;i++){ cin >> tera[i]; } long long q; for (int i; i<Q;i++){ cin >> q; long long b = upper_bound(jin.begin(), jin.end(), q) - jin.begin(); long long d = upper_bound(tera.begin(), tera.end(), q) - tera.begin(); long long ans = INF; vector<long long> jinv{jin[b-1],jin[b]}; vector<long long> terav{tera[d-1],tera[d]}; vector<long long> dv(3); for (auto j: jinv) { for (auto t: terav){ dv[0] = std::abs(j-q)+std::abs(t-j); dv[1] = std::abs(t-q)+std::abs(j-t); dv[2] = ans; ans = *std::min_element(dv.begin(), dv.end()); } } cout << ans << endl; } return 0; }
二分探索参考
所感
Cが解けずに時間が経過すると、めっちゃ焦る。。。冷静に解決のための手段を一個ずつ洗い出せるようにしないと。
まずいろんなアルゴリズムの知識を網羅的につけて正しく選択できるところを目指そう。
