競プロ記録

問題を解いた際に自分の復習用として使ってます

機会学習:メモ

前提インポート

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
import mglearn
from Ipython.display import display

前提コマンド

%matplotlib notebook

k-Nearest Neighbors

  • 新しいデータポイントに対して予測する際に、新しい点に最も近い点を訓練セットから探し、新しい点に最も近かった点のラベルを新しいデータポイントに付与する。
  • kは用いる点の個数が複数でも良いことを意味する。
  • 多数の特徴量を持つデータセットではうまく機能しない。
  • 特徴量の多くが0となる場合には特に相性が悪い
  • 実際の現場では扱える特徴量が少ないためほとんど使われていない。

    訓練と評価のための最小手順

X_train, X_test, y_train, y_test = train_test_split(iris_dataset['data'], iris_dataset['target'], random_state=0)
knn = KNeighborsClassifier(n_neighbors=1)
knn.fit(X_train, y_train)

print("Test set score: {:.2f}".format(knn.score(X_test, y_test)))

Pythonによるデータ分析入門:メモ

内容

ちらほらエラーがでるところがあったので修正した箇所一覧をまとめました。

p28

  • 修正前
users = pd.read_table('pydata-book/datasets/movielens/users.dat', sep='::', header=None, names=unames)
  • 修正後
users = pd.read_table('pydata-book/datasets/movielens/users.dat', sep='::', header=None, names=unames, engine='python')

p30

  • 修正前
mean_ratings = data.pivot_table('rating', rows='title',cols='gender', aggfunc='mean')
  • 修正後
mean_ratings = data.pivot_table('rating', index='title',columns='gender', aggfunc='mean')

p32

  • 修正前
top_female_ratings = mean_ratings.sort_index(by='F', ascending=False)
  • 修正後
top_female_ratings = mean_ratings.sort_values(by='F', ascending=False)

rating_std_by_title = data.groupby('title')['rating'].std() rating_std_by_title = rating_std_by_title.loc[active_titles] rating_std_by_title.sort_values(ascending=False)[:10]

p33

  • 修正前
rating_std_by_title = data.groupby('title')['rating'].std()
rating_std_by_title = rating_std_by_title.ix[active_titles]
rating_std_by_title.order(ascending=False)[:10]
  • 修正後
rating_std_by_title = data.groupby('title')['rating'].std()
rating_std_by_title = rating_std_by_title.loc[active_titles]
rating_std_by_title.sort_values(ascending=False)[:10]

#

  • 修正前
subset = total_births[['John', 'Harry', 'Mary', 'Marilyn']]
subset.plot(subplots=True, figsize=(12, 10), grid=False, title="Number of births per year")
  • 修正後
実行できませんでした。

p112など

  • 修正前
arr = randn(4, 4)
  • 修正後
arr = np.random.randn(4,4)

メモ

axis=0は縦
axis=1は横

メモ

4.4.2 ndarrayの保存:テキスト形式
array_ex.txtがないのでスキップ

p121

  • 修正前
X = np.random.randn(5, 5)
mat = X.T.dot(X)
mat.dot(inv(mat))
  • 修正後
正しい結果にならない。わからない。

p122

%timeit はIPythonの機能
Jupyter notebookでは機能しない

np.random.randint

numpy.random.randint(low, high=None, size=None, dtype='l')

np.cumsum

numpy.cumsum(a, axis=None, dtype=None, out=None)[source]

p134

  • 修正前
frame2.ix['three']
  • 修正後
frame2.loc['three']

p154

  • 修正前
obj.order()
  • 修正後
obj.sort_value()

p155

  • 修正前
frame.sort_index(by = 'b')
  • 修正後
frame.sort_values(by='b')

p155

  • 修正前
frame.sort_index(by = ['a', 'b'])
  • 修正後
frame.sort_values(by = ['a', 'b'])

p160

  • 修正前
import pandas.io.data as web
  • 修正後
