ABC163自分なりのまとめ
ABC163自分的振り返り
ABC163に出題された問題を自分なりにまとめました。
A - Circle Pond
2 * pi * rを出力すれば良い。
精度に注意
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #include <iomanip> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; int main() { int r; cin >> r; cout << fixed; cout << setprecision(3) << r * 2 * M_PI << endl; }
B - Homework
特に制限もないので宿題にかかる日数を計算して夏休みの日数から引けばよい。
結果が負になったら終わらせられない。
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; int main() { ll n, m; cin >> n >> m; ll total = 0; rep(i, m) { ll temp; cin >> temp; total += temp; } total = n - total; if(total < 0) { cout << -1 << endl; }else{ cout << total << endl; } }
C - management
入力文字列中に現れたAiの数が直属の部下の人数
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; int main() { int n; cin >> n; v a(n, 0); rep(i, n - 1) { int temp; cin >> temp; a[temp - 1]++; } rep(i, n) { cout << a[i] << endl; } }
D - Sum of Large Numbers
和についてもmodを取ると勘違いして、一生無理だろって思ってた。
まず最初に気づくのは、1からNまでの総和が絶対に10100を超えることはないこと。
これによって、選んだ数にが異なる場合に和が等しくなることはないと分かる。
あとは、1からNの中からK個以上選んだときに、一意な和が何種類あるかを考えれば良い。
これは、小さい順にK個選んだ総和と大きい順にK個選んだ総和の差と等しくなる。
(最小の総和をSmin, 最大の総和をSmaxとしたとき、この間の値は自由に作り出すことができるため)
よってKから順番にNまでありえる総和の個数を足し合わせていけば良い。
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; ll mod = 1e9 + 7; ll calc(ll i, ll n) { ll smallest = (i - 1) * i / 2; ll largest = (n * (n + 1) / 2) - ((n - i) * (n - i + 1) / 2); return (largest - smallest) + 1; } int main() { ll n, k; cin >> n >> k; ll ans = 0; for(int i = k; i <= n + 1; i++) { ans += calc(i, n); ans %= mod; } cout << ans << endl; }
E - Active Infants
難しい。
解法に至るまでの道筋があっているかはわからないが、自分なりのまとめ。
まず最初に幼児の中から2人を取ってきたときどの様に並べ替えるのが良いかを考える。
左詰めにすると仮定し、
それぞれの活発度をA, BとしA > Bとすると、大きい方をなるべく外側に持っていったほうが良いことが分かる。
これはBの増加分がAの減少分より小さいためである。
例えば
A, B,,,,,,
と並んでいるとき
B, A,,,,,,と並べ替えると
全体の嬉しさの合計は-A + Bとなる。
右詰めの場合も同様である。
よって、活発度が高い順から左右に振り分けていけばうれしさを最大化することができる。
あとは状態の更新方法を考えていけば良い。
N * Nの二次元配列dpを定義し、dp[i][j]に左側からi人、右側からj人詰めたときの嬉しさの総和の最大値を格納する。
状態遷移は
- dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 増加分)
- dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + 増加分)
maxを取る必要があるのは、それぞれのi, jの組に対して2通り到達する経路があるから。
ちなみに、これは有名なdpらしいです。
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; int main() { int n; cin >> n; vector<pl> a(n, {0, 0}); rep(i, n) { ll temp; cin >> temp; a[i] = {temp, i}; } sort(a.begin(), a.end()); reverse(a.begin(), a.end()); vector<vl> dp(n + 1, vl(n + 1, 0)); //dp[i][j] 左からi番目と右からj番目まで並べたときの嬉しさの合計の最大 ll result = 0; rep(i, n + 1) { rep(j, n + 1) { if(i + j == n) { result = max(result , dp[i][j]); break; } int index = i + j; //左側に追加 dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + abs(a[index].second - i) * a[index].first); //右側に追加 dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + abs(a[index].second - (n - 1 - j)) * a[index].first); } } cout << result << endl; }
ABC162自分なりのまとめ
ABC162自分なりのまとめ
ABC162に出題された問題について、自分なりの理解をまとめます。
今回は50分ほどで4完でしたがレートは落ちました。
やっぱり4完の場合は速解きできないと水色パフォーマンスは出ませんね。
A-Lucky-7
文字列に変換して、各桁に7が入っていないかを調べれば簡単です。
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; int main() { int n; cin >> n; string s = to_string(n); for(int i = 0; i < s.size(); i++) { if(s[i] == '7') { cout << "Yes" << endl; return 0; } } cout << "No" << endl; }
B-FizzBuzz Sum
1からNまで順番に見ていって、3と5で割り切れない値を足していけばいいです。
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; int main() { int n; cin >> n; ll result = 0; for(int i = 1; i <= n; i++) { if(i % 3 != 0 && i % 5 != 0) { result += i; } } cout << result << endl; }
C - Sum of gcd of Tuples (Easy)
制約がk <= 200とゆるいので、愚直に3重ループを回してgcdをとっても間に合うと判断。
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; template <typename number> pair<number, number> extended_euclid(number a, number b) { number r0, r1, a0, a1, b0, b1; r0 = a; r1 = b; a0 = 1; a1 = 0; b0 = 0; b1 = 1; while (r1>0) { number q1 = r0 / r1; number r2 = r0 % r1; number a2 = a0 - q1 * a1; number b2 = b0 - q1 * b1; r0 = r1 ; r1 = r2; a0 = a1 ; a1 = a2; b0 = b1 ; b1 = b2; } number c = r0; a = a0; //x b = b0; //y return {a, c}; } int main() { int k; cin >> k; ll result = 0; for(int i = 1; i <= k; i++) { for(int j = 1; j <= k; j++) { for(int l = 1; l <= k; l++) { if(i == 1 || j == 1 || l == 1){ result++; }else{ int temp = extended_euclid(i, j).second; temp = extended_euclid(temp, l).second; result += temp; } } } } cout << result << endl; }
D - RGB Triplets
まず1つ目の条件である
- Si != Sj && Si != Sk && Sj != Sk
を満たす組み合わせを数えることを考える。
愚直にやる場合は、3重ループを回せば見つかるが計算量的に間に合わないので高速化を考える。
文字種が2種類の場合は、ある添字iを見ているとき、iより後ろに別の文字種が何個あれば分かれば、O(1)で
組を計算することができる。
3種類の場合は、添字を2つ固定して同様のことを行えばよいので、R,G,B各種について累積和をとっておき
上記の計算を行うことで1つ目の条件を満たす組はO(n2)で計算可能。
次に2つ目の条件
- j - i != k - j
を考える。
これは、i, j, kの幅を固定して探索することで添字1につきO(n)で1つ目と2つ目の条件を満たす組の個数を
計算することができる。
よって、各添字についてこの処理を行い、最初に求めた組数から引くことでO(n2)で1,2を満たす組の個数が
求まる。
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; void createA(string &s, v &target, char c){ if(s[0] == c) target[0] = 1; var for(inservice.Output { if(s[i] == c){ target[i] = target[i - 1] + 1; }else{ target[i] = target[i - 1]; } } } int main() { int n; cin >> n; string s; cin >> s; v r(n, 0); v g(n, 0); v b(n, 0); createA(s, r, 'R'); createA(s, g, 'G'); createA(s, b, 'B'); ll result = 0; rep(i, n) { for(int j = i + 1; j < n; j++) { if(s[i] == s[j]) continue; if(s[i] == 'R'){ if(s[j] == 'B') result += g[n - 1] - g[j]; if(s[j] == 'G') result += b[n - 1] - b[j]; }else if(s[i] == 'G'){ if(s[j] == 'R') result += b[n - 1] - b[j]; if(s[j] == 'B') result += r[n - 1] - r[j]; }else if(s[i] == 'B'){ if(s[j] == 'R') result += g[n - 1] - g[j]; if(s[j] == 'G') result += r[n - 1] - r[j]; } } } rep(i, n) { for(int radius = 1; radius < n; radius++) { if(i + radius > n || i + 2 * radius > n) continue; string temp; temp.push_back(s[i]); temp.push_back(s[i + radius]); temp.push_back(s[i + 2 * radius]); int tempr = 0; int tempg = 0; int tempb = 0; for(auto e : temp) { if(e == 'R') tempr++; if(e == 'G') tempg++; if(e == 'B') tempb++; } if(tempr == 1 && tempg == 1 && tempb == 1) result--; } } cout << result << endl; }
E - Sum of gcd of Tuples (Hard)
解けなかった。
一歩目の考察はあっていたが、数え上げるフェーズで間違えた。
1~Kまでの数で長さNの数列を作るため、可能な組み合わせはKNとなり、全部試すのは不可能。
そこで、1~Kまでの数の中からある1つの数を選んで、何かできることはないか考えてみる。
すると、選んだ数をgcdにするような数列を数えることを思いつく。
そのような数列は、選んだ数をiとすると、すべての要素がiの倍数となっている数列となるので、k / iのN乗個存在する。
ここで注意しなければいけないのは、このような数え上げを行うと、gcdがiの倍数となるような数列が入り込んでしまう点。
この問題を解決するためにサイズKの配列memoを利用する。
具体的には、memoのi番目の要素にはiをgcdとするような数列の数を記憶する。
これを用いて数え上げをKから行うことで、k / iのN乗からiの倍数がgcdとなるような数列を取り除いていくことができる。
計算量としては、これは調和級数となるためO(k log k)となる。
べき乗の部分も高速べき乗法を用いることでO(log n)で済む。
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; ll mod = 1e9 + 7; ll mypow(ll a, ll n){ ll x = 1; while(n > 0) { if(n & 1ll) { x = (x * a) % mod; } a = (a * a) % mod; n >>= 1; } return x; } int main() { ll n, k; cin >> n >> k; vl memo(k + 1, 0); ll result = 0; for(ll i = k; i > 0; i--) { ll cand = k / i; memo[i] = mypow(cand, n); for(ll j = i + i; j <= k; j += i) memo[i] = (memo[i] - memo[j] + mod) % mod; ll temp = (memo[i] * i) % mod; result = (result + temp) % mod; } cout << result << endl; }
ABC161自分なりのまとめ
ABC161自分なりのまとめ
ABC161に出題された問題について、自分なりの理解をまとめます。
A-ABC Swap
x, y, zを受け取り、z, x, yの順番で出力すれば良い。
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; int main() { int x, y, z; cin >> x >> y >> z; cout << z << " " << x << " " << y << " " << endl; }
B-Popular Vote
商品がN個あり、各商品iはAi表を得ている。
この中から人気商品をM個選ぶ。(人気商品は得票数が1/4M以上)
Aiの総和を取った総得票数をTとしたとき、Ai * 4M >= Tを満たす商品をM個選べるか試せば良い。
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; int main() { int n, m; cin >> n >> m; v a(n, 0); int total = 0; rep(i, n) { cin >> a[i]; total += a[i]; } int cnt = 0; rep(i, n) { if(a[i] * 4 * m >= total) cnt++; } if(cnt >= m) { cout << "Yes" << endl; }else { cout << "No" << endl; } }
C-Replacing Integer
twitterで話題になってたのかな?
個人的にはいつものC問題という感じがした。
xをxとkの差の絶対値で置き換えるため、xがkよりも大きい間は単調減少する。
xがkよりも小さくなると、その一つ手前の値と振動するようになる。
よって、kよりも大きい最小のxとkよりも小さいxとを比べて小さくなる方を出力すれば良い。
最初に与えられる整数をx_0として、x_i = x_(i-1) - kという漸化式をたてる。
すると、x_i = x_0 - ikという式が得られる。
この式からx_iがkより大きい最小のiを求めて、i + 1とiの場合で整数が小さいものを答えとする。
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; int main() { ll n, k; cin >> n >> k; ll i = -1 + (n + (k - 1)) / k; ll c1 = (n - i * k); ll c2 = abs(n - (i + 1) * k); cout << (c1 < c2 ? c1 : c2) << endl; }
D-Lunlun Number
解けなかった。悔しい。
この問題で重要だと思うのは
- ある整数xが与えられたら、xより1桁大きいLunlun Numberを作ることができる
- 数の大小は辞書順であるため、xとyから作ったLunlun Numberはxとyの順序関係を維持する
の2つだと思う。
上記より、最初に1~9までをキューに入れておき
- 取り出した値numのmod 10をlastとする(最後の桁)
- 取り出した値numが10で割り切れなかったら、num * 10 + last - 1をキューに入れる
- num * 10 + lastをキューに入れる
- lastが9で無かったら、num * 10 + last + 1をキューに入れる
この手順を繰り返し、k回目に取り出した値が答えとなる。 うーん、シンプルですね。
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <string> #include <math.h> #include <stack> #define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define repr(i, n) for(int i = n - 1; i >= 0; i--) using namespace std; using ll = long long int; using p = pair<int, int>; using pl = pair<ll, ll>; using v = vector<int>; using vd = vector<double>; using vs = vector<string>; using vl = vector<ll>; int main() { int k; cin >> k; queue<ll> q; for(int i = 1; i < 10; i++) { q.push(i); } for(int i = 0; i < k; i++) { ll num = q.front(); q.pop(); if(i == k - 1) { cout << num << endl; break; } ll last = num % 10; if(last != 0) q.push(num * 10 + last - 1); q.push(num * 10 + last); if(last != 9) q.push(num * 10 + last + 1); } }
第5回ドワンゴからの挑戦状 予選
第5回ドワンゴからの挑戦状の予選に出場しました。 本番は残念ながら1完に終わりましたが2問目まで解いたので自分なりの考察を書きます。
A - Thumbnail
入力としてN個の整数が渡されます。
その平均値をN_Aとした時、N_Aとの差が最も小さい整数の番号を出力します。(差が等しいものがある時は番号が最も小さいもの)
この問題は普通に平均値を計算し差を愚直に計算すればよいです。
B - Sum AND Subarrays
入力として長さがNの整数列が渡されます。
N(N + 1)/2個の連続した部分列に対して、部分列の和が美しさとして定義されます。
N(N + 1)/2個の連続した部分列からK個を選び、それらの論理積を取った時の最大値を出力します。
この問題本番では解けませんでした。。。
ここからは解説を聞いた上で自分なりのまとめを書きます。
まず、部分列の個数はO(N2)であるため列挙が可能です。
列挙したものから論理積の最大値を求めるのですが、ここで求められている演算が論理積であることに注目します。
各部分列を2進数として考えます。
2つの2進数の比較は辞書順比較で行うことができます。
よって、求める最大値は辞書順で最大の値ということになります。
辞書順の最大値は貪欲法で求めることができます。
具体的には、bit列の先頭からこのbitを1にすることができるか試していきます。
これは、可能か判定したいbit列をAとしたとき、部分列iの美しさBiに対して(A & Bi) == Aiが成り立つか調べ、成り立つ部分列の数をカウントしそれがK以上であれば可能、K未満であれば不可能とすることで可能です。
求める値は辞書順の最大値であるため、一度1になったbitは最大値でも必ず1になります。
よって、m桁のbit列があるとき、最初はA=100....0からスタートしi桁目が1になるならばそこを1に固定しAを更新しながら1桁目まで処理を行うことで最大値を求めることができます。
今回の問題ではm=40で大丈夫です。
DjangoのForm生成に値を初期化する方法
DjangoのForm生成時に値を初期化する方法
DjangoのFormを使うときに,あらかじめ各入力欄にデータを入れておきたいことが.Webアプリ開発中にありました.
固定の値であれば,デフォルト値として設定すればよいのですが,今回はデータベース上にある,あるレコードの値を格納したいためこの方法は使えません.
この場合,Formの生成時にinitialを指定します.
例えば,LeagueFormというフォームにLeagueオブジェクトの各データを格納したいときには以下のようにします.
league_form = LeagueFrom(initial={ 'league_name' : current_league.league_name, 'match_style': current_league.match_style, 'rule_set': current_league.rule_set, 'red_count': current_league.red_count, 'start_point': current_league.start_point, 'calculate_point': current_league.calculate_point, 'uma4_1': current_league.uma4_1, 'uma3_2': current_league.uma3_2 })
私は,麻雀リーグの成績管理を自動で行うWebアプリMJMを開発しています
麻雀サークルや麻雀部でのリーグ運営をより簡単におこなるようになります.ぜひご利用ください!
Google ChartsのMaterialでは凡例の位置をbottomにできない
Google Charts
Google Chartsは,Googleが提供しているグラフ描画APIです.これによってwebサイトにグラフを簡単に設置することができます.
このGoogle Chartsにはグラフのタイプがclassicとmaterialの二種類が提供されています.
公式サイトから確認できますが,classicとmaterialだとやっぱりmaterialのほうがかっこいいです.
しかし,classicでは凡例の位置をオプションで制御できたのに対してmaterialでは制御できません.
私はLine Chartのみしか使っていないので,他のグラフで制御できるのかはわかりませんが,少なくともLine Chartでは制御できません.