ABC015 D - 高橋くんの苦悩|AtCoder
D - 高橋くんの苦悩 を解きました。
題意
この問題は良くある knapsack 問題に置き換えて考えられる為、本当の題意は省略します。
与えられる変数と値は以下のように置き換えて考えます。
- … knapsack の容量
- … 与えられる荷物の数
- … knapsack に詰めれる荷物の個数
- … 各荷物の重さ
- … 各荷物の価値
- 個の荷物とその荷物の重さ と荷物の価値 が与えられる。
- knapsack の容量 と knapsack に入る荷物の個数 が与えられるので、これらを超えないように荷物を選んだ時の価値の最大値を出力する。
考察
全探索で考えると、 個の中から 個選んで knapsack に荷物を入れる・入れないを全て試すと 時間のアルゴリズムになります。制約を見てみると なので全探索ではとても間に合わない為、DPで考えていきます。
まず、問題を読むと今まで解いてきた易しい、かつ、典型的な knapsack と 1 点違う箇所がありました。
それは、knapsack の容量制限に加えて、荷物の個数制限がある点です。
荷物の個数を管理する引数が増えるだけなので、loop DP で書く場合は 3 次元 DP で解けば良さそうでした。
DPテーブルの定義
番目以下の荷物から 個以下選び、重さ が を超えないように荷物を選んだ時の価値の最大値
漸化式の定義
計算量
DP 部分は、std::max での比較に 時間かかり、それを 3 重 loop で N・K・W 回繰り返すので、 時間。プログラム全体では 時間となります。
Max値取得|動的計画法( DP )
動的計画法 ( DP )の学習として解きました。
例題のねらい:動的計画法におけるメモ配列とDPテーブルの違いを確認する。
問題: 要素の int 型配列 が与えられる. の最大値を DP で求めよ
問題制約は特になかったので、適当に。( くらい?)
1. メモ化再帰編
正当性の証明
計算量
main 関数は std::vector::resize に 、再帰関数の呼び出しに 時間。
rec 関数は、訪問済判定の if 文、訪問済だった場合、memo した値を返すのにそれぞれ 時間。
基底ケース部分は、 if 文、res を返すのにそれぞれ 時間。再帰ケース部分は std::max *1 を使って大小比較 1 回につき 時間かかり、それを再帰関数 で 回繰り返すので 時間。プログラム全体では 時間。
コード
vector<int> memo( 100000 + 1, -1 ); int N, res; vector<int> A; int rec( int i ) { int &res = memo[ i ]; if( res != -1 ) { return res; } //基底ケース if( i == 1 ) { return res = A[ 0 ]; } //再帰ケース return res = max( rec( i - 1 ), A[ i - 1 ] ); } int main() { cin >> N; A.resize( N ); for( auto &x : A ) { cin >> x; } cout << rec( N ) << endl; return 0; }
実行コード:[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ
2. Loop DP 編
次にメモ化再帰編を元に Loop DP 版を書きました。
計算量
DP 部分は std::max を使っての大小比較 1 回につき 時間を loop で 回繰り返すので、 時間。
プログラム全体では 時間となる。
int main() { int N; cin >> N; vector<int> A( N ); for( auto &x : A ) { cin >> x; } vector<int> dp( 100000 + 1 ); dp[ 1 ] = A[ 0 ]; for( int i = 2; i <= N; i++ ) { dp[ i ] = max( dp[ i - 1 ], A[ i - 1 ] ); } cout << dp[ N ] << endl; return 0; }
実行コード:[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ
3. 学習まとめ
メモ化再帰も loop DP も計算結果を保存して次の計算に使うという本質的な所は同じで、単に実装方法が異なるだけということが例題から良く判りました(おわり)
2017年 進捗大反省会
昨年同様、今年1年の振り返り記事を残します。
独り反省会なので反省をポジティブにしていきます。
C++ について
C++を勉強しだして2年が経ちました。
まだまだ知識が浅く、基礎的な事も解らなかったり、知識が定着していなかったりするので、
猫C++ をもう一度軽くやり直したりしていました。
全体としては、今年は言語自体の勉強はあまり深くしなかったです。
学習方法として変わってきた事としては、学習 1 年目の頃は誰かが噛み砕いて書いているような Blog とかを好んで見ていたのですが、最近では解らない事があると C++ reference や C++ ポケットリファレンス(本)を良く見るようになりました。
少しは C++ に慣れてきた...(?)
競プロについて
アルゴリズム
今年はアルゴリズムの勉強を主にしていました。
初めはTLE本で問題を解きながら進めていたのですが、いつの間にか離脱...。
本に沿って勉強していると、解らないまま進んでしまえるので良くない気がして、途中から本で勉強を進めるのはやめました。*1
TLE本, 蟻本やチーター本は自分には難しく、全然勉強が進まなくなりました。
それからは、アルゴリズム理論の本を読んだり、自分に最適化された(易しい)資料を読む事で少しずつまた勉強を進める事ができました。
↑画像の本2冊は知識が何もない自分にも解りやすかった2冊で、学習の助けとなりました。
何事も一つひとつ自分の中で納得しないと進めない面倒なタイプなので*2、実装前に「動的計画法とは」みたいな勉強から始める方が自分には合っている気がしました。
本に沿って勉強するのをやめたので、主に yukicoder の問題を使って学習していました。
(同じ問題を何度も何度も解き直しをしていたので、yukicoder管理人のyukiさんには不審に思われていたかも知れない...。)
DFSも書けるようになってきたので、最近はずーーっとDP(knapsack, 数え上げ)の勉強を主にしています。
AC数
今年は考察ばかりに時間を割いていたので、AC数は少なく終わりました。
主に解いていた AtCoder と yukicoder 合わせて 140 くらいでしょうか...。
でも来年はもっと少ない予感しかない。
コンテスト
今年はコンテストもあまり参加しなくなってしまった。
理由は色々あったのですが、解決済みなので来年はもう少し参加したいですね。
あと運良く ABC で初めて全完出来たんですよ。
わーい!初めてABCで全完できたー!
— cww (@chiwawa_star) 2017年9月2日
しかしこれは罠でこの後プロからこのケースで D 落ちますみたいな指摘を受け凹む(現実は厳しい)(でもそういう指摘はうれしい)
来年も地道に ABC 頑張りたいな(希望)
LaTeXについて
今年は と出会いました。
始まりは Blog の数式部分が読みづらいよというご指摘を頂いたことでした。
指摘されるまで全然意識していなかったのですが、確かに他の人の Blog を見るとちゃんと数式部分は LaTeX で書かれていました。
別に強く勧められた訳ではなく、なんとなく MacTeX を DL して使ってみたら凄く直感的で感動しました。マークアップで文書作成出来るって凄い...!楽しい!!みたいな感想しかなかった。
自分は Adobe 生まれ Adobe 育ちなので、これまで文書作成は Illustrator だったのですが(レポート類も)、こんなに便利なものが世の中にあるのか...みたいな衝撃でした。
は最高。
2018年の課題
- アルゴリズムの勉強
2018年はもうこれしかないと思っていて、逆に他の事する時間もなさそう。
全振りしてしまっていいかは謎ですが...。
アルゴリズムの勉強法はまだ自分の中でしっくり来ていなくて、どう勉強を進めたら良いのかも模索中なのですが、自分の場合、習得を急いでいる訳ではないので楽しく勉強したいなと思っています。
とにかく動的計画法をマスターしないと!
本を良く読み理解して勉強する!解らない事は解るまで調べる!
- 考察する
DP の問題もそうなんですが、典型的な問題が解けてもちょっと応用っぽくなると解けなかったりするので、深く考察するようにしたいです。
- Effective に C++ を書く
C++ もまだまだ初心者以下なのでちゃんと勉強する。(Effective C++ と Effective STL を買った)
効率的なコードを書けるようになりたいです。
- 解いた問題の記事を書く
復習という意味で、簡単な問題でも出来ればしっかり書きたいです。
今年は結構書いたんですが、殆どが下書き状態で終わったので...。
Blog を書きながら考察してたりして、実装に入ってしまうと放置になってしまうの良くないので最後まで書きたいですね。
記事を書くと「計算量違うよ!」とか「もっと良い方法あるよ!」等、わりとお声がけいただけるので、本当に有り難いです。(お気付きの点があれば@ください!)
まとめ
1年間何してたんだろう...(成長なし)
来年は DP を頑張る!それだけ!
余談
実は夏頃に転職しました。
少しだけキャリアチェンジもしました。(チェンジと言う程でもないけれど)
新しい職場の開発環境(git)にもやっと慣れて...もいないのですが、炎上案件に放り込まれ、毎日楽しいです(真顔)
二分法( 二分探索 )で平方根を求める
二分探索の練習をしました。
追記:二分探索と書いたけれど、正しくは二分法 *1 かも知れない...。
追記②:正しくは二分法だった...
整数 および 実数 が与えられるので となるような を絶対 or 相対誤差が となる精度で求めてください。
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int main() { int N; cin >> N; for( int i = 0; i < N; i++ ) { double x; cin >> x; double left{}, right{ x }, mid{}; if( x < 1 ) right = 1; while( right - left > 0.00001 ) { mid = ( left + right ) / 2.0; if( mid * mid > x ) { right = mid; } else { left = mid; } } cout << fixed << setprecision( 8 ) << mid << " " << sqrt( x ) << endl; } return 0; }
INPUT
5 2 4 0.5 0.1 10
OUTPUT
1.41420746 1.41421356 2.00000763 2.00000000 0.70709991 0.70710678 0.31623077 0.31622777 3.16227913 3.16227766
- が 以下の場合の処理を忘れない。
- while の loop 回数を 増やすと精度が上がって std::sqrt() *2 の結果に近くなる。
参考になる記事
satanic0258.hatenablog.com
std::tuple の使い方|C++
std::tuple の使い方を覚えたのでメモします。
std::tuple とは?
std::pair が 2 つの型の値を保持出来るのに対し、std::tuple は N 個の型の値を保持する事ができる。*1
宣言・要素格納:
//宣言 vector<tuple<int, string, bool>> vc; for( int i = 0; i < 3; ++i ) { string a; bool b; cin >> a >> b; //要素構築 vc.emplace_back( i, a, b ); }
格納する値が全部 int の場合 vector<tuple<int, int, int>> vc; となる。
値の型が異なる場合は vector<tuple<int, string, bool>> vc; とできる。
要素構築(格納)は std::emplace_back などを使ってできる。
要素の取得
std::tuple::get *2 を使って各要素を取得できる。
for( auto x : vc ) { //位置を指定する場合(I番目の引数) cout << get<0>( x ) << " " << get<1>( x ) << " " << get<2>( x ) << endl; }
⬆ I 番目の引数を指定する事で要素を取得できる。( tuple<0番目, 1番目, 2番目> の順 )
for( auto x : vc ) { //型を指定する場合 cout << get<bool>( x ) << " " << get<string>( x ) << " " << get<int>( x ) << endl; }
⬆引数の代わりに型を入れると、その型の要素が取得できる。
for( int i = 0; i < 3; ++i ) { //添字も使える cout << get<0>( vc[ i ] ) << " " << get<1>( vc[ i ] ) << " " << get<2>( vc[ i ] ) << endl; }
⬆ range-based for でなく普通の for 文 + 添字 で要素の取得もできる。
要素をソート
sort( begin( vc ), end( vc ) );
⬆ sort した場合、tuple の第一要素、第二要素、第三要素の順で比較した結果が返ります。*3
sort( begin( vc ), end( vc ), greater<tuple<int, string, bool>>() );
⬆ 降順 sort は第三引数に greater<tuple<int, string, bool>>() を指定します。
sort( ALL( vc ), []( const auto &x, const auto &y ) { //第一要素が同一ならば第二要素の小さい方を返す return get<0>( x ) == get<0>( y ) ? get<1>( x ) < get<1>( y ) : get<0>( x ) > get<0>( y ); });
std::sort の第三引数にラムダで各要素の比較結果を返せるようにも書けます。