AtCoder CLI + Online Judge Toolsではじめる競プロ
やることリスト
acc new [contestname]
cd a
touch filename
[windows] typenul > filename
g++ main.cpp & oj t -d ./test/
acc submit main.cpp
おわり。g++ main.cpp & ...は多分なんかコマンドあるけど探すのしんどいので見つけたら追記します。gまで打って上矢印押せば推察してくれるし大して差はないやろ（楽観）
DjangoとReactで作るWebアプリ入門
やっていきますよーーー
本日の作業
必要なもののインストール
python -m pip install Django sudo apt install -y nodejs npm sudo npm install n -g sudo n stable sudo apt purge -y nodejs npm exec $SHELL -l curl https://cli-assets.heroku.com/install.sh | sh
Djangoアプリケーションの作成
django-admin startprojcect backend cd backend python mange.py startapp GetLine python manage.py migrate python manage.py runserver
http://127.0.0.1:8000をブラウザで開くとアプリケーションが作れていることがわかります。
GetLineアプリケーションの追加
backend / settings.pyにINSTALLED_APPSを追加します。
INSTALLED_APPS = [
...
'GetLine',
]
GetLine / models.pyに追記します。
from django.db import models
# Create your models here.
class GetLine(models.Model):
line_name = "line_name"
line_color = "line_color"
def _str_(self):
return self.line_name
追記したらmakemigrationsしておきます
python manage.py makemigrations GetLine python manage.py migrate GetLine
Superuserの設定
python manage.py createsuperuser
UsernameとEmailとPasswordを設定します。これで http://127.0.0.1:8000/admin/ から管理者ページヘアクセスすることができるようになります。
Heroku用の設定
ファイルの追加
rootに
Procfile
web: gunicorn backend.wsgi
requirements.txt
dj-database-url==0.5.0 Django==2.2.6 django-heroku==0.3.1 gunicorn==20.1.0 psycopg2==2.8.4 pytz==2019.3 whitenoise==4.1.4
runtime.txt
python-3.10.4
heroku.yml
build:
docker:
web: Dockerfile
.ignore
*.log *.pyc __pycache__/ db-volumes/ db.sqlite3
composer.json(空)
backendディレクトリ
local_settings.py(追加)
import os
BASE_DIR = os.path.dirname(os.path.dirname(__file__))
DATABASES = {
'default': {
'ENGINE': 'django.db.backends.sqlite3',
'NAME': os.path.join(BASE_DIR, 'db.sqlite3'),
}
}
DEBUG = True
settings.py
import osまとめ〜
〜
DEBUG = False
ALLOWED_HOSTS = ['.herokuapp.com', '127.0.0.1']
MIDDLEWARE = [
'whitenoise.middleware.WhiteNoiseMiddleware',
]
LANGUAGE_CODE = 'ja'〜
TIME_ZONE = 'Asia/Tokyo'
STATIC_ROOT = os.path.join(BASE_DIR, 'staticfiles')
STATIC_URL = 'static/'
DATABASES = {
'default': {
'ENGINE': 'django.db.backends.sqlite3',
'NAME': str(BASE_DIR / 'db.sqlite3'),
}
}
STATICFILES_DIRS = (
os.path.join(BASE_DIR, 'static'),
STATICFILES_STORAGE = 'whitenoise.storage.ComprまとめessedManifestStaticFilesStorage'
import django_on_heroku
django_on_heroku.settings(locals())
)
Reactアプリの作成
rootに移動してから
npx create-react-app frontend
起動は
cd frontend npm start
まとめ
1, 2ヶ月前に同じところはやったけど再び開いたら動かなくなっていたのでやり直しです......8時間ぐらいかかりました。つらい。明日は同じDynoの上で起動できるようにします。あと、今日の段階だとherokuでエラーが発生しますがそれはmanage.pyがrootより一段階深いところにあるからっぽいです（階層を移動させたらちゃんと起動した）なので明日の作業が終わればちゃんと動く！はず！
それでは〜〜〜
Ubuntuの初期設定とか
何もしていないのにインターネット周りのドライバが壊れました()
色々格闘したけどネットつながってない状態でドライバ復旧させるのはちょっと自分のスキルを超えていたので、(データは全部クラウドにバックアップ取れてるし)すべて消して0から新しいUbuntu人生を歩むことにしました。
できればこんなことは避けたいですが次があるかもしれないのでメモしておきます。
Ubuntuのインストール
UbuntuのISOファイルをインターネット上からダウンロードしてきて をつかってインストールディスク(usb)を作成します。
インストールしたいPCを起動し、OS(WindowsとかUbuntuとか)が立ち上がる前にブートオプションメニューに入り、usbを選択します。その後は指示に従ってインストールしていきます。このとき、使わないディスクは取り外しておきましょう。違うところにインストールして大事なデータが消えてしまっては目も当てられません。また、個人的にはドキュメントやピクチャといったディレクトリ名が英語になって打ちやすいのでインストール時は英語を選択しています。
GoogleChromeのインストール
Firefoxを経由して/Downloadsにgoogle-chrome-stable_...をダウンロードします。これを右クリックして別のアプリケーションで開く>ソフトウェアのインストールを選択してインストールします。
mozc(日本語入力)のインストール
端末を開き、以下のコマンドを入力します。すべて終了したら、再起動します。
sudo apt update sudo apt install -y fcitx-mozc im-config -n fcitx fcitx-autostart
設定>キーボードで、mozcを追加します
私はUSキーボードを使用しており、半角/全角キーがないのでMacよろしく左右altキーの空打ちで英語/日本語入力を切り替えています。fcitx設定を開き、全体の設定タブのShowAdvancedOptionsにチェックマークを入れた後、以下の東リ設定します。
入力メソッドをオンに : Ralt
入力メソッドをオフに : Lalt
あと細かい外観もここで変更ができます。
クラシックUIのフォントサイズを8に、ヒントメッセージと入力メッセージの色を変更しています。
外観
最低限動くようになったので気分を上げるために外観をいじっていきます。
設定>外観から、ダークモードのオンオフとメインカラーの設定ができます。
ついでに端末の背景透過とカラーの変更も行っておきます。
VScodeのインストール
ここ(https://code.visualstudio.com)から.debファイルをインストールしてGoogleChromeと同じ要領でインストールします。
GitHubアカウントと紐付けておけば拡張機能やら諸々を同期してくれるので楽ちんです。
Pythonとか
デフォルトで入っているには入っていますがpyenvを使います。
$ sudo apt update
$ sudo apt -y upgrade
$ sudo apt -y install make build-essential libssl-dev zlib1g-dev libbz2-dev \
libreadline-dev libsqlite3-dev wget curl llvm libncurses5-dev libncursesw5-dev \
xz-utils tk-dev libffi-dev liblzma-dev
$ sudo apt install git
$ git clone https://github.com/pyenv/pyenv.git ~/.pyenv
$ cd ~/.pyenv
$ git checkout v2.2.5
$ sed -Ei -e '/^([^#]|$)/ {a \
$ export PYENV_ROOT="$HOME/.pyenv"
$ a \
$ export PATH="$PYENV_ROOT/bin:$PATH"
$ a \
$ ' -e ':a' -e '$!{n;ba};}' ~/.profile
$ echo 'eval "$(pyenv init --path)"' >>~/.profile
$ echo 'eval "$(pyenv init -)"' >> ~/.bashrc
$ source ~/.bashrc
$ pyenv -v
$pyenv install 3.10.3
$ pyenv global 3.10.3
GitHub
$ git config --global user.name [名前] $ git config --global user.email [メールアドレス] $ ssh-add ~/.ssh/[id_rsaとか] $ ssh-add ~/.ssh/[id_rsaとか].pub
GitHubにログインして、Settings>SSH and GPG keys>SSH keysに表示されたssh-rsaから始まる文字列をコピペ。
その他
$ sudo apt install nodejs $ sudo apt install npm $ npm install --global yarn
【競プロ覚書】SCC
本日のお題はSCC(StronglyConnectedComponents、強連結成分分解)です。有向グラフにおいて、相互に行き来できる成分ごとに分解できるものです。計算量はO(V+E)
【22 日目】
— E869120@本発売 (@e869120) 2021年4月22日
昨日の解説と今日の典型問題です。今日は立方体の問題です！！！
なお、AtCoder ジャッジへの問題追加は 15 時頃を予定しています。（入力形式・入出力例は GitHub を参照のこと） #競プロ典型90問 pic.twitter.com/mHRaIeiZWY
DFSを2回やることがポイントで、1回目は行き止まりになった順番に番号を記録、2回目はその頂点の順番で枝の向きを逆にしたグラフに対してDFSをします。
詳しくは下のリンクで
強連結成分分解の意味とアルゴリズム | 高校数学の美しい物語
コード
使いやすいようにクラス化しました。
AddEdge(a, b) : A→Bの辺を追加
isSame(u, v) : 頂点uと頂点vが同じ強連結成分に含まれているか
GetGroup(u) : 頂点uの含まれている成分の番号を取得
GetGroup_num() : 全てで幾つの強連結成分に分かれているかを取得
GetGroup_size(i) : 成分iに含まれている頂点の数を取得
class StronglyConnectedComponents { private: vector<bool> used; vector<int> G[1 << 18]; vector<int> H[1 << 18]; vector<int> I; vector<int> group; vector<vector<int> > group_component; int group_num; void dfs1(int pos) { used[pos] = true; for(int i : G[pos]){ if(used[i] == false) dfs1(i); } I.push_back(pos); } void dfs2(int pos, int _group) { used[pos] = true; group[pos] = _group; group_component[_group].push_back(pos); for(int i : H[pos]){ if(used[i] == false) dfs2(i,_group); } } public: void AddEdge(int from, int to) { G[from].push_back(to); H[to].push_back(from); } void Init(int vertex_num) { group.assign(vertex_num+1, -1); used.assign(vertex_num+1, false); group_num = 0; for(int i=1;i<=vertex_num;i++){ if(used[i] == false) dfs1(i); } reverse(I.begin(), I.end()); used.assign(vertex_num+1, false); for(auto &i : I){ if(used[i] == true) continue; group_component.push_back(vector<int>()); dfs2(i,group_num); group_num ++; } } bool isSame(int u, int v) { return group[u] == group[v]; } int GetGroup(int u) { return group[u]; } int GetGroup_num() { return group_num; } int GetGroup_size(int _g) { return group_component[_g].size(); } };
【旅程表 #04】(例外処理が)もう終わりだみぃ
前回最後に言った通りに正規表現についてやっていきます
そもそも正規表現とは
まずはそこから。平たく言えば欲しい文字列があるか探すための便利なツールみたいなものです(素人並説明)
たとえば'abcdefghijklmn'という文字列があって、この中に'de'という文字列があるかを探したい時、これだけなら前から見ていけばいいだけで済みますが、'eから始まってiで終わる5文字の文字列'があるかどうかやもっと複雑なものを見たいときにこの正規表現が役立ちます。 今回は、ジョルダン 乗換案内・路線情報・時刻表・運行情報サービスから出力したtxt形式の乗り換えデータをcsvファイルに落とし込んでいきます。
どうデータを抽出するか
ジョルダンは乗り換えを検索してテキストというボタンを押せば文章として乗り換え案内を出力することができます(←神サイト)(普段はYahoo!を使っているけれどurlでしか出力してくれないので解雇)
■東京 6番線発 ｜ 京浜東北線(大船行) 6.8km 4・6・7・8号車 ｜ 04:41-04:53［12分］ ｜ 6,930円 ◇品川 5番線着・11番線発 ［17分待ち］ ｜ 東海道本線（東日本）(小田原行) 77.1km ｜ 05:10-06:21［71分］ ｜ ↓
データを取ろうと思えばapiという手段もあるのですがいまいち使い勝手が悪い(後述)のと有料だったりするので使いません。
さて、この出力されたテキストデータからどのデータを抽出するかですが、 - 発着駅 - 発着時間 - 発着番線 - 行先 は簡単に取れそうです。列車番号とかはデータないのでそれは後から編集で。 まず、発着駅については■や◇というのが行の最初にあるのが目印になっているので、row[0]で判定して最初の空白文字までを取れば終わりです。 次に発着時間についても、HH:MM-HH:MM形式を探して抜くだけですし、発着番線については\d番線発(or着)って書かれてるのでそれで終わりです。発着番線についてはデータなしのため空欄になっている可能性もあるのでそもそもあるかどうかも確認しないといけません。余裕だろって思ったんですがどうもうまくいきません。
東海道本線（東日本）(熱海行)
一行の中に半角と全角を混ぜるな
とまぁ問題はありましたがここまでをまとめると
datalist = ['1'] datalist.append(trigger.group()[1:]) #発駅 datalist.append(DATE_current + ' ' + txt_data[i+2][3:8]) #発時間 datalist.append(re.match(jorudan_datapattern_train,txt_data[i+4]).group()[1:]) #着駅 datalist.append(DATE_current + ' ' + txt_data[i+2][9:14]) #着時間 datalist.append(re.match(後述) #路線 datalist.append('') #列車番号 datalist.append('') #列車種別 datalist.append(re.search('\(\D+行\)',txt_data[i+1]).group()[1:-1]) #行先 if(re.search('\d+番線発',txt_data[i])): #発番線 datalist.append(re.search("\d+番線発",txt_data[i]).group()[:-3]) else: datalist.append('') if(re.search('\d+番線着',txt_data[i+4])): #着番線 datalist.append(re.search('\d+番線着', txt_data[i+4]).group()[:-3]) else: datalist.append('') txt_formatting.append(datalist)
最終的に
csv.writer(csv_file).writerows(txt_formatting)
でcsvに保存するので二次元配列的にデータを保存すればいいみたいです。
路線データ
これは始める前から絶対にめんどくさくなるというのがわかっていた問題ですが、路線名称についてはややこしいです。 まず東京→名古屋の乗り換えがこちら
■東京 14番線発 ｜ のぞみ1号(N700系)(博多行) 366.0km ｜ 06:00-07:34［94分］ ｜ 6,380円（ 指定席 4,720円 ） ■名古屋 17番線着
はい。特急や快速列車の場合は路線名ではなく列車名が表示されるんですね。なので路線名は得られません。もっというと東海道本線のJR西日本区間は琵琶湖線/京都線/神戸線と表示されるのでもやもや感はありますね。 これの対処法として発駅と着駅を両方含む路線をデータベースから引っ張ってくるということも考えましたが、マリンライナー(宇野線・本四備讃線・予讃線経由)と言ったものの処理が難しいのと、横浜→大船のように複数経路(東海道本線・根岸線)が考えられる場合も考えないといけません。
鉄道以外
とりあえず鉄道のみの乗り換えに関しては一応動くという形になりましたが。実際のところは徒歩や航空機、船舶利用時にはフォーマットが異なってくるので動きませんorz。うーんでも例外処理とかいちいちやってたら完成しないのでとりあえず後から考えるということでーーー
【旅程表 #03】エラーないっていったよね
あ、お気づきの人もいるかもしれませんが全12回を予定しています
ファイルを分ける
なんかこれからもコードがどんどん増えていってごっちゃになりそうなのでファイルを分けていきたいと思います。 とりあえず
- main.py
- config.py
- Edit_xlsx.py
に分けたいと思います。
main.pyに他の二つのファイルの読み込みをさせます。configファイルにはパスとか保存したいので、毎回config.〜ってするのは面倒です。なので(非推奨みたいな記事を見かけた気もしますが)fromとワイルドカード使って読み込みをします。
import Edit_xlsx from config import *
ファイル間の共有
と、ここまでは(単にコピペするだけなので)良かったのですが、ファイル間での変数の共有がめんどくさいということに気づきました。例えば変数workbookを置きたいとして、他のファイルと相互に共有するのが面倒なことになっています。グローバル変数で全部のファイルで名前共有してくれれば便利なのにそうは問屋が卸さないようです。
とまぁ数十分悩んでいたのですが、最終的に引数でxlsxファイルのworkbookオブジェクトと編集する内容をわたすようにしました。また、日付データだけ別フォーマットで保存すると後々ややこしいことになりそうなので乗り換えデータの発着時刻に日付データも入れるようにして
#main.py
Edit_xlsx.edit(row, workbook)
#Edit_xlsx def edit(row, workbook) : worksheet = sheet_edit(date, workbook) ............
時系列入れ替え
前のままだと単純に下に下に追加されていくだけなので時系列で並べられるようにしていきます。流れとしては、 時刻データ取得→既存のデータの適切な位置に空白行を挿入→挿入した行を編集 とします。 時刻データはdatatimeを使います。データとしてはYYYY/MM/DD HH:MMと入れています。
start_time = datetime.datetime.strptime(row[2],"%Y/%m/%d %H:%M") st_t = datetime.datetime.strftime(start_time,"%H:%M") end_time = datetime.datetime(1,1,1) en_t = '' if row[0] in ["1","2","3","4"]: end_time = datetime.datetime.strptime(row[4],"%Y/%m/%d %H:%M") en_t = datetime.datetime.strftime(end_time,"%H:%M")
これで発着日時刻とHH:MM形式の文字列を取得できました。 その上で、時刻データが保存されているのはA列なので、A列を上から見ていって(空白)または(発時刻より前)なら下へ移動する、を繰り返します。また、記入されている最終行までいったらそこでbreakすることも忘れずに。
while worksheet.cell(row=row_write,column=1).value==None or worksheet.cell(row=row_write,column=1).value < datetime.datetime.strftime(start_time,"%H:%M"): row_write += 1 if row_write > worksheet.max_row: break
また、着時刻も見て次の発車時刻より後に到着するみたいなことが起きていないかも確認します。
row_duplicate_check = row_write while row_duplicate_check<=worksheet.max_row: if worksheet.cell(row=row_duplicate_check,column=1).value!=None and worksheet.cell(row=row_duplicate_check,column=1).value < datetime.datetime.strftime(end_time,"%H:%M"): print("時間重複") return row_duplicate_check += 1
ここまでできたら、認識コード(鉄道かバスかetc)をもとに何行挿入すればいいかを確認しつつinsertするだけです。
#insert rows rows_numbers = [0,4,3,3,3] worksheet.insert_cols(row_write,rows_numbers[int(row[0])])
は？
んーずれてますね。
ぱいてょんしょしんしゃさんなのでこれで1時間悩んでました。
わかりましたか？
列挿入してるやん！うーんざこ
はい。というわけでcolsをrowsに変えて完成！
txt→csvの内容まで含めると分量が多くなりすぎちゃうので今回はここでおしまいです。ではまた。
【旅程表 #02】完全に理解した
※ダニング・クルーガー効果
昨日に引き続き旅程表アプリを作っていきます。今回は大まかな雛形とxlsxファイル操作をします。
CSVファイルの準備
最終的にどんな感じになるかはまだわかりませんがネットの乗り換え案内のコピペで時刻とか自動で入力できたらいいなって思っているので
元データ→python→CSVファイル→python→xlsxファイル
というような流れでデータを処理していくことにします。
入れたいデータとしては発着する駅と時刻、番線と路線名、列車番号、列車種別(普通/快速/特急〇〇号とか)、行先です。(ホームミスって乗り換え失敗したことが幾度とあるため)あと鉄道だけではなくて船だったり徒歩だったり、あるいは美術館とかも入れたいのでその識別番号とオプション的なものを前後につけて
識別番号, 発駅, 発時刻, 発番線, 着駅, 着時刻, 着番線, 路線, 列車番号, 列車種別, 行先, オプション
としてみます。 準備したものはこちら
0,20220214 1,東京,0700,15,名古屋,0839,16,東海道新幹線,203A,のぞみ203号,新大阪,0 1,名古屋,0845,6,大垣,0918,,東海道本線,,特別快速,大垣,0
特別快速の列車番号を調べるのがめんどくさかったので空欄です(おい)
xlsxファイルの初期設定
余白設定
とりあえず周りを1インチずつ余白をとってヘッダーフッターはとらないようにしてみます。コードは以下の通り。
#margines settings worksheet = workbook.active worksheet.page_margins.left = 1 worksheet.page_margins.right = 1 worksheet.page_margins.top = 1 worksheet.page_margins.bottom = 1 worksheet.page_margins.header = 0 worksheet.page_margins.footer = 0
セルの幅の設定
とりあえず適当です。↓みたいな感じに。
worksheet.column_dimensions['A'].width = 5 worksheet.column_dimensions['B'].width = 1 worksheet.column_dimensions['C'].width= 3 worksheet.column_dimensions['D'].width = 7 worksheet.column_dimensions['E'].width = 35 worksheet.column_dimensions['F'].width = 15
ファイル書き込み
CSVファイル
とりあえずさっきつくったCSVファイルを開きます。
with open(csv_filename, encoding='utf8',newline="") as csv_file: csvreader = csv.reader(csv_file) for row in csvreader:
これでファイルが開けてそれぞれの行ごとに処理していくことができます。
シート作成
それぞれの日に分けてシートに保存したいのでまずはそこから作っていきます。 シート名には日付を設定するとしてほしい日付のシートがあるかを調べればいいので、workbook.sheetnamesでシート名を取得した後if inで条件を満たすものがあるかを調べます。 ここでのrowは日付の含まれている[0,20220214]です
if not row[1] in workbook.sheetnames: workbook.copy_worksheet(workbook.worksheets[0]) workbook.worksheets[-1].title = row[1] worksheet = workbook[row[1]]
最後にworksheet = workbook[row[1]]として操作するシートを指定しています。 既存の場合だとifの内容が処理されないので操作するシートが指定されるだけです。
データ書き込み
ここまでできたのであとはmax_rowでシートのどこまで記入されているかを確認した上でその次の行からデータを埋めていくだけです。
if row[0] == "1": row_write = worksheet.max_row + 1 worksheet.cell(row=row_write,column=4).value = row[1] worksheet.cell(row=row_write,column=1).value = row[2] worksheet.cell(row=row_write,column=3).value = row[3] worksheet.cell(row=row_write+3,column=4).value = row[4] worksheet.cell(row=row_write+3,column=1).value = row[5] worksheet.cell(row=row_write+3,column=3).value = row[6] worksheet.cell(row=row_write+1,column=5).value = row[7] worksheet.cell(row=row_write+1,column=6).value = row[8] worksheet.cell(row=row_write+2,column=5).value = row[9] worksheet.cell(row=row_write+2,column=6).value = row[10]
まとめ
これまでのコードのまとめです
import openpyxl import os import csv name = "Sample1" # xlsx_filename = name + ".xlsx" #filename = path + filename #filename = os.path.expanduser(filename) csv_filename = name + ".csv" workbook = "" worksheet = "" if os.path.exists(xlsx_filename): #open file print("File exists.") workbook = openpyxl.load_workbook(xlsx_filename) else: #create new file print("File doesn't exist.") workbook = openpyxl.Workbook() workbook.save(xlsx_filename) #edit sheet name workbook.worksheets[0].title = "TITLE" #margines settings worksheet = workbook.active worksheet.page_margins.left = 1 worksheet.page_margins.right = 1 worksheet.page_margins.top = 1 worksheet.page_margins.bottom = 1 worksheet.page_margins.header = 0 worksheet.page_margins.footer = 0 #dimensions settings worksheet.column_dimensions['A'].width = 5 worksheet.column_dimensions['B'].width = 1 worksheet.column_dimensions['C'].width= 3 worksheet.column_dimensions['D'].width = 7 worksheet.column_dimensions['E'].width = 35 worksheet.column_dimensions['F'].width = 15 with open(csv_filename, encoding='utf8',newline="") as csv_file: csvreader = csv.reader(csv_file) for row in csvreader: print(row) if row[0] == "0": print("Check DATE") if not row[1] in workbook.sheetnames: workbook.copy_worksheet(workbook.worksheets[0]) workbook.worksheets[-1].title = row[1] worksheet = workbook[row[1]] if row[0] == "1": row_write = worksheet.max_row + 1 worksheet.cell(row=row_write,column=4).value = row[1] worksheet.cell(row=row_write,column=1).value = row[2] worksheet.cell(row=row_write,column=3).value = row[3] worksheet.cell(row=row_write+3,column=4).value = row[4] worksheet.cell(row=row_write+3,column=1).value = row[5] worksheet.cell(row=row_write+3,column=3).value = row[6] worksheet.cell(row=row_write+1,column=5).value = row[7] worksheet.cell(row=row_write+1,column=6).value = row[8] worksheet.cell(row=row_write+2,column=5).value = row[9] worksheet.cell(row=row_write+2,column=6).value = row[10] workbook.save(xlsx_filename)
これを3回実行した結果がこちら
重複処理とかしてないのでこんな感じになっちゃいますね。
あと名古屋が2列連続並んでいるのも気持ち悪いですし、時刻の早い順からデータを入力できればいいですが前後したりした場合に対応できてないので次はそこら辺を実装していきたいと思います。あと、xlsxファイルへの入力は他のところでも使い回すことになりそうなので別ファイルに移したりして見やすくもしたいです。
今日はここまで。それでは〜
