Google Code Jam Crazy Rows (Python)
行列を隣り合った行の入れ替えによって下三角行列に変形する問題
あらかじめ 各行の最後に1が出る場所を記録しておくことで，
O(n^2)に抑えることができる．
Pythonで書いてみた．
たぶんコードは合ってるはずなんじゃが，間違ってたら教えておくれやす．
n = int(input())
m = [map(int, input().split()) for _ in range(n)]
res = 0
a = [0]*n
for i in range(n):
a[i] = -1
for j in range(n):
if m[i][j] == 1:
a[i] = j
for i in range(n):
pos = -1
for j in range(i, n):
if a[j] <= i:
pos = j
break
for j in range(pos, i, -1):
a[j], a[j-1] = a[j-1], a[j]
res += 1
print(res)
半年ぶりに競プロに復活
久々の投稿。
一昨日の土曜日、Atcoder主催のプログラミングコンテストABC158に久々に出た。
たぶん半年ぶりの参加だったと思う。
わけあって休学を始めたと同時にプログラミングを始め、自然と競プロをやるようになっていた自分を、懐かしく感じた。
それまではC++を主に使っていたが、今回はPythonのみで挑戦をした。
結果はABCDの四完。EとFに手も足も出なかったのがとても悔しい。
色は変わらず緑で、Ratingの値は少しだけ上昇した。
久々にコンテストに参加して最初に感じたことは、意外と体に身についているんだなということ。
半年前にバリバリ過去問を解いていた頃に比べ、解法を考える力やプログラムの実装力が落ちたのは確かだが、根本的なアルゴリズムやプログラムを作る考え方は忘れてはいなかった。ABCDを解けたことがそれを実証していると思う。
改めて、プログラミングに出会ったこと、競プロ、Atcoderというサイトに出会ったことは自分に大きな価値を与えてくれているんだなと感じた。
与えてくれた価値をさらに伸ばすために、今後もAtcoderを中心に様々なプログラミングコンテストに参加していきたいと思う。
まずは水色になることを目標に頑張ろう。（入水というらしい。。）
p.s 解説のすぬけさんを久々にみて、なぜか安心した。わら
Macで仮想環境を作ってpythonのmatplotlibを使うの巻
Pythonの仮想環境として今日は「venv」を使いました。
手順
1.新しい環境の作成
$ python3 -m venv [name] ...nameには作りた仮想環境の名前を入れます。
2.Activate
$ source [name]/bin/activate ...仮想環境を始めるためのコマンドです。
3.Deactivate
$ deactivate ...仮想環境を終了させるためのコマンドです。
matplotlib
1.パッケージのインストール
$ pip install numpy ...数値計算を行うライブラリです。
$ pip install matplotlib ...グラフ描画を行うライブラリです。
$ pip install PyQt5 ...グラフを描画する場所を提供するライブラリです。
python pipによるパッケージインストール
pipによるパッケージのインストール
↓
pip install [パッケージ名]
pipでインストールしたパッケージ表示
↓
pip freeze
pipのバックアップの取り方
↓
pip freeze > pip.txt
バックアップの復帰
↓
pip install -r pip.txt
matplotlibの注意点
↓
matplotlibをインポートしようとすると
「ImportError: Python is not nstalled as a framework....」というエラーが出ることがある。
こんな時は、matplotlibの設定ファイル（matplotlibrcというファイル）の
「backend : macosx」という箇所を、
「backend : Tkagg」に変更することで解決する。
この設定ファイルは
$ python -c "import matplotlib;print(matplotlib.matplotlib_fname())"
で場所がわかる。
python pyenvでのインストールメモ
インストールできるバージョンの確認
↓
pyenv install -l
バージョンを指定してインストール
↓
pyenv install 3.7.1
これだとエラーが出ることがある。
自分は「zipimport.ZipImportError: can't decompress data; zlib not available」というエラーメッセージが出た。
この「zlibエラー」は次のようにインストールすることで解決する。
↓
CFLAGS="-I$(brew --prefix readline)/include -I$(brew --prefix openssl)/include -I$(xcrun --show-sdk-path)/usr/include" \
LDFLAGS="-L$(brew --prefix readline)/lib -L$(brew --prefix openssl)/lib" \
PYTHON_CONFIGURE_OPTS=--enable-unicode=ucs2 \
pyenv install -v 3.7.1
アクティブにするバージョンの選択
↓
pyenv global 3.7.1
バージョンの確認
↓
pyenv versions もしくは python --version
機械学習２
前回の続き
性能を評価する指標を決めておく必要がある
どのモデルが性能の良いものか判断ができなくなるから
数種類のアルゴリズムを比較することが不可欠
よく使用される指標は正解率
モデルの汎化性能をテストする必要性がある
（未知のデータにも対応できる力）
これについてはトレーニングデータセットをさらに、トレーニング用のサブセットと検証用のサブセットに分割して、様々な交差検証の手法を試すという方法がある
それで最終的に最適化に成功したと思われつモデルをテストデータセットでテストしてモデルの汎化性能を評価する
↑この評価によって、汎化誤差を評価できる。
この誤差が少なく性能に納得が行けば、このモデルを使って将来のデータを予測できる
などを学習して機械学習の大まかな流れと概念を理解し始めた。
友達はフランス語の文法を習得する間際で、間違いを繰り返してうわーと言いながら頑張っている。
趣味でフランス語を勉強するというおしゃれな彼を今後も応援していきたい。
機械学習
今日は友達と勉強会
友達はフランス語の勉強、自分は機械学習についての勉強をした。
機械学習は大きく分けて3種類ある。
教師あり学習と教師なし学習と強化学習である。
教師あり学習はラベル付きのトレーニングデータ（答えがあるデータ）を用意して、それを機械学習アルゴリズムによって予測データのモデルを作り出す。
そして、未知のデータや将来のデータを予測する。
分類と回帰の2種類などがある。
教師なし学習はラベル付けされていないデータや構造が不明なデータを扱って、クラスタリングや次元削除によってモデルを構築する。
強化学習は環境とのやり取りを通じて報酬を最大化しようとすることでモデルを構築する。
機械学習では前処理がとても大切になってくる。
生のデータがアルゴリズムの性能を最適化するのに必要な形式で提供されることは滅多にない。
特徴量を抽出する、特徴量の尺度を揃える（特徴量のスケジューリング）、特徴量の重複を避けるために低次元の部分空間に圧縮する（次元削除）、データの無関係な特徴量を削除する（次元削除）
することが重要になってくる。
データセットを分割する
トレーニングデータセットとテストデータセット
トレーニングデータセットはモデルをトレーニングして最適化するために使用して、テストデータセットは最終モデルを評価する時まで取っておく
