Codeforces Round #308 Div.2 C - Vanya and Scales
問題
Codeforces Round #307(Div. 2) - C. Vanya and Scales
天秤があり、整数wとmが与えられる。重さm, w^0, w^1, w^2, ..., w^100のおもりを使って、天秤の両側を同じ重さにできるか。ただし、重さmのおもりは必ず使うものとする。
制約
2<=w<=10^9, 1<=m<=10^9
Codeforces Round #307 Div.2 C - GukiZ hates Boxes
問題
Codeforces Round #307(Div. 2) - C. GukiZ hates Boxes
一直線の列があり、列の各地点に箱の山が置かれている。箱が置かれている列の長さはnで、地点i(1<=i<=n)にはai個の箱が置かれているとする。この箱をm人で取り除きたい。各人は1秒に以下の2つの行動のどちらかができる。
- 地点iからi+1に移動する
- 地点iにある箱を1つ取り除く
最初、全員が地点0にいるとき、最小何秒で箱を取り除くことができるか。
制約
時間制限: 2秒
1 <= n, m <= 10^5
0 <= ai <= 10^9 (ただし、少なくとも1つの地点iでai != 0であることが保証されている)
SRM509 div.2 1000 NumberLabyrinthDiv2
問題
TopCoder Statistics - Problem Statement
平面が与えられて、各格子には0〜9の数字もしくは空白(.)が与えられる。
数字の書いてある格子からは、4方向に数字の分だけジャンプして移動できる。0に来た場合はそれ以上移動できない。
スタート地点とゴール地点が与えられて、空白をK回まで書き換えてよいとした場合、移動回数の最小値を求めよ。
どうやってもゴールにたどり着けないときは-1を出力せよ。
SRM509 div.2 500 LuckyRemainder
div.1 250と同じ問題。
問題
TopCoder Statistics - Problem Statement
あるn桁の数字Xに対してsuper(X)を定義する。
super(X)=(Xからm桁(0 <= m < n)取り除いてできる数字の集合の総和)
例:super(123) = 123 + 12 + 13 + 23 + 1 + 2 + 3 = 177
Xが与えられるので、super(X)を9で割った余りを求めよ。
SRM659 div.2 500 PublicTransit
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13793&rd=16462
R行C列のグリッド上に都市があり、距離をマンハッタン距離で計算するとする。
グリッド上に2つteleporterを設置して、その2つを距離0で移動できるとき、全点対の最大距離を最小に2つteleporterを配置したとき、その距離はいくらになるか
制約
0<=R<=10
0<=C<=10
今年やったこと(プログラミング編)
これはknuu Advent Calender*1 初日の記事です！
今年やったこととか書きます！
春休み
競技プログラミング
AOJに登録して競技プログラミングを始める。春休みに200問くらい解く。
前期
学校の演習でコンパイラを作る
C言語のサブセットのTinyCという言語のコンパイラを作る。bisonとかflexとか触った。無駄な拡張をしまくって面白かった。(参考:Hardware and Software Laboratory Project 3B (Software Part))
FPGAに触る
学校の演習でFPGAでCPUを作る。動いたときはすごく達成感があったけど、やっぱりハードウェア方面よりソフトウェア方面のほうが好きだということを確認した。(参考:計算機科学実験及演習 3A)
Eigen
Eigen(C++の行列計算ライブラリ)を使った。暗黒通信団の資料がわかりやすかった。
http://mikaka.org/~kana/dl/pdf/pdf-eigennote.pdf
数値解析の授業で固有値計算法のヤコビ法とかやったのでそのコード書くために使った。
ヤコビ法
べき乗法
実装力向上
実装力を上げるためにいろいろ書いてみた。
練習問題としてここ(練習問題 - プログラミングスレまとめ in VIP)にあるものを書いたりした。
Git
gitの勉強した。本がわかりやすい。
- 作者: Travis Swicegood,でびあんぐる
- 出版社/メーカー: オーム社
- 発売日: 2009/08/12
- メディア: 単行本（ソフトカバー）
- 購入: 25人 クリック: 305回
- この商品を含むブログ (101件) を見る
夏休み
Ingressに消えた
後期
Emacs
Emacs自体は1年前期の演習で使わされ始めてから惰性で使い続けてるが、適当にネットで拾った設定を切り貼りしてたら、コピペしてもうまく設定できない状態に陥ってたので本を買った
Emacs実践入門 ?思考を直感的にコード化し、開発を加速する (WEB+DB PRESS plus)
- 作者: 大竹智也
- 出版社/メーカー: 技術評論社
- 発売日: 2012/03/07
- メディア: 単行本（ソフトカバー）
- 購入: 22人 クリック: 396回
- この商品を含むブログ (1件) を見る
でもちゃんと設定できるようになったしいいや(適当)
Coq
授業でCoqの勉強してる。(Computation and Logic: Winter Semester 2014)
Python
Pythonを書き始める
Pythonを書き始めて1ヶ月がたった - n-knuu's logs
まあ久しぶりにブログでも書くかーって感じで書いたらめっちゃ伸びててびびった。
あと、前期の忙しくなった頃(7月くらい？)にいったん放棄していた競プロを、Pythonで再開した。
Codeforces
初参戦して1完だった。
来年やりたいこと
本を読む
とにかく読んでとにかくコード書く。
本欲しい(切実)
Amazon.co.jp
Vim
V◯mは開いたのはいいけど編集する方法も閉じる方法もわからなくてトラウマになった
— アレ (@n_knuu6) 2014, 12月 10まあこれはプログラミング始めた頃の話なのだけど、いまでも開いてしまった時はターミナルをそっと閉じるようにしてる。
まあでもさすがにこれではまずいのでVimチュートリアルくらいは読んで、設定をできるくらいにはなっとこうと思う。まあEmacsは環境として最高でVimはテキストエディタとして最高ってばっちゃも言ってたし。
競プロ
こどふぉDiv1に上がることを目標に頑張りたい。
Pythonを書き始めて1ヶ月がたった
10月30日にPythonを突発的に始めて1ヶ月がたった。
始めて2週間で学校の課題(Webアプリ)を書いたりした。
技術的にためになる話はないけど、まあ日々のログとして書いておく。
経緯
以下は時期的な話。
- 学科の演習(https://www.db.soc.i.kyoto-u.ac.jp/lec/le4db/)でWebアプリをJavaで書いていたが、Javaプログラム中にhtmlとかSQLとか書いてたらやる気がなくなってきた
- ちょうどそのころPython始めるならまず何を読むべきかなどを情報収集していたら、みんなのPython Webアプリ編がHTML版として無料公開された(みんなのPython Webアプリ編をHTMLで読めるようにしました | TRIVIAL TECHNOLOGIES 4 @ats のイクメン日記)
- ちょっと気分転換としてPythonやってみるかってなった
やったこと(時系列順)
入門
1日でさらっと読み流した。プログラミングやったことない人には難易度高そうという印象。雰囲気つかむだけならすぐに読めると思う。
- みんなのPython Webアプリ編 HTML版
2日で読んだ。HTTPレスポンスの処理とかテンプレートエンジンとかORMとかを自分で作って、セキュリティ対策とか認証とかも自分でやってWebアプリを1から作ろうぜ！って本。始めてWebアプリを作ったのでいい本なのかどうかは判断しかねるけれども、自分は読んでよかったと思う。
Django
ここまでやって、Javaで書いてたWebアプリもPythonで書き直せばいいんじゃね？となる。
選んだ理由は「Python フレームワーク」でググると最初に出てきたからとかたぶんそんな理由。
やりたいこと(というか演習の最低限作らなきゃいけない部分)がだいたい載ってた。入門としてはすごくよかったと思う。
日本語版は1.4までしか翻訳が進んでないので上のDjango入門とはバージョンが違うが、英語をゆっくり読んでる時間もなかったので、適当に読み替えながらやった。まあわからないところは英語版読まなきゃいけないんだけどね。
syncdbが新しいバージョンだとできないんだったっけ…？ よくわかってない上に、多分上のDjango入門を読んだほうがいい。
その後いろいろ
— アレ (@n_knuu6) 2014, 11月 1とりあえずPythonでつぶやいてみた
— アレ (@n_knuu6) 2014, 11月 1とりあえずツイートの仕方とリプライの送り方だけわかった。
これを読み進めつつ、課題のWebアプリを書いた。みんPyは2週間できっちり読み終えた。
- 11月14日にScrapyに触った
みんPyを読んでたら、いとも簡単にWebページを引っ張ってきてhtmlを解析していたことに驚いて、これなら簡単にクローラとか作れるんじゃないのと思って調べたらScrapyを知った。
このページのプログラムを動かして遊んだ。
- 11月22日に標準モジュールのHTMLParserで画像ダウンローダを書いた
ページ内の画像を一括ダウンロードするプログラムが割と簡単に書けた。とは言っても、プログラム中に予めURLとか保存先フォルダをプログラム中に書いておかないといけないというお粗末なもの。
- 11月29日にGoogle App Engine - Python Tutorialをやった
但し読んだのは和訳版。
まだ試作段階なので公開してない
やっとGAEからつぶやけた pic.twitter.com/cU8P2phkEd
— アレ (@n_knuu6) 2014, 11月 28Pythonの日本語の本
最終更新: 2015年12月8日
追記(2017年12月13日)
最近はpythonの本が多すぎて追いきれないため、おそらく以降更新はしません。
ご了承下さい。
Pythonの本
入門
Pythonチュートリアル 第2版
みんなのPython 第3版
たのしいプログラミング Pythonではじめよう!
Pythonスタートブック
Python入門[2&3対応]
空飛ぶPython即時開発指南書 (Programmer’s SELECTION)
初めてのPython 第3版
入門 Python 3
PYTHoNで始めるプログラミング入門
Pythonエンジニア養成読本［いまどきの開発ノウハウ満載！］ (Software Design plus)
Python言語によるプログラミングイントロダクション: 世界標準MIT教科書
データマイニング・機械学習
Pythonによるデータ分析入門 ―NumPy、pandasを使ったデータ処理
入門 ソーシャルデータ 第2版 ―ソーシャルウェブのデータマイニング
実践 機械学習システム
ゲームプログラミング
制御工学
Rのインストールと簡単な計算
3回生にもなって、社会統計学実習Bなる全学共通科目(一般教養科目)をとることにした。
理由は、シラバスにRをやるってかいてあったから。
初回のガイダンスを聞いてると、どうやら統計のことを受講者がまだあんまりやってないらしく(1・2回生が多いしそりゃそうだ)、統計の基本的なことをやりつつ、それをRで例を実際に計算してみる、みたいな実習らしい。
まあこんなことでもしないと自分からはやらないだろうし、統計学の復習になるからいいやと思い受けてみることにした。
とりあえずRのインストールと基本的な操作をメモしておこうと思う。
Rのインストール
とりあえず筑波大のミラーと統計数理研究所のミラー統計数理研究所のミラーをおいておく。
「CRAN」で検索しても出てくる。CRANってのはRのパッケージでユーザが作ったライブラリを公開してたりするらしい。
実際にRを開くと、プロンプトが表れるだけのそっけない感じで、書いたものの再利用もしにくい。
そこで、IDEであるRStudioも一緒に入れたほうが良い。
RStudioのインストールはここのInstallers for ALL Platformsのところから。
RStudioのいいところは定義した変数なり関数なりを表示しておいてくれるところだと現時点では思ってる。
RStudioのエディタで書いたプログラムをカーソルなりで一部だけ選択して実行なんてこともできる。
R言語
以下はR言語についてのメモ。
#以下はコメントとして扱われる。
代入
a <- 1 #整数の代入 Pi <- 3.14 #小数の代入 x <- c(1, 2, 3) # リストの代入、c(…)はリストをつくる関数。
型は勝手に推測してくれるらしい。
計算
演算子は以下。
| 演算子 | 意味 |
|---|---|
| + | 加算 |
| - | 減算 |
| * | 乗算 |
| / | 除算 |
| ^ | 累乗 |
| %% | 剰余 |
| %/% | 整数除算 |
以下は関数。
sqrt(x) # xのルート abs(x) # xの絶対値 x <- scan("<ファイル名>") # <ファイル名>を開いて、xに代入。 # 空白区切りのデータなどを<ファイル名>に入れて上のようにすると、xはリストとなる。
リスト
リストの演算は、リストの要素ごとの演算となる。
つまり、リストarrayに対してarray+2とすると、リストの各要素に2が加算される。
以下は、リストに適用する関数など。
data[n] # リストdataのn番目の要素 length(data) # リストdataの長さ(要素の個数) max(data) # リストdataの最大値 min(data) # リストdataの最小値 sort(data) # リストdataを昇順ソート mean(data) # リストdataの平均 median(data) # リストdataの中央値 var(data) # リストdataの標本分散(不偏分散) sd(data) # リストdataの標準偏差 cor(data1, data2) # リストdata1とdata2の共分散、covじゃないのか… hist(data) # リストdataのヒストグラムを描く #histでは、引数として題名、x軸名、y軸名、クラス数(何個に分けてヒストグラムを集計するか)を指定できる。 hist(data, main="題名", xlab="x軸名", ylab="y軸名", nclass=クラス数) # hist(data)とだけ書いた場合、下のようになる。 hist(data, main="Histogram of data", xlab="data", ylab="Frequency", nclass=dataの範囲) plot(data1, data2) # x要素をdata1, y要素をdata2とした散布図を描く # plotも、引数として題名、x軸名、y軸名を指定できる。 # さらに、プロットする点の形も指定できる。(例えば"+"など) plot(data1, data2, main="題名", xlab="x軸名", ylab="y軸名", pch=点の形) # plot(data1, data2)とだけ書いた場合、下のようになる。 plot(data1, data2, main="", xlab="data1", ylab="data2", pch="○") #さらに、その散布図に縦線や横線を加えることもできる。 abline(v=mean(data1)) # data1の平均(mean)のところに縦線(vはverticalの略)を引く abline(h=mean(data2), lty=2) # data2の平均のところに横線(hはhorizontalの略)を引く # ltyはline typeの略で、線の種類を指定できる # lty=2は破線で、デフォルトでは直線(lty=1)
関数定義
関数を定義する関数functionを利用する。
#関数fooの定義 foo<-function(引数){ statement 1 statement 2 … statement n }
Rの関数の返り値は、関数内で最後に実行した式の結果である。
つまりここでは、statement n の結果が関数の値として返される。
例えば、xを二乗する関数square(x)は以下のように定義できる。
square<-function(x){ x*x }
とりあえずやったところまで。(2014/10/11)
C++の勉強とか蟻本の勉強とか全然進んでない。
入門git 第Ⅰ部(第1章〜第3章)
以前TLで見かけた入門gitを買って読んでる。
- 作者: Travis Swicegood,でびあんぐる
- 出版社/メーカー: オーム社
- 発売日: 2009/08/12
- メディア: 単行本（ソフトカバー）
- 購入: 25人 クリック: 305回
- この商品を含むブログ (101件) を見る
第1章
いろんな用語説明。
リポジトリは金庫と出納簿、作業ツリーが金庫の中身、みたいな感じだろうか。
書くの面倒いので割愛
第2章
2.1 Gitのインストール
gitはcommand line toolをinstallした時に、Apple git-48なるものが一緒に入ってるからそのまま使うことを試みる。
で、git-guiなるgitのGUI出てきて紹介されてるからとりあえず開いてみようとして「git gui」と入力して実行してみる。
でも、そんなコマンドねーよって怒られるから何でだ〜と思ってたら、Apple git-48がだめっぽいので、brew install gitする。
それでも、git --versionしてみてもまだApple git-48が入ってるらしいし、なんでやねんと思ってると、PATHの関係でだめっぽいので、export PATH=/usr/local/bin:$PATHしたらbrewで入れたgitの方になってた。よかった。(でもGUIで使うなら、多分SourceTreeつかうだろうなあ)
2.2 Gitの設定
git configコマンドを使う。とりあえず、本の通りに設定してみる。
user nameとemailのデフォルトの設定
git config --global user.name "名前" git config --global user.email "メール"
--grobalオプションはデフォルトの設定をするときにつける。
なんかgrobalって入力してしまう。
git config --global --list
で今までgit config --globalで設定した一覧が見れる。
git config --global color.ui "auto"
これは色の設定で、設定しておくとあとから見やすい、かも。
2.3 GitのGUI
ふーんって感じ。git-guiとかgitkとかある。Apple git-48ではコマンドがないって怒られる。brewで入れたgitなら大丈夫。
MacだとGitXなるがあるらしい。とりあえず後回し。
2.4 Gitのヘルプ
git help <command>
でマニュアルが見れるらしい。
第3章
コマンド一覧
リポジトリの作成(追跡したいディレクトリで)
git init
1つのファイルをコミット(新たなファイルを作った時でも、変更を加えた時でも同じ)
git add ファイル名 git commit -m "コミットメッセージ"
-mを指定しなければ、エディタが開かれて、コミットメッセージを入力して、保存する。
全てのファイルをコミットしたければ、以下を入力する。
git commit -a
エディタはvimがデフォルトで設定されているので、emacsに変更したければ以下を入力すれば良い。
git config --global core.editor emacs
コミットのログは以下で見れる。(過去n個のコミットのログを見たければ、-nオプションをつければ良い)
git log git log -n
以下を入力すれば、コミットのログがそれぞれ1行で表示できる。
git log --pretty=oneline
また作業ツリーの状態は以下で確認できる。
git status
作業ツリーの状態は、ステージされてない状態と、ステージされてる状態と、コミットされた状態の3つがあるっぽい。
ステージされてない状態でgit addするとステージされてる状態になり、git commitすると、コミットされた状態になる。
コミットメッセージは複数行入力できて、
git commit -m "コミットメッセージ1" \ -m "コミットメッセージ2"
とすれば良い。
ブランチを作成/削除したいときは以下を入力する。
git branch ブランチ名 ブランチ元 git branch -d ブランチ名
ブランチを切り替えるときは以下を入力する。
git checkout ブランチ名
タグを打ちたいときは以下を入力する。(リポジトリにあるtagを確認したい時はタグ名とブランチ名を入力しなければ良い)
git tag タグ名 ブランチ名
リベースしたいときは以下を入力する。
git checkout リベース先ブランチ名 git rebase リベースしたいブランチ名
リモートリポジトリのクローンを作るためには以下を入力する。
git clone リモートリポジトリの場所
蟻本2-4
動的計画法を一旦飛ばして読み進めてる(個数制限なしナップサック問題の漸化式の変形がわからんかった)
プライオリティキュー
使い方
#include <queue> priority_queue<int> pque; // int型のプライオリティキューpque pque.push(num); // numをpqueにpush pque.top() // pqueの最大値 pque.pop() // pqueの最大値をpop pque.empty() //pqueが空ならtrue
プライオリティキューはキューの中身が(デフォルトでは)降順に並べ替えられてるだけで、操作方法(使う関数)は同じ。
中身を昇順にしたければ、宣言の部分を、
priority_queue<int, vector<int>, greater<int> > que;
とすればいいらしい。中身はリファレンス見たけどわからなかった。(vectorとgreaterがわからなかったけど省略した)
これでDijkstraが実装できるぞー(やったぜ)
Expedition(POJ2431)
全部試すとO(2^N)でまあ全探索は無理。
「ガソリンスタンドを通ると燃料缶がもらえて、なくなったところで今持ってる燃料缶を使う。使った回数は？」って言いかえた方が自分はわかりやすかった。ガソリンスタンドの場所気にしなくていいって考えは使えそう。
1番量の多い缶から補給するから貪欲法って言っていいのだろうか。補給場所に制限があったら使えなさそう(補給した次のガソリンスタンドでは補給しちゃダメとか)。
計算量は最悪は全部燃料使った時だからO(N)。
POJに通そうと思ってちょこっと修正したら、サンプルは通ったのにRuntimeErrorだった。
Fence Repair(POJ3253)
前回はO(N^2)の方法が載ってたけどプライオリティキューだとO(NlogN)でいけますね〜という話だけど、前回の時点で、O(NlogN)でソート＋O(logN)で挿入がN回だからO(NlogN)でいけることに気がついてた。二分探索のリファレンス見るの面倒だったから実装してないけども。
二分探索木
ちゃんと実装するとポインタの操作がつらそう(せやろか)。やっぱりあってよかったSTL。
setとかmapとか。
setの使い方
#include <set> set<int> s; // int型のset sの宣言 s.insert(num); // numをsにinsert s.erase(num); // numをsから削除 set<int>::iterator ite; setを探索する用のイテレータite s.begin() // sの先頭(一番初めの一つ前)のイテレータ、最初の要素のイテレータではない s.end() // sの末尾(一番最後の一つ後)のイテレータ、最後の要素のイテレータではない s.find(num); // findはnumがあればnumのイテレータが、なければs.end()が帰る s.count(num); // countはnumがあれば1が、なければ0が帰る(setは重複がないから必ず0か1になる)
勝手にソートしてくれるから二分探索木になってるそうな。
mapの使い方
#include <map> map<int, const char*> a; // int型のキーとchar*型の値を持つmap mの宣言 m.insert(make_pair(num, "hogehoge")); // キーがnumで値がhogehogeであるpairをmにinsert m[num]="hogehoge" // 上と同じ結果が得られる(配列風の書き方ができる) m.erase(num); // numをmから削除 map<int, const char*>::iterator ite; mapを探索する用のイテレータite m.begin() // mの先頭(一番初めの一つ前)のイテレータ、最初の要素のイテレータではない m.end() // mの末尾(一番最後の一つ後)のイテレータ、最後の要素のイテレータではない m.find(num); // findはnumがあればnumのイテレータが、なければs.end()が帰る m.find(num)->first // numが帰る(ポインタ風の書き方ができる) m.find(num)->second // "hogehoge"が帰る
キー付きのsetという解釈してる。
両方ともここ(C/C++ リファレンス)を参考にした。
単に二分木つくるだけだと根に一番小さい値を持ってきた場合とか、アホみたいに深くなるけど、これらは勝手にバランスとって平行二分木になってくれるらしい。やっぱりC++つよい。