sudo pip install pandas-datareader

または

sudo python3 -m pip install pandas_datareader

してから

import pandas_datareader.data as web

price = DataFrame({tic : data['Adj Close'] for tic, data in all_data.items()}) volume = DataFrame({tic: data['Volume'] for tic, data in all_data.items()})

p160

  • 修正前
piece = DataFrame({tic : data['Adj Close']
                  for tic, data in all_data_iteritems()})
volume = DataFrame({tic : data['Volume'] for tic, data in all_data.iteritems()})
  • 修正後
price = DataFrame({tic : data['Adj Close']
                  for tic, data in all_data.items()})
volume = DataFrame({tic: data['Volume']
                             for tic, data in all_data.items()})

p192

  • 修正前
from urllib2 import urlopen
  • 修正後
from urllib.request import urlopen

メモ

  • 開始
p195 6.1.51 lxml.objectify を使ったXMLの読み込み
  • 終了
7章の終わりまで

AGC018 A問題

問題

agc018.contest.atcoder.jp

解説

この問題はユークリッドの互除法を用います。ではなぜユークリッドの互除法と言う考え方が出てくるのか解説します。 まずユークリッドの互除法に関して以下のページを読んでください。

math.nakaken88.com

a(modG)が0, b(modG)が0,ならば a-b(modG)も0になることが理解できたかと思います。すると任意の二つの数に関する最大公約数 が書かれたボールを入れることができるため、それらの最大公約数が書かれたボールに対して再び上記の捜査を繰り返すとすべての数の最大公約数が書かれたボールを入れることができます。その最大公約数をGとし、K-G、 K-2G, K-3G,....2G, Gのボールを入れることができるためKがGで割り切れる時、K=x*GであるKのボールも入れることができます。 したがってKがGで割り切れるかどうかを判定すれば良いです。

コード

include

include

include

using namespace std;

int gcd(int a, int b){ if(a%b == 0){ return b; }else{ return gcd(b,a%b); } } int main(void){ int n, k, a[100005]; cin >> n >> k; for(int i=0;i<n;i++){ cin >> a[i]; if(a[i] == k){ cout << "POSSIBLE" << endl; return 0; } } sort(a,a+n); if(a[n-1] < k){ cout << "IMPOSSIBLE" << endl; return 0; } int G = gcd(a[0], a[1]); for(int i=2; i<n; i++){ G = gcd(a[i], G); } if(k%G == 0){ cout << "POSSIBLE" << endl; }else{ cout << "IMPOSSIBLE" << endl; }

return 0;

}

ABC051 D問題 Candidates of No Shortest Paths

問題

abc051.contest.atcoder.jp

解説

まずNが少ないのでワーシャルフロイドを使いそうだなと考えられ、実際に使用します。
まず頂点間の最小距離を求めておきます。 そしてある辺が最小距離のパスに使われているかどうかは以下の式を満たしているs, tが存在するかで判断します。

dist(s, t) = dist(s, i) + edge(i, j) + dist(j, t)

この式を満たしているs, tを2重ループを使って探索して一つでも存在すれば最短距離のパスの中に使われていることになります。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

struct edge {
    int from, to, cost;
};

typedef pair<int, int> P;
typedef vector<vector<edge> > G;

G graph;
int n, m;

int d[105][105];
bool used[105][105];
vector<edge> dist;

