ABC026_C
※bukaという変数とkouhaiという変数が混ざって大変汚いコード
部下と上司の木を表現してある社員が部下を持たなければ1,
部下を持っていればその部下の中からmax(部下の給料)+min(部下の給料)+1を返す.
メモ化再起風に解いた.
#include <bits/stdc++.h> using namespace std; static const int MAX_N = 20; struct Node{ vector<Node*> kouhai; int kyuuryou; }; Node worker[MAX_N]; int solve(Node *p) { /* 引数(Node*) : 社員 返り値(int) : 給料 worker[num].kyuuryou */ if((int)p->kouhai.size()==0){//部下がいなければ //給料を1にセットしてから給料1を返す p->kyuuryou = 1; return 1; }else{//部下がいれば //部下全員の給料を求めmax(部下の給料)+min(部下の給料)+1を返す vector<int> buka_kyuuryou; int max_kyuuryou = INT_MIN; int min_kyuuryou = INT_MAX; for(int i=0;i<(int)p->kouhai.size();i++){ int tmp = solve(p->kouhai[i]);//部下p->kouhai[i]の給料 buka_kyuuryou.push_back(tmp); max_kyuuryou = max(tmp,max_kyuuryou); min_kyuuryou = min(tmp,min_kyuuryou); } p->kyuuryou = max_kyuuryou+min_kyuuryou+1; return p->kyuuryou; } } int main() { int n,x; cin>>n; for(int i=1;i<n;i++){ cin>>x; worker[x-1].kouhai.push_back(&worker[i]);//社員iの先輩は社員x-1 == 社員x-1の後輩は社員i } solve(&worker[0]); int ans = worker[0].kyuuryou; cout<<ans<<endl; return 0; }
より簡単な方法
部下が上司より後になるのを利用して後ろから計算していく.
int P[MAX_N];//給料 int minP[MAX_N];//部下の給料の最小値 int maxP[MAX_N];//部下の給料の最大値 int sub[MAX_N];//部下の人数 for(int i=N-1;i>=0;i--){ if(sub[i].size()==0){//部下が0人ならば P[1]=1;//給料は1 continue; } //部下がいるならば部下の中で最大+最小+1 maxP[i] = 0; minP[i] = (int)1e9; for(int j=0;j<(sub[i].size();j++){ maxP[i] = max(maxP[i],P[j]); minP[i] = min(minP[i],P[j]); } P[i] = maxP[i] + minP[i]; }
ABC029_C
'a','b','c'から構成できるn文字の文字列を全て挙げる問題.
n=2ならaa,ab,ac,ba,bb,bc,ca,cb,cc
文字が増えていくので文字列と文字列の長さを引数にした関数を作ればよい.
#include <bits/stdc++.h> using namespace std; char alphabet[4] = {'a','b','c'}; int n; void solve(string s,int cnt){ if(cnt == 0){//作っている文字列の長さがnならば cout<<s<<endl; return; } //作っている文字列の長さがn以下ならば //'a','b','c'のどれかを挿れる for(int i=0;i<3;i++){ solve(s+alphabet[i],cnt-1); } } int main() { cin>>n; string s = ""; solve(s,n); return 0; }
ifでreturn文使うよりもelse文を使ったほうが個人的には綺麗だと感じた.
void solve(string s,int cnt){ if(cnt == 0){//作っている文字列の長さがnならば cout<<s<<endl; }else{ for(int i=0;i<3;i++){ solve(s+alphabet[i],cnt-1); } } }
C++ setの要素の検索
setにある要素が含まれているか否かを判定するにはS.find(value)を用いる.
要素が含まれていない場合はS.end()を返す.
よって
if(S.find(x)!=S.end())cout<<"要素あり"; else cout<<"要素なし";
のように判定すればよい.
#include <bits/stdc++.h> using namespace std; int main() { set<int> S; S.insert(1); S.insert(2); if(S.find(2) != S.end()){ cout<<"2あり"<<endl; }else{ cout<<"2なし"<<endl; } if(S.find(3) != S.end()){ cout<<"3あり"<<endl; }else{ cout<<"3なし"<<endl; } return 0; }
レポート表紙
過去のGISTが見れなくなったので再掲
\documentclass[a4j]{jarticle} \usepackage{color} \usepackage{listings,jlisting} \usepackage{ascmac} \usepackage{url} % \lstset{ language={python}, backgroundcolor={\color[gray]{.85}}, basicstyle={\small}, identifierstyle={\small}, commentstyle={\small\ttfamily \color[rgb]{0,0.5,0}}, keywordstyle={\small\bfseries \color[rgb]{1,0,0}}, ndkeywordstyle={\small}, stringstyle={\small\ttfamily \color[rgb]{0,0,1}}, frame={tb}, breaklines=true, columns=[l]{fullflexible}, %numbers=left, xrightmargin=0zw, xleftmargin=3zw, numberstyle={\scriptsize}, stepnumber=1, numbersep=1zw, morecomment=[l]{//} } \usepackage[dvipdfmx]{graphicx} \begin{document} \begin{titlepage} \title{title} \author{author} \maketitle%タイトルを出力 \vspace{8cm} %\center{name} \thispagestyle{empty} \end{titlepage} \appendix \begin{thebibliography}{n} \bibitem{key1}%文献情報 \end{thebibliography} \end{document}
Ctrl+x h ;全範囲選択 Esc-w ;指定範囲コピー
TeX関連コマンド
$platex test.tex $dvipdfmx test.dvi $evince test.pdf
Project Euler 83 Path sum: four ways
問題を見た時からdijkstra法だと分かっていたが集中してやりたかったので敢えて取っておいた問題
#include <bits/stdc++.h> using namespace std; static const int WHITE = 1; static const int GRAY = 2; static const int BLACK = 3; static const int INF = 1<<21; static const int MAX_N = 1000; static const int N = 80; int d[N][N]; int color[N][N]; int M[N][N]; int sx,sy,gx,gy; int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; void dijkstra() { int mincost; //初期化 for(int y=0;y<N;y++){ for(int x=0;x<N;x++){ color[y][x]=WHITE; d[y][x]=INF; } } color[sy][sx]=GRAY; d[sy][sx]=M[sy][sx]; while(true){ //集合Sに隣接している頂点のうち最もコストの小さい頂点を探す mincost=INF; int uy=-1,ux=-1; for(int y=0;y<N;y++){ for(int x=0;x<N;x++){ if(color[y][x]!=BLACK && d[y][x]<mincost){ mincost=d[y][x]; uy=y;ux=x; } } } if(uy==-1 || ux==-1)break;//集合Sの更新が無かったら終了 color[uy][ux]=BLACK;//その頂点を集合Sに挿れる //集合Sに隣接している頂点のd[v]を更新 for(int i=0;i<4;i++){ int vy=uy+dy[i],vx=ux+dx[i]; if(0<=vy && vy<N && 0<=vx && vx<N){ if(color[vy][vx]!=BLACK){ if(d[vy][vx]>d[uy][ux]+M[vy][vx]){ d[vy][vx]=d[uy][ux]+M[vy][vx]; color[vy][vx]=GRAY; } } } } } } vector<string> split(const string &s, char delim) { //文字列から文字をkeyにして分割する vector<string> elems; stringstream ss(s); string item; while(getline(ss,item,delim)){ if(!item.empty()){ elems.push_back(item); } } return elems; } int main() { //test.txt からint型二次元配列をinput std::ifstream ifs("test.txt"); std::string str; int i=0,j; while(getline(ifs,str)) { std::cout<< str << std::endl; vector<string> s = split(str,','); for(int j=0;j<80;j++){ M[i][j] = atoi(s[j].c_str()); } i++; } cout<<"--------------------------"<<endl; sx=0,sy=0; gx=N-1,gy=N-1; dijkstra(); cout<<d[gy][gx]<<endl; return 0; }
C++でファイルの読み込み
複数行の,で区切られた数値を二次元配列に格納する処理
std::ifstream ifs("test.txt"); std::string str; int i=0,j; while(getline(ifs,str)) { std::cout<< str << std::endl; vector<string> s = split(str,','); for(int j=0;j<80;j++){ M[i][j] = atoi(s[j].c_str()); } i++; }
ABC020_C
2分探索と単一始点最短経路問題の問題
dijkstra法は二次元配列と頂点の番号を対応させて考えればよい.
#include <bits/stdc++.h> using namespace std; /* 考え方 1.2文探索でtmp<=tを満たす最大のtmpを見つける 2.dijkstra法で'#'の移動コストがtmpであるとして'S'->'G'への移動コストの最小値を求める */ #define ll long long int static const int WHITE = 1; static const int GRAY = 2; static const int BLACK = 3; static const int MAX_H = 10; static const int MAX_W = 10; static const ll MAX_T = 1e9; static const ll INF = INT_MAX; char maze[MAX_H][MAX_W+1]; ll h,w,t; ll dt[MAX_H][MAX_W];//頂点の始点からの最小距離 ll color[MAX_H][MAX_W];// ll sx,sy,gx,gy; ll dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; void dijkstra(ll tmp) { //次のマスが黒色'#'だったときの移動コストをtmpとしたときのdijkstra法を用いる ll mincost; //初期化 for(ll y=0;y<h;y++){ for(ll x=0;x<w;x++){ color[y][x] = WHITE; dt[y][x] = INF; } } color[sy][sx] = GRAY; dt[sy][sx]=0; while(true){ mincost=INF; ll uy=-1; ll ux=-1; for(ll y=0;y<h;y++){ for(ll x=0;x<w;x++){ if(color[y][x]!=BLACK && dt[y][x]<mincost){ mincost = dt[y][x]; uy=y;ux=x; } } } if(ux==-1 || uy==-1){ break; } color[uy][ux]=BLACK; for(ll i=0;i<4;i++){ ll vy = uy+dy[i],vx=ux+dx[i]; if(0<=vy && vy<h && 0<=vx && vx<w){ if(color[vy][vx]!=BLACK){ ll cost=0; if(maze[vy][vx]=='#')cost+=tmp; else cost+=1; if(dt[vy][vx]>dt[uy][ux]+cost){ dt[vy][vx]=dt[uy][ux]+cost; color[vy][vx]=GRAY; } } } } } } bool judge(ll tmp) { //tmp<=tであるかを判定 //次のマスが黒色'#'だったときの移動コストをtmpとしたときのdijkstra法を用いる dt[sy][sx] = 0; dijkstra(tmp); if(dt[gy][gx]<=t)return true; else return false; } int binarySearch(ll left,ll right) { //二分探索 if(left+1==right)return left; ll mid = (left+right)/2; if(judge(mid)){ return binarySearch(mid,right); }else{ return binarySearch(left,mid); } } int main(){ /* ios_base::sync_with_stdio(0); cin.tie(0); #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif */ //input cin>>h>>w>>t; for(int y=0;y<h;y++){ scanf("%s",maze[y]);//cin>>maze[y]; } //スタート地点とゴール地点を記録 for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ if(maze[y][x]=='S'){ sx=x;sy=y; } if(maze[y][x]=='G'){ gx=x;gy=y; } } } int ans = binarySearch(0,MAX_T); cout<<ans<<endl; return 0; }
単一始点最短経路 dijkstra法
#include <bits/stdc++.h> using namespace std; static const int MAX_N = 100; static const int WHITE = 0;//未踏 static const int GRAY = 1;//確定している点と隣接 static const int BLACK = 2;//確定 static const int INF = 1<<21; int M[MAX_N][MAX_N] = {0};//隣接行列 int d[MAX_N] = {0};//最短経路コスト int color[MAX_N] = {WHITE}; int n,u,k,c,v; void dijkstra(int s){ int mincost; //初期化: 全ての頂点uに対してcolor[u]をWHITE, d[u]をINF, d[s]=0, p[s]=-1; for(int u=0;u<n;u++){ color[u] = WHITE; d[u] = INF; } d[s]=0; color[0] = GRAY; while(true){ mincost = INF; int u = -1; for(int i=0;i<n;i++){ if(color[i]!=BLACK && d[i]<mincost){ mincost = d[i]; u = i; } } if(u==-1){ break; } color[u]=BLACK; for(int v=0;v<n;v++){ if(color[v]!=BLACK && M[u][v]!=INF){ if(d[v]>d[u]+M[u][v]){ d[v]=d[u]+M[u][v]; color[v]=GRAY; } } } } } int main() { cin>>n; for(int i=0;i<n;i++){//隣接グラフは重みINFの辺に初期化しておく for(int j=0;j<n;j++){ M[i][j] = INF; } } for(int i=0;i<n;i++){//隣接リストから隣接グラフへ書き換える cin>>u>>k; for(int j=0;j<k;j++){ cin>>c>>v; M[u][c] = M[c][u] = v; } } //始点は0 dijkstra(0); for(int i=0;i<n;i++){ cout<<i<<" "<<d[i]<<endl; } return 0; }
スクレイピング
imgタグのみを抽出する.
# encoding : utf-8 # for python3 import urllib.request import os.path import pyquery as pq import requests from bs4 import BeautifulSoup import urllib.request from urllib.request import Request, urlopen #def download(url,folderName): def scraping(): url = 'http://umashika5555.hatenablog.com/'#まずはurlをぶち込む req = Request(url) response = urlopen(req)#開け！url html = response.read()#htmlを読み込んでぶち込む soup = BeautifulSoup(html, "lxml")#ここでBeautifulsoupの出番だぁっ #contents = soup.find_all(id = 'contents') #今回抜き出したいタグ contents = soup.find_all("img") #今回抜き出したいタグ for i,content in enumerate(contents): print(i,end="") print('-'*50) print(content) if __name__ == '__main__': scraping()
こんな感じの結果が得られる.
参考
engineer-terminal.com
qiita.com
umashika5555.hatenablog.com
Python3で画像スクレイピング
指定したサイトで画像を一括ダウンロードできる.
備忘録とかそんな感じ — python3.xでweb上の画像を一括ダウンロード
# encoding : utf-8 # for python3 import urllib.request import os.path import pyquery as pq import requests def download(url, folderName): #フォルダが存在していなかった場合は作成する if not os.path.exists(folderName): print (folderName + "フォルダを作成しました") os.mkdir(folderName) save_path = './'+folderName+'/' src= urllib.request.urlopen(url).read() # decodeしない query = pq.PyQuery(src) for img_tag in query('img'): img_url = query(img_tag).attr('src') print (os.path.basename(img_url)) # 確認用でターミナルに保存ファイル名を出力 with open (save_path + os.path.basename(img_url), 'wb') as f: raw = requests.get(img_url).content f.write(raw)#ファイルに画像を書き込む if __name__ == '__main__': print ("写真を取得したいサイトのURLを入力") input_url = input('>>> ') target_url = input_url print ("保存先フォルダ名を入力（※存在しない場合は新規作成）") input_folderName = input('>>> ') target_folderName = input_folderName download(target_url, target_folderName)
このブログのURLを指定した場合こんな感じになった.
Googleの画像検索のURLだとうまくいかない.
全探索 整数を作れるかの問題
配列の要素から整数を作れるかを判定する関数
#include <bits/stdc++.h> using namespace std; static const int MAX_N = 1000; int n;//配列Aの大きさ int m;//判定する整数 int A[MAX_N]; bool solve(int i,int m){ /* 整数mが作れるか否かの再起関数 */ if(m==0)return true; if(i>=n)return false; return solve(i+1,m) || solve(i+1,m-A[i]); } int main() { cin>>n; cout<<"判定する整数"<<endl; cin>>m; for(int i=0;i<n;i++){ cin>>A[i]; } cout<<(solve(0,m)?"possible":"impossible")<<endl; return 0; }
bool solve(int i,int m){ /* 整数mが作れるか否かの再起関数 */ if(m==0)return true; if(i>=n)return false; bool res1 = solve(i+1,m);//A[i]を使わない bool res2 = solve(i+1,m-A[i]);//A[i]を使う bool res = res1 || res2; return res; }
便利ワザ4
INT_MIN,INT_MAXがint型の最大,最小値の定数らしい.
#include <bits/stdc++.h> using namespace std; int main() { int a = INT_MAX; int b = INT_MIN; cout<<a<<endl;//2147483647 cout<<b<<endl;//-2147483648 return 0; }
その他にも
CHAR_BIT //char型のビット数 MB_LEN_MAX //マルチバイト文字の最大バイト数 SCHAR_MIN //signed char型の最小値 SCHAR_MAX //signed char型の最大値 UCHAR_MAX //unsigned char型の最大値 CHAR_MIN //char型の最小値 CHAR_MAX //char型の最大値 SHRT_MIN //short型の最小値 SHRT_MAX //short型の最大値 USHRT_MAX //unsigned short型の最大値 INT_MIN //int型の最小値 INT_MAX //int型の最大値 UINT_MAX //unsigned int型の最大値 LONG_MIN //long型の最小値 LONG_MAX //long型の最大値 ULONG_MAX //unsigned long型の最大値
MySQL2
#テーブルの作成 create database sample; #作成されたテーブルを確認 show databases; #操作するテーブルを選択 use sample; #データの型を入力 CREATE TABLE T01Prefecture ( PREF_CD INT(3), PREF_NAME VARCHAR(10), PRIMARY KEY (PREF_CD) ); #中身を見る select * from to1prefecture; #データの挿入 insert into to1prefecture(PRED_CD,PREF_NAME) VALUES(1,'hokkaido'); insert into to1prefecture VALUES(2,'aomori');#フィールドを順番通りに全て追加する場合はフィールド名を省略可 insert into to1prefecture(PREF_NAME,PREF_CD) VALUES('iwate',3); insert into to1prefecture(PRED_CD,PREF_NAME) VALUES(4,'miyagi'),(5,'aktia'),(6,'yamagata'); insert into to1prefecture set PREF_CD = 7,PREF_NAME='hukushima';#「set」を使う
