競技プログラミング

[PR]

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

完全なる備忘録
下記について、オヌヌメのサイトなどあればコメントで教えてください。

・重複の除去
https://qiita.com/ysk24ok/items/30ae72f4f1060b088588

・std::set（上とも関連）
http://vivi.dyndns.org/tech/cpp/set.html

・Union-Find木
https://qiita.com/ofutonfuton/items/c17dfd33fc542c222396

・

[0回]

ABC001-010まとめ

AtCoderBeginnerContestの各問題におけるミソを自分用にまとめた記事。
その001-010。
リンク先はそのミソについてまとめられた（まとめた）記事になっています。

ABC001

A問題　なし

B問題　なし

C問題
小数の計算誤差。
http://kikihijidarake.blog.shinobi.jp/nocategory/avoidcalcerror
一般には私がまとめたのより、こちらのサイトの方が詳しいし良いかも。http://d.hatena.ne.jp/komiyam/20111210/1323503019

D問題

ABC002

A問題　なし

B問題　なし

C問題
小数の計算誤差。
同上

D問題

ABC003

A問題
計算順序とかもっといい方法があった。
詳細はいずれ。（書かないかも）

B問題
別解：文字に点数をつけて、その合計点を見ることで条件を満たすか否かを判別する方法。
文字と点数の結びつけは連想配列で。C++ならstd::mapとか。
→連想配列の詳細 http://vivi.dyndns.org/tech/cpp/map.html
詳細はいずれ。（書かないかも）

C問題
組み合わせが膨大な問題に対してどう取り組むか。
詳細はいずれ。（書かないかも）

D問題

ABC004

A問題　なし

B問題
マスをどうやって回転させるか。
→c[i][j]とc[3-i][3-j]をswapすればよい。

C問題
膨大な計算をどう削減するか。
→今回は繰り返し（規則性）の発見。
→やっている計算も同じようなことを繰り返しているだけだしね。
詳細はなし。

D問題

ABC005

A問題　なし

B問題　ソートするか入力段階でmin値を更新していくか。

C問題　別解の二部グラフってなに。調べたら追記。

D問題

ABC006

A問題　なし

B問題　なし

C問題　1変数の固定とか、3変数のうち既に求めた2変数を用いて残りの1変数を導出するとか。

D問題

ABC007

A問題　なし

B問題　なし

C問題　幅優先探索の例題

D問題

ABC008

A問題　なし

B問題　なし

C問題

D問題

ABC009

A問題　なし

B問題　降順ソートのやり方
http://kikihijidarake.blog.shinobi.jp/Entry/8/

C問題

D問題

ABC010

A問題　なし

B問題　なし

C問題
小数の計算誤差。
ABC001 C問題と同じ

D問題

[0回]

小数計算の誤差を回避する

ききひじの競プロ備忘録

割り算の結果が小数になる場合、その誤差が時に問題を生じさせる。
特に比較をするときなどは顕著だろう。
その解決策である。

因みに私は記事を書いてなおよくわかっていない。

回避策1：少しだけ小さい数を足す

割られる数が整数などの場合、計算結果に、例えば0.00001のような小さめの値を足すという方法がある。

double ans = 241 / 60 + 0.00001;

「少しだけ」が曖昧なので、妥当な数字がどれくらいかを考えるのは難しい気がする。
また割られる数が小数以下の細かい数字の場合、この方法をとることが出来ない。

回避策2：10のn乗倍してから、整数として計算する。

整数xを整数yで割る。このとき、商を10^-nの精度で求めたいとする。
解決策2では、xを先に10^n倍してyで割るのだ。そして計算結果を10^-n倍すればよい。

もし計算結果をそのまま出力するとか、文字にするのならば10^-n倍しないことも可能だろう。こうすると完全にずれはなくなる…気がする。

// n = 1, y=2 のとき
const int a = 何かしらの値1
const int b = 何かしらの値2

cin>>x;
x = x * 10 / 2;
cout<< x / 10 << '.' << x % 10 << flush;

また、計算が続くのならば、すべての計算が終わった段階で10^-n倍するとよいかもしれない。この方法で注意すべきは、変数のオーバーフローである。特に計算が長く続き、かつ最後に10^-n倍をする場合、その計算途中で桁が溢れる危険があるので使う際には留意されたし。

回避策3：そもそも計算しない

そもそも小数を扱わなければいけないような計算をしなければいい。

例えば、入力xについて、xを７で割った商で条件分岐する場合を考える。
このとき、境目となる値を先に7倍し、7倍された値とxを比較すればよいのだ。

before

// a > b
const double a = 何かしらの値1
const double b = 何かしらの値2

cin>>x;
double quotient = x/7;
if(quotient > a){
  //何かしらの処理
}
else if(quotient > b){
  //何かしらの処理
}
else{
  //何かしらの処理
}

after AやBは可能なら先に自分で計算をしておくとよりよい（のだろうか）。

// a > b
const double A = 何かしらの値1*7
const double B = 何かしらの値2*7

cin>>x;
if(x > A){
  //何かしらの処理
}
else if(x > B){
  //何かしらの処理
}
else{
  //何かしらの処理
}

[0回]

ソートと降順（逆順）ソート　 C++

ききひじの競プロ備忘録

・ソート

必要なヘッダファイルは<algorithm>
以下の方法で、データを昇順（小→大）にすることができる。
処理としてはクイックソートを行っているはず。
例えばvectorをソートするならば、

#include <algorithm>
#include <iostream>

int main() {
  vector<int> A(5);
  for (int i = 0; i < 5; ++i) {
    cin>>A[i];
  }

  //肝心のソート部
  sort(A.begin(), A.end());
  for (int i = 0; i < 5; ++i) {
    cout<<A[i]<<" ";
  }
  cout<<endl;
}

例えば上記のコードで
　　7 3 4 1 9
と入力すれば、
　　1 3 4 7 9
と結果が出力される。

・降順ソート

先のソートでは昇順でソートされた。
これを降順（大→小）でソートするにはどうすればいいか。
ヘッダファイルは上記の<algorithm>に加えて<functional>も必要となる。

#include <algorithm>
#include <functional>  //これが必要
#include <iostream>

int main() {
  vector<int> A(5);
  for (int i = 0; i < 5; ++i) {
    cin>>A[i];
  }

  //肝心のソート部
  sort(A.begin(), A.end(), greater<int>());



for (int i = 0; i < 5; ++i) {
    cout<<A[i]<<" ";
  }
  cout<<endl;
}

例えば上記のコードで
　　7 3 4 1 9
と入力すれば、
　　9 7 4 3 1
と結果が出力される。

降順ソート別解

以下の方法でも逆順ソートは達成できる。
またこの場合は<functional>は不要となる。
ただ、実行速度はこちらの方が劣るとか。

#include <algorithm>
#include <iostream>

int main() {
  vector<int> A(5);
  for (int i = 0; i < 5; ++i) {
    cin>>A[i];
  }

  //肝心のソート部
  sort(A.rbegin(), A.rend());



  for (int i = 0; i < 5; ++i) {
    cout<<A[i]<<" ";
  }
  cout<<endl;
}

・因みに…

std::sort()
std::greater<Type>()
とstdです。

[5回]