void warshall_floyd(){
    for(int k=0; k<n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(d[i][j] > d[i][k] + d[k][j]){
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

int main(void){
    cin >> n >> m;
    graph = G(n);

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(i == j){
                d[i][j] = 0;
            }else{
                d[i][j] = inf;
            }
        }
    }
    int cnt = 0;
    for(int i=0; i<m; i++){
        int x, y, c;
        cin >> x >> y >> c;
        x--;
        y--;
        d[x][y] = c;
        d[y][x] = c;
        edge e;

        e.from = x;
        e.to = y;
        e.cost = c;
        dist.push_back(e);
        e.from = y;
        e.to = x;
        e.cost = c;
        dist.push_back(e);

    }

    warshall_floyd();
    int ans = 0;
    for(int i=0; i<dist.size(); i++){
        bool flag = false;
        for(int s=0; s<n; s++){
            for(int t=0; t<n; t++){
                if(d[s][dist[i].from] + dist[i].cost + d[dist[i].to][t] == d[s][t]){
                    flag = true;
                }
            }
        }
        if(!(flag)){
            ans++;
        }
    }
    cout << ans/2 << endl;
    return 0;
}

CODE FESTIVAL 2017 qual B C問題 3 Steps

問題

code-festival-2017-qualb.contest.atcoder.jp

解説

辺を3本巡って到達できる頂点と辺を新たに結ぶので、2頂点間に奇数長のパスが存在すれば辺を結ぶことができます。 では奇数長のパスが存在するとはどのような時なのでしょうか。それは2分グラフであるかどうかに影響されます。 * 2分グラフである場合 辺を結ぶことができるのは色が異なる頂点間です。それは同色であると必ずパスの長さが偶数になるからです。 よって黒と白に塗り分けるとすると、黒の頂点数=b, 白の頂点数=wとすると bC1 * wC1 が結ぶことができる辺の数であり、すでに結ばれている辺の数Mを引いた値が答えになります。 * 2分グラフでない場合 必ず奇数長のサイクルが存在するので全ての2頂点間のパスの中に奇数長のパスが存在することになり、任意の2頂点間を辺で結ぶことができるためnC2-mが答えになります。

コード

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
using namespace std;

const long long inf = 1e10;
const long long mod = 1e9+7;

typedef vector<vector<int> > G;
G graph;

int color[100050];

bool dfs(int u, int c){
    color[u] = c;
    for(int i=0; i<graph[u].size(); i++){
        int v = graph[u][i];
        if(color[v] == c){
            return false;
        }
        if(color[v] == 0 && !dfs(v, -c) ){
            return false;
        }
    }   
    return true;
}

int main(void){
    long long n, m;
    cin >> n >> m;
    graph = G(n);
    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    long long B=0, W=0;
    if(dfs(0, 1)){
        for(int i=0; i<n; i++){
            if(color[i] == 1){
                B++;
            }else if(color[i] == -1){
                W++;
            }
        }
        cout << B*W - m << endl;
    }else{
        cout << ( (n*(n-1)) /2) - m << endl;
    }
    
    return 0;
}

ABC075 A~D問題

A問題

A - One out of Three

解説

これは解説省略します。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

int main(void){
    int a, b, c;
    string s;
    cin >> a >> b >> c;
    if(a == b){
        cout << c << endl;
    }else if(b == c){
        cout << a << endl;
    }else if(a == c){
        cout << b << endl;
    }
    return 0;
}


B問題

B - Minesweeper

解説

全ての' . 'に関して8方向に#がいくつあるかをカウントしていけば良いです。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

int main(void){
    int h, w;
    char field[55][55];
    cin >> h >> w;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> field[i][j]; 
        }
    }
    int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
    int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(field[i][j] == '.'){
                int cnt = 0;
                for(int k=0; k<8; k++){
                    int nx = j + dx[k], ny = i + dy[k];
                    if(nx >= 0 && nx < w && ny >= 0 && ny < h && field[ny][nx] == '#'){
                        cnt++;
                    }
                }
                cout << cnt;
            }else{
                cout << "#";
            }
        }
        cout << endl;
    }
    return 0;
}


C問題

C - Bridge

解説

全ての辺に関して、その辺がないものとしてDFSし、全ての頂点を訪れることができるかどうかを調べていきます。
訪れていない頂点があればその辺は橋であり、全ての頂点を訪れることができればその辺は橋ではありません。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

typedef pair<int, int> P;

