ABC146（当日参加回）
A 3:25
B 7:27
C 10wa
D nosub
E nosub
F nosub
Perf 697
A問題
int main() { cout << setprecision(10); cin >> S; int ans = 6; if(S =="SUN"){ ans =7 ; }else if(S == "MON") ans= 6; else if(S == "TUE") ans= 5; else if (S =="WED") ans =4; else if(S == "THU" ) ans = 3; else if(S == "FRI") ans = 2; else ans = 1; cout << ans << endl; }
A解法
ifでたくさん分岐です。MON とか書き間違えないようにする
上のコード、何これ。汚い。
補足
vimを使っているのに全部手打ちしました。
馬鹿
本当にバカ vim のコマンドを本番でも使えるようにしなさい。 vimの練習してみました
B問題
int main() { cout << setprecision(10); int n ; string s; cin >> n >> s; //A から Z のループ rep(i,s.size()){ int ban = s[i]-'A' + n; ban %= 26; char newban = 'A'+ ban; cout << newban ; } cout << endl; }
解法
親の顔より見た 文字列を数字っぽく扱う問題
A は 0 , 26 B は 1,27 、Z は25,51に対応してる。みたいな感じです。
例えば、元の文字列が、Z で n = 3 だったら、 Z , A , B , C って感じでぐるぐるしてるので
Cに変換する。 https://www.youtube.com/watch?v=i8ltrVR7AD4&feature=youtu.be Zは25に、Cは2に対応していて、(25 + 3 )% 26 = 2
って感じで、2番目の文字であるCを出力すればいい。
Aから見てi番目の文字を出力するには
char hoge = 'A' + i ;とやればいいです i = 0 なら A が取れます。
C問題
解説の写経ACです。この問題から得られるラムダ式とかいうもの！！すごい！！！
ll N,M,H,W,K,A,B; string S; int main() { cout << setprecision(10); auto keta = [&](ll n){ //nの桁数を取得する int res = 0 ; while(n > 0){ n /= 10; res ++; } return res; }; auto money = [&](ll c){ //その時にかかるお金を計算 する ll res = 0; res = A * c + B * keta(c); return res; }; ll X ; cin >> A >> B >> X; ll left = 0 ; ll right = 1e9+1; while(right - left > 1){ ll c = (left + right) / 2; if(money(c) <= X){ left = c; }else right = c; } cout << left << endl; }
解法
答え決め打ち二分探索
left 0は絶対買えるもの。 right 1,000,000,001は絶対買えない者として、
まずその中間を見るc 500,000,000 が買えるなら、left をc にして
次に left 500,000,000 とright 1,000,000,001の間に買える最大値がある。
その中間 c 750,000,000 が買えないなら、 right を c にする。
なぜなら 750,000,000は買えないから 500,000,000と750,000,000の間に買えるものがあるから
って感じで、left と right の中間を見てそれが買えるなら さらに大きいものを求めて、
買えないなら少し控えめを求めて買える最大値を求めようっていう魂胆。
感想
auto keta = [&](ll c){ int res = 0 ; while(c){ c /= 10; res ++ ; } return res; } ;
これラムダ式？なんだろう。main関数内で関数を作るみたいな感じかな
[&]を置くことで、それより前（後もいけるかな？）の変数も使うことが出来るらしいです
(ll c) これは引数
使い方は keta(引数)でいいらしい、不思議。
関数の定義に keta = って感じで使ってるのもうなじめないよね
で、なんか普通の？関数だと hoge = function(引数)みたいな使い方するけど
これに関しては keta(c) がそのまま数として扱える。スゴイ!!
left には買える整数が、rightには買えない整数が入っているよ。
left とright の間はright - left > 1である限り、買えるかどうかはまだ分からない。
一言
ラムダ式の関数表記というものについて [&]とすることで、引数以外に情報を与えることが出来る。 moneyを求める関数でA やBを用いることが出来るのはこのおかげだ。 しかし使うことが出来るのは、それよりも前で宣言しているものだけ。 僕はテンプレートとして、 A , Bをフィールドで宣言しているためAやBを入力しているのはmoney の定義のあとですが使うことが出来ています。 いやああああああああああ
良い問題
お勉強になった。
二分探索って、配列に入ってるものに対してしか使えないと思っていました。
D問題
当日はACできてないです。
vector<int> ans; struct Edge { int to ; int id ; }; vector<vector<Edge>> g; void dfs(int v ,int c = -1 ,int bef= -1){ //vertex,前の色,どこからきたか //今いる頂点と繋がってるところをゲットする。それは、g[v].toに入っている。g[v].sizeで何回やればいいか見る int k = 1; //淹れる色 rep(i,g[v].size()){ int next_vertex = g[v][i].to; //vとnext_vertexをつなぐ頂点の式のIDは、g[v][i].id int ei = g[v][i].id;//idが辺の番号で、next_vertexが、次行く頂点 if(next_vertex == bef) { continue; } if(k == c) { k ++ ; ans[ei] = k; k++; dfs(next_vertex, k-1 , v); }else{ ans[ei] = k; k ++ ; dfs(next_vertex , k-1 , v); } } } int main() { cout << setprecision(10); cin >> N ; g.resize(N);//to , id(辺の番号) ans.resize(N-1); rep(i,N-1){ int a , b ; cin >> a >> b; a--;b--; g[a].push_back((Edge){b,i}); g[b].push_back((Edge){a,i}); } dfs(0); //最大次数を取得したい。 int mx = 0; rep(i,N-1){ mx = max((int)mx,(int)g[i].size()); } cout << mx << endl; rep(i,N-1){ cout << ans[i] << endl; } }
解法
証明はできないけど、必要な色の個数は一番繋がってる物の個数を出力する。 とりあえずメイン関数の
rep(i,N-1){ int a , b ; cin >> a >> b; a--;b--; g[a].push_back((Edge){b,i}); g[b].push_back((Edge){a,i}); }
これで木？なんですかね？を作成します。 どの頂点とどの頂点が繋がってるかをここで作ります。 dfs (Deapth First Serach)が今回の一番大事なところ？ですかね。 とりあえずこの段階では最大次数がいくつかっていうのは必要なくて、 前の頂点からあとの頂点に移動したとき、色を1にする。で、辺に色を付ける。 色をインクリメント。 で色を付けていく段階で、前の頂点と後の頂点をつなぐ色と同じものを塗ろうとしたら、kを+１した色を塗ります。
この結果として、 1,2,..(befcolorは塗れない),って感じで塗っていくと、結果として最大次数が必要な色の個数となるです。
一言
DFS かけた！！よっしゃあああああああああ！！！
