ダイパキッズでもよくわかるDP(動的計画法)
動的計画法とは
動的計画法は前の状態から次の状態を計算することで計算量を落とすアルゴリズムです。
ダイパリメイクの命名では動的計画法が使用されており、ダイアモンドにブリリアンを、パールにシャイニングを追加することで次のリメイクの名前を決定している事がわかります。
よって次のコードが書けます。
N = 101 dp = [['', ''] for _ in range(N)] dp[0] = ["ダイアモンド", "パール"] for i in range(N - 1): dp[i + 1][0] = "ブリリアント" + dp[i][0] dp[i + 1][1] = "シャイニング" + dp[i][1] print("ダイアモンドの100回目のリメイクの名前は", dp[-1][0]) print("パールの100回目のリメイクの名前は", dp[-1][1])
実行結果は次のようになり100回目のリメイクの名前がわかります。
ダイアモンドの100回目のリメイクの名前は ブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントダイアモンド パールの100回目のリメイクの名前は シャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングパール ||<
B - Taking the middle
この記事は解説記事というより類題を解けるように問題の本質を自分用にメモしたものなのであまり参考にならないかも...
続きを読む473時間で簡単! 青色コーダーの作り方(簡単とは言っていない)
今回は水色コーダーを使った青色コーダーの作り方を紹介します。 もしご家庭に水色コーダーがない場合は以下のサイトが参考になると思います。
材料
- 低級水色コーダー (1200程度でよい)
- 473時間
- 223問
- 91コンテスト(バチャ含む)
記録を取り始めた段階でのレートは1333です。
更に詳しい情報は僕のtwitter(@kumakumaaaaa__)に乗っているのでぜひ。精進木は固定ツイートに生えてるしているので比較的見つけやすいと思います。
手順
1.基礎を固める
まず先程紹介したの記事(中級)と合わせて、上級編も読んでください。
自分は
- 中級・上級の問150問
- JOIの難易度6〜7
- 上級編で紹介されていたtopcoderの50問
この３つを重点的にやることで基礎を固めました。
2.問題演
1.で固めた基礎を実践で使えるように問題演習を行います。問題演習では水・青diffの問題を埋めたり、コンテストに参加してください。
コツ・ポイント
手順1.基礎を固めるのコツ
- 解説AC多めで良いが、しっかり理解するまで時間をかける
- 解けなかった問題の解き直しを時間をおいてする(自力で解けるようになるまで)
手順2.問題演習のコツ
- 解説AC少なめにする、もし自力で解けないなら問題の難易度を下げたほうが良いかも。
- 本番を想定して時間・WAに注意する
参考にさせていただいたサイト
【10分で簡単】夏バテ防止ピリ辛うどん♡ by kanami_♡ 【クックパッド】 簡単おいしいみんなのレシピが336万品
量子コンピューターに入門した話
はじめに
いま非常にホットな量子コンピューターについ先日入門したので、個人的な入門の流れや学習の役に立ったサイトなどを紹介しようと思います。構成としてはIBM Quantum Challenge2020を主体に紹介していこうと思います。この記事で紹介されているサイトなどを参考にすればおそらくIBM Quantum Challenge2020の演習問題を全て解く事ができると思います。
ちなみにIBM Quantum Challenge2020での順位は93位(1177人中)という微妙な順位だったので、こうやって入門した人がいるんだ程度に読んでもらえると幸いです。
※以降この記事ではIBM Quantum Challenge2020のことをIBM Quantum Challengeと呼びます
1. IBM Quantum Challengeとは
github.com
IBM Quantum Challenge」とは、毎年IBMが主催する、量子コンピューターの競技型オンライン・プログラミング・コンテストで、初心者から経験者までがコンテスト形式のチャレンジに参加することで、量子コンピューティングに関する基礎から応用まで学べるコンテストとなっています。また教材・演習問題などが日本語に対応しており、英語が苦手な方でも気軽に参加できるようになっています。
またコンテスト開催期間でなくても教材にアクセスできるので是非チェックしてください。
2.量子コンピューターの理論
IBM Quantum Challengeは演習問題としてはいいのですが、入門者がいきなり読むと教材が簡潔すぎて理解できないと思います。そのため以下のサイトで量子コンピューターの概要を把握しながらIBM Quantum Challengeの演習問題を進めていくのがいいと思います。
enakai00.hatenablog.com
3.グローバーのアルゴリズム
IBM Quantum Challengeに登場した鬼門、N個の物の中から探してる物をO(√N)で見つけれるアルゴリズム。
詳細はこの記事が非常にわかりやすかった。
qiita.com
今後
IBM Quantum Challengeは一年間隔で開かれているため、もっと多く量子コンピューターのハッカソンをやりたいという方は以下のサイトで１ヶ月おきにハッカソンが開かれるらしいので是非参加してみてください。
github.com
2008年 日本情報オリンピック春合宿OJ Cheating: カンニング対策
問題概要
M人の受験者をN個の機械で監視するとき、機械がが監視しないといけない最大範囲を最小にしたときの値をもとめよ。
また監視はx,y両方の方向から行う。
制約
2 <= n <= 200,000
1 <= m <= 100,000
0 <= x,y <= 1,000,000,000
考えたこと
- x方向,y方向それぞれ独立に考えることができる
- 最大範囲を二分探索で求めれそう
受験者が存在するx座標、y座標をソートしてX,Yに格納しておく。
最大範囲をmとするとき、あるi,j (i < j)に関してX[j] - X[i] <= mなら x座標がX[i]以上X[j]以下の受験者はひとつの機械で監視できる。同様のことがy方向に対しても言えるため、最大範囲を決めたとき貪欲的に必要な機械の数がわかる。
よって以下の方法でこの問題が解ける。
- mを決める
- 必要な機械数を求める
- 必要な機械数がN以下ならmよりも小さい最大範囲で観測ができるか試す。Nより大きいなら最大範囲を大きくして試す。(二分探索)
- mが定まるまで1〜3を繰り返す
#include <bits/stdc++.h> #define INF 2000000000000000000 #define ll long long using namespace std; int main() { ll N, M; cin >> N >> M; vector<ll> X, Y; for (ll i = 0; i < M; ++i) { ll x, y; cin >> x >> y; X.push_back(x); Y.push_back(y); } sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end());//かぶってるx座標を1つにしている 例{1, 1, 1, 2, 3, 3} ⇒ {1, 2, 3} sort(Y.begin(), Y.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end()); ll l = -1, r = pow(10, 9);//二分探索の範囲を設定 while (l + 1 != r) { //1.mを決める ll m = (l + r) / 2; //2.機械の数を数える ll cnt = 2;//機械の数 x,y方向に必ず1ずつは使うためcnt = 2始まり ll before = X.at(0);//beforeの位置に機械をおく for (ll i = 0; i < X.size(); ++i) { //一つ前の機械からの距離がmより大きいときは新しく機械を設置する if (X.at(i) - before > m) { cnt += 1; before = X.at(i); } } before = Y.at(0); for (ll i = 0; i < Y.size(); ++i) { if (Y.at(i) - before > m) { cnt += 1; before = Y.at(i); } } //3.機械の数によって探索する範囲を変更する if (cnt <= N) { r = m; } else { l = m; } } cout << r << "\n"; }
AOJ - Union of Rectangles
問題へのリンク
問題文
平面上に N個の長方形があります。 各長方形の辺は、x 軸または y 軸に平行で、
i個目の長方形の左上の座標は(x1i,y1i), 右下の座標は (x2i,y2i) です。
１つ以上の長方形で覆われている部分の面積を求めてください。
注意: 左上の座標は (x1i,y1i), 右下の座標は (x2i,y2i)となっていますが、
入力例を見る限り (x1i,y1i)は左下、(x2i,y2i)は右上の点だと思います。
制約
1≤N≤2000
10^9≤x1i＜x2i≤10^9
10^9≤y1i＜y2i≤10^9
解法
1.二次元座標圧縮をする
（座標圧縮がわからない方はこちら)
長方形の辺があるx,y座標のみを残すように圧縮する。このとき圧縮する前の辺があったx,yの座標を配列X, Yにそれぞれ保存しておく。(X, Yはsortしておく)
例
X = {0, 1, 3, 4}, Y = {0, 2, 3, 4}
(X = {AD, EH, BC, FG}, Y = {AB, EF, HG, DC})
2.面積を求める
長方形に囲まれているかの判定をイモス法を使ってします。(イモス法がわからない方はこちら)
長方形の下辺の上のマスを+1、上辺の上のマスを-1にし、下から和を取っていったとき、マスの値が1以上のマスは長方形の内部に含まれます。
よってマスの値が1以上のマスの面積の合計が答えになります。
また圧縮後の左下の点の座標が(i,j)、右上の点が(i+1, j+1)のマスの面積は(Y[j + 1] - Y[j]) * (X[i + 1] - X[i])で求めることができます。
実装
ソースコードはこちらのコードを参考にさせていただきました。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n; int ax[5000],ay[5000]; int bx[5000],by[5000]; vector< ll > X,Y; vector< int > lower_edge[5000]; vector< int > upper_edge[5000]; int imos[5000]; int main(){ //入力 cin>>n; for(int i=0;i<n;i++){ cin>>ax[i]>>ay[i]>>bx[i]>>by[i]; X.push_back(ax[i]); Y.push_back(ay[i]); X.push_back(bx[i]); Y.push_back(by[i]); } //座標圧縮の前準備(詳細は関連リンク1をご覧ください) sort(X.begin(),X.end()); sort(Y.begin(),Y.end()); X.erase( unique( X.begin(), X.end()) , X.end() ); Y.erase( unique( Y.begin(), Y.end()) , Y.end() ); for(int i=0;i<n;i++){ //座標圧縮 ax[i]=lower_bound(X.begin(),X.end(),ax[i])-X.begin(); ay[i]=lower_bound(Y.begin(),Y.end(),ay[i])-Y.begin(); bx[i]=lower_bound(X.begin(),X.end(),bx[i])-X.begin(); by[i]=lower_bound(Y.begin(),Y.end(),by[i])-Y.begin(); //lower_edge[yi]には 直線y=yi上にある下辺のx座標をpush_backしている(upper_edgeは上辺) //axは辺の左側の点、bxは辺の右側の点 lower_edge[ ay[i] ].push_back( ax[i] ); lower_edge[ ay[i] ].push_back( bx[i] ); upper_edge[ by[i] ].push_back( ax[i] ); upper_edge[ by[i] ].push_back( bx[i] ); } ll ans=0; for(int y=0;y+1<(int)Y.size();y++){ //imosの更新 for(int i=0;i<(int)upper_edge[y].size();i+=2){ //upper_edgeの偶数番目には辺の左側、奇数には辺の右側の点が入っている //lower_edgeもupper_edgeと同様 int left=upper_edge[y][i]; int right=upper_edge[y][i+1]; for(int x=left;x<right;x++)imos[x]++; } for(int i=0;i<(int)lower_edge[y].size();i+=2){ int left=lower_edge[y][i]; int right=lower_edge[y][i+1]; for(int x=left;x<right;x++)imos[x]--; } //答えの更新 for(int x=0;x+1<(int)X.size();x++){ //imosが0じゃないならそのマスは長方形内に含まれる if(imos[x]==0)continue; ans+=(Y[y+1]-Y[y])*(X[x+1]-X[x]); } } cout<<ans<<endl; return 0; }
関連リンク
1.https://scrapbox.io/pocala-kyopro/%E5%BA%A7%E6%A8%99%E5%9C%A7%E7%B8%AE