int n, m;
bool visited[100];
bool AList[100][100];

void dfs(int u){
    visited[u] = true;
    for(int i=0; i<n; i++){
        if(AList[u][i] && !(visited[i]) ){
            dfs(i);
        }
    }
    return;
}

int main(void){
    int ans = 0;

    queue<pair<int, int> > que; 
    cin >> n >> m;

    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        AList[x][y] = true;
        AList[y][x] = true;
        que.push(P(x, y));
    }

    for(int i=0; i<m; i++){

        bool flag = true;
        fill(visited, visited+n, false);

        P p = que.front();
        que.pop();
        AList[p.first][p.second] = false;
        AList[p.second][p.first] = false;

        dfs(0);
        for(int j=0; j<n; j++){
            if(!(visited[j])){
                flag = false;
            }
        }

        if(!(flag) ){
            ans++;
        }

        AList[p.first][p.second] = true;
        AList[p.second][p.first] = true;
    }
    cout << ans << endl;

    return 0;
}


D問題

D - Axis-Parallel Rectangle

解説

ある長方形の区間にいくつ点が含まれているかを数え、それがkを超えている、かつ面積が最小である。この時の最小の面積を出力すれば良いので、長方形の区間をどのようにして決定させるか問題になります。そこで長方形の横の区間を決定付ける値を求めていきます。それは左右の辺には必ず頂点が含まれているため頂点のx座標が左右の端の座標の候補になります。同様にして上下の区間もy座標が候補になるので全て全探索して、その区間に含まれる頂点の個数を数えてあげ面積を保持しながら求めていけば解くことができます。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

typedef pair<int, int> P;

int main(void){
    int n, k;
    long long surface = 4e18;
    cin >> n >> k;
    vector<int> vecx, vecy;
    vector<P> vec;
    for(int i=0; i<n; i++){
        int x, y;
        cin >> x >> y;
        vecx.push_back(x);
        vecy.push_back(y);
        vec.push_back(P(x, y));
    }
    sort(vecx.begin(), vecx.end());
    sort(vecy.begin(), vecy.end());
    for(int xi=0; xi<n; xi++){
        for(int xj=xi+1; xj<n; xj++){
            for(int yi=0; yi<n; yi++){
                for(int yj=yi+1; yj<n; yj++){
                    int cnt=0;
                    long long tmp = (long long)(vecx[xj]-vecx[xi])*(vecy[yj]-vecy[yi]);
                    for(int i=0; i<n; i++){
                        P p = vec[i];
                        if(vecx[xi] <= p.first && p.first <= vecx[xj] && vecy[yi] <= p.second && p.second <= vecy[yj] ){
                            cnt++;
                        }
                    }
                    if(cnt >= k && surface > tmp){
                        surface = tmp;
                    }
                }
            }
        }
    }
    cout << surface << endl;
    
    return 0;
}

AGC014 B問題 Unplanned Queries

問題

agc014.contest.atcoder.jp

解説

まずこの問題では木を根付き木として考えます。各辺は偶数回 +1 されていれば良い、つまり各辺の値が0, 2, 4, ...となっていれば良いのでmod2で考えることができます。そして根をrとすると, +1する辺を(a, b)ならば(a,r)と(r,b)に分解できます。それはLAC(aとbのもっとも近い親)をcとするとa-cに+1, b-cに+1, c-r, r-cに+1ずつされることになりr-cは+2で実質操作を行っていないことになります。

次に奇数回しかクエリに出ていない数の中で一番深いノードをxとするとxの上の辺には+1しかされていないため全てを偶数にすることはできません。 よって全ての数に関して出現回数が偶数であればYES, 奇数回の数があればNOとなります。

コード

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

#define ALL(x) x.begin(), x.end()
using namespace std;

int point[100005];

int main(void){
    int n, m;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        point[x]++;
        point[y]++;
    }
    for(int i=0; i<n; i++){
        if(point[i] % 2 == 1){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}