(クソコード) 変数宣言と同時に標準入力を受け取りたい [C++編]
得られる情報はないです。
二つに分かれる
C++ で標準入力をするなら、どのようなコードを書きますか?
cinを使うのであれば、
int a;
cin >> a;
このように書けば良いですね。基礎中の基礎です。
時々、
int a; cin >> a;
のように、改行しない一行のコードを見ることがあります。気持ちはわかります。
どうにかして、変数の宣言/入力をまとめてできないでしょうか。
in()でもできない
cinしてその値を返すだけの関数を作ってみるとどうでしょうか。
int in(){ int x; cin >> x; return x; }
これを使えば変数宣言から入力までをまとめて行えます。
in関数で普通にcinしてますが
int a = in();
問題点は 型がintでなければ使えない ことです。
template<typename T> T in(){ T x; cin >> x; return x; }
テンプレートを使うことで型の問題は解消されますが、残念なことにタイプ数が増えます。
int a = in<int>(); double b = in<double>();
各型についてin関数を作るという方法もありますが、それはなんかいやなのでしません。 どうにかして型名を書くのを避けられないでしょうか?
そしてクソコードへ
class Void{ public: Void() { } } const Void IN; class Int{ private: int value; public: Int() { } Int(Void IN){ int x; cin >> x; value = x; } } int main(){ Int a(IN); }
いろいろなものを犠牲にすることで宣言と入力をまとめて行えるようになりました。 入力部分のみに着目すると、タイプ数を3文字(全体の23%)削減することができます。
各型ごとにクラスが必要になるから手間が増えただけ
このままだとvalueにアクセスする手段がないので(publicにしたりget()を作ってもいいですが)、以下の変換関数をクラスに加えておきます。
operator int() const { return value; }
すると、あたかもintであるかのように扱えるようになります。
参考:https://msdn.microsoft.com/ja-jp/library/wwywka61.aspx
Int a(IN); cout << a << endl; // OK cout << a + 10 << endl; // OK
それができたからといってどうにもならないですが。
クイズ
突然ですがクイズです。以下の文はどのように動くでしょうか。
vector<Int> a(5, IN);
正解は、「一度だけ入力を受け取り、その値を使って全ての要素を初期化する」でした。
vectorもまとめたい
vectorの宣言と同時に複数の入力を受け取る、ということも実現したかったのですがその方法が思いつきませんでした。
in関数を使えばできます。ただし、型名を書く必要はありますが。
以下の入力を受け取るとします。全てintに収まる整数です。
N A_1 A_2 ... A_N
template<typename T> T in(){ T x; cin >> x; return x; } template<typename T> vector<T> in(int n){ vector<T> x(n); for(int i = 0; i < n; i++) x[i] = in(); return x; } int main(){ auto a(in<int>(in<int>())) }
かなり奇妙に感じるコードになりました。 in関数が奇妙に感じるのは当然としても、autoがコンストラクタでも型推論をしてくれるのは意外でした。
vector<int> a = {1, 2, 3}; auto b = a; // <- わかる auto c(a); // <- !?
冷静になって考えてみると、奇妙の原因は何をするのかわからないin関数が入れ子になっていることのような気がします。
議論
今のままではできることが減ったintでしかありません。メンバ関数を増やして機能を補いましょう。
結局各型ごとに、例えば Int, Double, String クラス等を作る羽目になりますが、BaseTypeみたいなクラスを作って継承すれば手間は少なくなります。
本当はある部分に変数名を書くだけで入力までしてくれる、というものを考えていたんですが、思いつかないのでやめました。
あとC++編とありますが別の編はないです。
もしかすると言語によってそういうのできるのかなぁ……
結論
普通に書いて。
AOJ 0110 Alphametic
覆面算 | Aizu Online Judge
概要
A + B = C
という形式で式が与えられる。式の長さは 126 以下である。
与えられる数値にはひとつ以上の X が含まれている。
X は 0 以上 9 以下の整数である。
X に当てはまる整数を求めよ。当てはまる整数がない場合は NA を出力せよ。
実装
X に当てはまる数値を全探索する。
多倍長整数でなければオーバーフローする。
ではどうするか。
modを使うのである。
この嘘解法を落とすケースはあるようで、 mod 10^9 + 7 と mod 10^9 + 9 ではWA。
よくわからない大きな素数でmodを取るとACする
#include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,b) for(int i = 0; i < (b); i++) #define all(a) (a).begin(), (a).end() #define show(x) cerr << #x << " = " << (x) << endl; //const int INF = 1e8; using namespace std; const long long M = 67280421310721LL; vector<string> split(string in, char sp = ' '){ vector<string> ret; stringstream ss(in); string s; while(getline(ss, s, sp)){ ret.emplace_back(s); } return ret; } void modmod(vector<string> sp, int start){ range(i,start,10){ vector<long long> a(3,0); rep(j,3){ for(auto c : sp[j]){ (a[j] *= 10) %= M; if(c == 'X') a[j] += i; else a[j] += c - '0'; } } if((a[0] + a[1]) % M == a[2] % M){ cout << i << endl; return; } } cout << "NA" << endl; return; } int main(){ string s; while(cin >> s){ rep(i,s.size()) if(s[i] == '+') s[i] = '='; vector<string> sp = split(s, '='); int start = 0; for(auto& i : sp) if(i.front() == 'X' and i.size() > 1) start = 1; modmod(sp, start); } }
Firebaseをandroidアプリに追加したときにつまずいたポイント
androidアプリにFirebaseを追加する
これは、Firebaseコンソールから行う。
名前や鍵を設定し、google-services.jsonをダウンロードし、所定の位置に置く。
その後、gradleファイルを変更する。
app_name/app/src/build.gradleを以下のように変更。
dependencies { ... compile 'com.google.firebase:firebase-core:11.8.0' .. } apply plugin: 'com.google.gms.google-services'
app_name/build.gradleを以下のように変更。
buildscript { ... dependencies { ... classpath 'com.google.gms:google-services:3.2.0' } }
次に、画面上側のオレンジのバーのSyncをクリックする。
しかし、エラー。
Failed to resolve: com.google.firebase:firebase-core:9.0.0
解決策
app_name/build.gradleを以下のように変更。
allprojects { repositories { jcenter() maven { url "https://maven.google.com" } } }
技術室奥プログラミングコンテスト E - 不可視境界線 (The Invisible Borderline)
E - 不可視境界線 (The Invisible Borderline)
問題概要
辺にコストがある木が与えられる。
各頂点から最も遠い点を求めよ。
考察
木の直径を用いて解を求めることを考えます。
まず、最長パス を求めます。
赤い部分は最長パスに含まれることを表しています。
すると、最長パスに含まれる頂点と、最長パスに含まれない部分木に分けることができます。
最長パスに含まれる頂点 の最遠点
から までの距離と、 から の距離を比較すれば良いです。
部分木に含まれる頂点の最遠点
ある部分木 に含まれる全ての頂点の最遠点は、 の最遠点と一致します。
一致しないと仮定すると、最長パスであることと矛盾します。
- 最長パスの一部を含まないようなパスよりも、含むパスの方が必ず長くなる。
- 最長パスの一部を経由して別の部分木に入るようなパスよりも、入らないパスの方が必ず長くなる。
最遠点が複数ある場合は、頂点番号が小さいものを出力しなければいけないので、そこだけ注意します。
コード
※最長パスが複数ある場合を考えていないのにACしたコード
- bfsで最長パスを求める
- 最長パスに含まれている頂点の最遠点を求める
- 部分木を求める
- 部分技に含まれる頂点の解を求める
- 出力
#include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,b) for(int i = 0; i < (b); i++) #define all(a) (a).begin(), (a).end() #define show(x) cerr << #x << " = " << (x) << endl; using namespace std; #define int long long const int INF = (1LL << 60); const int MAX_V = 100005; class Edge{ public: int to, dis; Edge(){} Edge(int to, int dis): to(to), dis(dis) {} }; vector<Edge> g[MAX_V]; int dis[MAX_V]; vector<int> bfs(int s, int n, bool f){ queue<int> q; rep(i,n) dis[i] = INF; dis[s] = 0; q.push(s); vector<int> pre(n,-1); while(not q.empty()){ int d = q.front(); q.pop(); rep(i,g[d].size()){ Edge e = g[d][i]; if(dis[e.to] == INF){ pre[e.to] = d; dis[e.to] = dis[d] + e.dis; q.push(e.to); } } } int maxi = -1; rep(i,n){ if(dis[i] == INF) continue; if(maxi == -1) maxi = i; if(dis[maxi] < dis[i]){ maxi = i; } } if(f) return vector<int>() = {maxi}; vector<int> path = {maxi}; while(pre[maxi] != -1){ maxi = pre[maxi]; path.emplace_back(maxi); } reverse(all(path)); return path; } //---------------------------- union-find int par[MAX_V]; //親 int depth[MAX_V];//木の深さ void init(int n){ rep(i,n){ par[i] = i; depth[i] = 0; } } int find(int x){ if(par[x] == x){ return x; }else { return par[x] = find(par[x]); } } void unite(int x, int y){ x = find(x); y = find(y); if(x == y) return; if(depth[x] < depth[y]){ par[x] = y; }else{ par[y] = x; if(depth[x] == depth[y]) depth[x]++; } } bool same(int x, int y){ return find(x) == find(y); } //---------------------------- signed main(){ int n; cin >> n; vector<pair<int, int>> e(n - 1); rep(i,n - 1){ int a, b, c; cin >> a >> b >> c; a--; b--; e[i] = make_pair(a,b); g[a].emplace_back(b,c); g[b].emplace_back(a,c); } vector<int> path = bfs(bfs(0, n, 1).front(), n, 0); //最長パスを求める vector<bool> used(n,0); vector<int> ans(n); for(auto i : path){ used[i] = true; if(dis[i] > dis[path.back()] - dis[i]){ ans[i] = path.front(); }else if(dis[i] < dis[path.back()] - dis[i]){ ans[i] = path.back(); }else{ ans[i] = min(path.front(), path.back()); } } init(n); rep(i,n - 1){ //部分木を求める if(used[e[i].first] and used[e[i].second]) continue; unite(e[i].first, e[i].second); } vector<int> par(n); for(auto i : path){ par[find(i)] = ans[i]; } rep(i,n){ if(used[i]) continue; ans[i] = par[find(i)]; } for(auto& i : ans){ cout << i + 1 << endl; } }
ARC 088 E - Papple Sort
E - Papple Sort
公式解説が賢かった(レート1600並感)。
考察
- 回文なので、文字列を半分に分けて考えそう。
- 左右どちらの文字列に合わせて回文にすれば良いのかわからない。
- 外側から貪欲に決めれば最小回数になりそう(適当)
外側から決める方法
以下、スワップする回数をコストと呼ぶ。
回文;????????
余り;ataatmma
回文を a??????a にするとき、必要なコストは0。
回文を t??????t にするとき、必要なコストは4。
回文を m??????m にするとき、必要なコストは6。
よって、a??????a にするのが最善。
回文:a??????a
余り:taatmm
同様に、
aa????aa にするとき、コスト4。
at????ta にするとき、コスト2。
am????ma にするとき、コスト4。
よって、at????ta にするのが最善。
これを繰り返す。
回文:at????ta
余り:aamm
回文:atammata
余り:
計算量
- 外側の文字を決める O(26)
- 外側を決めうちしたとき、必要なコストを求める O(log |S|)
各英小文字につき、何番目に出てくるかを前計算しておき、最も小さい値と最も大きい値(外側に近い)を参照すればよい(前計算 O(|S|)、本計算O(1))。
ただし、「余り」文字列において何番目に現れたかを持っていなければ、コストが計算できない。
そのため、セグ木(BIT)を使って何番目かを再計算する必要がある。
よって、O(log |S|)となる。
- 回文を構築する O(|S|)
したがって、O(26 * |S| log |S|)
実装
#include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,b) for(int i = 0; i < (b); i++) #define all(a) (a).begin(), (a).end() #define show(x) cerr << #x << " = " << (x) << endl; const int INF = 1e8; using namespace std; const int MAX_N = 200005; //[1, n] int bit[MAX_N + 1] = {0}; int sum(int i){ int s = 0; while(i > 0){ s += bit[i]; i -= i & -i; } return s; } void add(int i, int x){ while(i <= MAX_N){ bit[i] += x; i += i & - i; } } bool impossible(vector<vector<int>> v){ int odd = 0; rep(i,26){ if(v[i].size() % 2) odd++; } return odd >= 2; } int main(){ string s; cin >> s; vector<vector<int>> v(26); // 各英小文字が何番目に現れるか rep(i,s.size()){ v[s[i] - 'a'].emplace_back(i); } if(impossible(v)){ cout << -1 << endl; return 0; } pair<int, int> p[26]; rep(i,26) p[i] = make_pair(0, v[i].size() - 1); //front, back int len = s.size() - 1; long long ans = 0; rep(i,s.size() / 2){ int t; int minCost = INF; rep(j,26){ if(v[j].size() <= 1) continue; int front, back; tie(front, back) = p[j]; if(front >= back) continue; int front_p = v[j][front]; int back_p = v[j][back]; int left = front_p - sum(front_p + 1); // 「余り」文字列の何番目に現れるか int right = back_p - sum(back_p + 1); int cost = left + (len - right); // 'a' + j を外側に移動させるコスト if(minCost > cost){ minCost = cost; t = j; } } ans += minCost; add(v[t][p[t].first] + 1, 1); add(v[t][p[t].second] + 1, 1); p[t].first++; p[t].second--; len-=2; } cout << ans << endl; }
Indeed study session に競プロ的な愚直解コードを投げてしまった話
Indeed study session に参加して思ったこと。
Indeed study sessionとは
提出したコードをレビューしてもらえる勉強会。
書いたコードについて色々言ってもらえる。
ちなみに2次募集の締め切りが 12/20 です。
学んだこと
競プロの気持ちでやってはダメだよ
競プロをやる気持ちで書いたコードを投げてはいけない(それはそう)。
無駄な部分は減らそう
AC or TLE で考えると無意味な高速化もちゃんとやらないといけない。
競プロ的に丁寧に書いても読めない
競プロの丁寧は、読めないを読めるようにはしない。
includeを減らす
いらない部分は消す。
参照渡しを使う
for(auto &i : data) とか。
競プロ的にはあまり変わらなくても、無駄は減らす。
using namespace stdはダメ
それはそう。
感想
コードレビューに使うコードは90分で書く必要がある。
簡単に言えば、一問だけの90分コンテスト。
解法が思いつかず、時間ギリギリに愚直解で書いたのが悪かった。
自明に高速化できる部分が多々あった。それでもTLEにはかわりないが。
このような形式であれば、さっさと見切りをつけて部分点解法を書く気持ちで取り掛かった方が良いかもしれない。
アルゴリズムの部分はほぼ触れられていないので、考える部分を間違えた感がある(それはそう)。
コードをきっちりかかないと、それだけレビューの内容も薄くなってしまう。
つめるところはきっちりとつめよう。
全体的に”それはそう”という感想しか出てこない。
dein.vimとdeopleteをmacにインストールする。
dein.vim
dein.vimは暗黒のプラグインマネージャです。
元々neobundleを使っていましたが、後継が1.5年前に出ているのでさすがに乗り換えました。
インストール
githubのQuick start、dein.vimのインストール自体にハマってしまったメモ - Qiitaを参照。
1、Run below script. $ curl https://raw.githubusercontent.com/Shougo/dein.vim/master/bin/installer.sh > installer.sh $ sh ./installer.sh {specify the installation directory}
これを実行すると、最後に「今表示したscriptをvimrcに貼り付けてね(意訳)」と表示されるので見逃さずに貼り付けましょう(1敗)。
" If you want to install not installed plugins on startup. if dein#check_install() call dein#install() endif
この部分のコメントアウトを外して起動時にインストールするようにします。
You can specify revision/branch/tag. call dein#add('Shougo/deol.nvim', { 'rev': 'a1b5108fd' })
vim8だとこの部分で deol.nvim requires Neovim と言われます。
, { 'rev': 'a1b5108fd' } の部分を消して、deol.nvimを削除、その後インストールすれば使えます。
deoplete.nvim
自動補完プラグイン。
インストール
vimrcに以下を記述。
C++の補完のため、deoplate-clangもインストールする。
GitHub - deoplete-plugins/deoplete-clang: deoplete.nvim source for C/C++/Obj-C/Obj-C++ with clang-python3
brew install cmake brew install llvm --with-clang
必要なものを揃える。
call dein#add('Shougo/deoplete.nvim') call dein#add('zchee/deoplete-clang') if !has('nvim') call dein#add('roxma/nvim-yarp') call dein#add('roxma/vim-hug-neovim-rpc') endif
上記をvimrcに追加。
g:deoplete#sources#clang#libclang_path g:deoplete#sources#clang#clang_header
この二つの設定は必須です。
libclang_pathにはlibclang.dylibへのpath、clang_headerはclangディレクトリへのpathです。
libclang_pathと同じディレクトリにclangのディレクトリがあれば、それへのpathをclang_headerにします。
denite.vimはうまく動かないので諦めました。