天下一プログラマーコンテスト2016 予選A C問題 山田山本問題
要約
となるように アルファベットの順番を出力する。
アルファベットの順番は辞書順最小のものを出さないといけない
やること
要約
1. AとBを左端から同じ位置にある文字を1文字ずつ比較して違うタイミングでa->bに有向グラフを張る
2. 明示的に、値が小さい方から取り出すトポロジカルソートを使用する.
- A>B and A.size() != B.size() and グラフを貼れなかったとき: -1
- グラフが閉路を含んでいる時: -1
- 辺を張らなかった頂点も, 孤立した単独の頂点として取り扱う。
トポロジカルソート
有向グラフがすべて一方向を向くように、ノードを並べる。
DFSの方法とKhanのアルゴリズムがある。
トポロジカルソート - Wikipedia
memo
- Khanのアルゴリズムを実装
- 今回は, priority_queueでアルファベットが小さい順に取り出していく.
- 辺の削除はコストが掛かりそうなので, 入力辺の数を数えて, 減らしていきながら数を数えた(∵それぞれの辺は一度しか使用されないため)
- max(残りの入力辺の数) != 0 ならば, 閉路がある(-1を出力する。)
SourceCode
#include <iostream> #include <queue> #include <map> #include <list> #include <vector> #include <string> #include <limits> #include <cassert> #include <fstream> #include <cstring> #include <bitset> #include <iomanip> #include <algorithm> #include <functional> #include <cstdio> #include <ciso646> #include <array> #include <cmath> using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define inf 0x3f3f3f3f #define uinf 0x3f3f3f3f3f3f3f3f #define CLEAR(a) a = decltype(a)() #define MP make_pair #define ALL(a) (a).begin(),(a).end() #define pii pair<int ,int> #define pcc pair<char,char> #define pic pair<int,char> #define pci pair<char,int> #define VS vector<string> #define VI vector<int> #define VVI vector<vector<int>> #define DEBUG(x) cout<<#x<<": "<<x<<endl #define pi 2*acos(0.0) #define INFILE() freopen("in.txt","r",stdin) #define OUTFILE() freopen("out.txt","w",stdout) #define ll long long #define ull unsigned long long #define eps 1e-14 #define FIN std::ifstream cin("D:\input.txt") const int MOD = 1e9 + 7; // @brief topological sort (Khan's algorithm O(|V|+|E|)) // @param G[node] = {to} (G: adjacency list) // @return sorted values (if G is closed: {}) template<class T> vector<T> tsort(const vector<vector<T> >& G) { vector<T> res; vector<T> in(G.size()); for (auto &node : G) for (auto &to : node) ++in[to]; priority_queue<int, vector<int>, greater<int>> que; REP(i, in.size()) if (in[i] == 0) que.push(i); while (not que.empty()) { int n = que.top(); que.pop(); res.push_back(n); for (auto &to : G[n]) if (--in[to] == 0) que.push(to); } return *max_element(ALL(in)) == 0 ? res : vector<T>(); } signed int main(void) { int N; cin >> N; vector<vector<int> > G('z'-'a'+1); vector<bool> check('z' - 'a' + 1); REP(i, N) { string A, B; cin >> A >> B; int size = min(A.size(), B.size()); bool isPush = false; REP(j,size) { if (A[j] != B[j]) { check[A[j] - 'a'] = true; check[B[j] - 'a'] = true; G[A[j]-'a'].push_back(B[j]-'a'); isPush = true; break; } } if (A > B and A.size() != B.size() and (not isPush)) { cout << -1 << endl; return 0; } } vector<int> res = tsort<int>(G); if (res.size() == 0) cout << -1 << endl; else { for (auto &a : res) cout << (char)(a + 'a'); cout << endl; } return 0; }
ubuntuでterminalを強化したけどいろいろ躓いたメモ
Motivation
後輩がfishを使っていたので、これは便利そうだということで、そろそろterminalを強化してみようと思った
以下を参考に、強化したのだが、いろいろ躓いたところがあるのでメモを残す
各コマンドのチェックはwhichコマンドで
環境 Ubuntu16.04
Content
brewの代わりにaptを使用する.
oh-my-fishのリポジトリが変わっている
現在インストール方法はこう
curl -L https://github.com/oh-my-fish/oh-my-fish/raw/master/bin/install | fish
agnosterfishテーマは,
omf install agnoster
のみで良い
powerline/fontsのリポジトリも変わってる
tmuxは一応ソースビルド
automakeとlibevent-devが必要
sudo apt install automake sudo apt install libevent-dev
入ったらこれ
git clone https://github.com/tmux/tmux sh autogen.sh ./configure && make sudo make install
pecoはaptじゃあ入らない
sudo apt install golang export GOPATH=$HOME/go # .bashrcにも追加しておくこと export PATH=$PATH:$GOROOT/bin # .bashrcにも追加しておくこと go get github.com/peco/peco/cmd/peco fish omf install peco
その他functionなど参考
qiita.com
powerlineも変わってる
sudo apt install python-pip pip install powerline-status==2.4 sudo pip psutil
zコマンドがよくわからない
ubuntuでfish(oh-my-fish導入済み)でz
タイトル通り ubuntuでfishでzコマンドが使いたい
1. z.shを持ってきます。
git clone https://github.com/rupa/z cp z/z.sh /usr/local/bin/
2. z.shのパスを指定
~/.config/fish/config.fish に 以下を追加
set -gx Z_SCRIPT_PATH /usr/local/bin/z.sh
3. omf
omf install z
これでfish上でzコマンドが動きます
4. z-fish (2016-10-29追記)
こいつも導入しておくひつようがあるっぽいです
`git clone`をして, `.config/fish/functions`内に`z.fish`を入れてあげる
参考文献
プレゼンツールメモ(主にmarkdown->pdf)
Motivation
最近、研究室に所属しプレゼンをすることが多くなりました。
以前はPowerpointを中心に使用してプレゼン発表をしていたのですが、
数式がださかったり、ソースコードの貼り付けに難があったりといろいろ問題が発生し、
markdownを使用して簡易的な進捗報告をスマートにかつスムーズに作れたらと思いいろいろ調べたのでまとめます。
使い分け
現在、以下の3つのソフトを使い分けています
1. Powerpoint
スライド プレゼンテーション ソフトウェア - Microsoft PowerPoint
2. Marp
yhatt.github.io
3. pandoc
Pandoc - About pandoc
3つとも, 現在(2016-07-14)それぞれ一長一短があります
1. powerpoint: 動画や画像の挿入が楽, 数式がダサく, ソースコードの挿入が難
2. Marp: markdownで表記できて, リアルテイムプレビュー, ソースコードの挿入が楽で画像の挿入が比較的楽, 数式がまだ未対応で、動画が不可
3. pandoc: markdownからtexに変換してpdfにするのに使用する奴, beamerな感じのスライドができる. エディタによるけど画像の挿入がめんどう. 動画は不可
texでも頑張ったら動画を挿入できるそうですが, (高専の時の)先生はそういうときはめんどうなのでpowerpoint使ってるって言ってました。
なので以下のように使い分けをします
1. powerpoint: 動画を挿入するとき。 画像の挿入が多い時
2. Marp: ソースコードやプログラミング中心の発表をするとき
3. pandoc: 数式中心で説明するとき
Marpの数式は将来的に対応するっぽいです(Githubのissueを見る限り)
現在pandocを使用しているのは数式のためなので、対応したらMarpに移行します。
markdown->pandocでスライドを作る
基本方針は, 以前の記事を参考にします。
kurenaif.hatenablog.com
デフォルトでは、日本語が対応していないらしく、このページを参考に以下のファイルを"h-luatexja.tex"という名前で保存しました。
\usepackage{luatexja} \hypersetup{unicode=true} \bigskip\hrule\setbeamertemplate{items}[default]
3行目は, 下のコマンドのthemeだとitem(箇条書きのやつ)がかなり見難いものになっていたので、それをデフォルトの見やすいやつに変更するコマンドです。
beamerを使用する場合, コマンドは以下のように filename.md を filename.pdf にします。
pandoc filename.md -o filename.pdf --latex-engine=lualatex -t beamer -V theme:Madrid -V colortheme:seahorse -V fontsize:12pt -H h-luatexja.tex
themeやcolorthemeをいろいろいじることはできますが, いろいろ試した結果デフォルトの中では一番これがいい感じな気がしました。
以前作ったmd2pdfも今回のスライドも, markdownからpdfという方針は変わっていないので, 同じ実行ファイルでコマンドライン引数でスライドにするか通常のA4のpdfにするかに変更できるように改造しました。
gistff3558b7210ac6c722420f76a6954ff4
これでささっと研究進捗報告ができたらいいですね
Codeforces Div.2 682C Alyona and the Tree
問題要約
ある頂点から部分木の頂点
までの距離を
とする.
すべての,
に対して,
を満たさないようにするために、(木の)葉を取っていく.
取った数を調べる
Python3で競技プログラミングめも
Motivation
Pythonで競技やったら早そう(小並感)と思ったのでABC039をPython3でやってみた
なれたら早そうという印象
実行時間はC++に比べて10倍程度になると思っておいて良い?
C++と比較しながらPython3でのプログラミングをメモしていく(基礎テクニックを随時更新予定)
C++との比較
入力
line = input() # そのまま入力すると文字列型になる(1行分一括) tokens = input().split() # これでスペース区切りの文字列の配列を作る num = int(input()) # 入力が1行に1つの数字だけだったらこれで数字 nums = list(map(int, input().split())) # これで数字のデータのスペース区切りの配列 A, B, C = list(map(int, input().split())) # こうすると3つの数字がA, B, Cの順に入る
出力
print("str") #=> "str\n" print("str", end=" ")#=> "str " print("str", end="")#=> "str" print("{0} {1} {2}".format(0, "a", 2)) # フォーマット記法というらしい(まだ使ってない) arr = [1, 2, 3, 4, 5, 6] # ただの配列宣言 print(*arr) #=> "1 2 3 4 5 6\n" print("{:>6}".format(1)) #=> " 1\n" print("{:>06}".format(1)) #=> "000001\n" print("{:>.6}".format(1)) #=> "1.000000\n"
配列(vector相当)
a = [0]*114514 # 114514のサイズを持つ配列を定義(中身は0) arr = [] #空の配列を宣言 arr.append() #これで.push_back()相当 (型は一様でもなくても可)
2次元配列の宣言
a = [[0 for i in range(W)] for j in range(H)] # arr[H][W] = {}相当 arr = [] # 空の配列を宣言 arr.append([]) # 配列を追加することで動的に二次元配列を作ることができる
REP
for i in range(H): # REP(i,H) <=> for(int i=0;i<H;++i) 相当 arr[i]
if(0 <= x && x < H)
if 0 <= x < H: arr[x]
グローバル変数的な?
def func(): #このように変数があれば引数に渡さずとも使用可能 global S # この1行がないとたとえばS=3みたいなのを書いた時にそっちを参照されるケースがある グローバル変数を使うなら明記する print(S) S = "abc"
三項演算子
print("OK") if True else print("NG") # (True if Boolean else False)
インクリメント
i += 1 # i++はないです
部分配列
arr[x:y] # [x,y)な部分配列を表す(x or yは省略可 省略した場合は最初か最後を指定する感じ) sum(arr[x:y]) # こういう使い方や arr[1:]+arr[:1] # こうすると配列をrotateさせることができる
std::map
dict = {} # これでC++のstd::mapっぽいことができる dict['a'] = 3 # こんな感じで作成, アクセス可能
a == b && b == c
a == b == c
swap(a, b)
a,b = b, a
v.back()
v[-1] # 最終要素にアクセスする -2や-3も同様に後ろから
謝辞
おりさの氏とうさぎさんにいろいろおしえていただいた感謝
