読者です 読者をやめる 読者になる 読者になる

noyのブログ

プログラミングとかゲームとか

AOJ - 2170 Marked Ancestor

Marked Ancestor | Aizu Online Judge

問題概要

木が与えられる。
以下の2つのクエリを処理し、出力された番号の合計を求める。

  • 頂点aをマークする
  • 頂点aから最も近いマークされた祖先の番号を出力する
解法

union-find

このスライドにある解法をそのまま実装した。
http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2009%2FPractice%2F夏合宿%2F講評&openfile=3f.pdf

入力を隣接リストで受け取った後、クエリ ’M' だけを処理する。
マークされた頂点を記録する。このとき、同じ部分にマークされた場合、処理せずなかったものとして扱う。

その後、与えられた木を構築するためdfsを行う。このとき、depthに木の深さを記録した。
深さの情報をもとに、マークされなかった頂点と、その頂点の親をuniteした。
常に根に近い部分を親としてuniteしなければいけないため、深さを利用した。

後はクエリを逆順に処理していく。
’Q' クエリはfindし、値を足す。
'M' クエリは、自分の親とuniteする。

木を構築する、各頂点の親を持つ、uniteするときに根に近い頂点を親にする、などやることが多く実装に時間がかかった。

コード
#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;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 2000000000;
using namespace std;

const int gmax_n = 100005;

int par[gmax_n]; //親
int depth[gmax_n];//木の深さ

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;
    }
}

bool same(int x, int y){
    return find(x) == find(y);
}

void dfs(vector<int> t[gmax_n], int g[gmax_n], int cur){
    rep(i,t[cur].size()){
        int next = t[cur][i];
        if(g[next] != -1) continue;

        depth[next] = depth[cur] + 1;
        g[next] = cur;
        dfs(t,g,next);
    }
}

int main(){
    int n, m;
    while(cin >> n >> m, n||m){
        vector<int> tree[gmax_n];
        init(n);
        rep(i,n - 1){ //木の構築
            int a;
            cin >> a;
            a--;
            tree[i + 1].emplace_back(a);
            tree[a].emplace_back(i + 1);
        }

        bool marked[gmax_n] = {false};//マークされるノードを記録
        marked[0] = true;
        vector<pair<char, int>> q;
        rep(i,m){
            char a;
            int b;
            cin >> a >> b;
            b--;
            if(a == 'M'){
                if(marked[b]) continue; //同じ部分にマークした場合は、初回以外を無視。
                else{
                    marked[b] = true;
                    q.emplace_back(make_pair(a, b));
                }
            }else{
                q.emplace_back(make_pair(a,b));
            }
        }

        int g[gmax_n] = {0};
        range(i,1,gmax_n) g[i] = -1;
        dfs(tree, g, 0);

        rep(i,n){
            if(not marked[i]) unite(g[i], i);
        }

        //rep(i,n) show(g[i])
        //rep(i,n){ show(find(i)) }
        //rep(i,n){ show(depth[i]) }

        long long ans = 0;
        for(int i = q.size() - 1; i >= 0; i--){ //クエリを逆順に処理
            if(q[i].first == 'Q') ans += find(q[i].second) + 1;
            else{
                unite(g[q[i].second], q[i].second);
            }
        }
        cout << ans << endl;
    }
}

『SOFT SKILLS ソフトウェア開発者の人生マニュアル』の各章を1行でまとめた

『SOFT SKILLS ソフトウェア開発者の人生マニュアル』の内容を各章ごとに1行で表した。
章を要約するつもりで書いたが、上手くできているかはわからない。

第1部

02. 自分自身はソフトウェアを作れる能力を提供する事業である
03. キャリアの目的を決めよう
04. 人との付き合い方は大切
05. 職を得るためには人脈も大切
06. 雇用形態を理解しよう
07. どの程度専門特化すれば有利になるか考えよう
08. 自分会う環境はどんな会社にあるだろう
09. 出世するには、責任、主張、勉強が大事
10. プロとして正しい習慣を身につけよう
11. 仕事をやめるなら十分な準備をしてからにしよう
12. フリーランスになるなら、準備をきちんとしよう
13. 必要とされている製品を開発しよう
14. スタートアップを起業するなら上手に支援してもらおう
15. 在宅勤務にも課題がある
16. わざと困難な環境に身を置き、技術を身につけよう
17. 履歴書にこだわろう
18. テクノロジーに対し宗教的な概念を持つのは無駄

第2部

19. 自分自身をマーケティングするために、何らかのブランドを作ろう
20. 自分を表す良いブランドを作ろう
21. ブログは様々な点で役にたつ
22. 他人に本物の価値を与えることは成功への近道である
23. ソーシャルメディアを活用しよう
24. 人前で話すことで様々なチャンスを作れる
25. 本や記事を書けば自分の評価を高められる
26. 勇気を出して挑戦しよう

第3部

27. 学び方を学ぼう
28. 身につけたいスキルのうち、本当に重要な20%を学ぶ
29. 勉強する前に計画を立てる
30. 学んだことを自由に実践し、誰かに教えよう
31. 師匠を見つけよう
32. 弟子をとろう
33. 教えることでより深く理解できる
34. 成功に学位は必要ないが、あれば選択肢が広がる
35. 知識の隙間を埋めよう

第4部

36. 集中すれば生産性が上がる
37. タスクをスケジューリングしよう
38. ポモドーロテクニックを使おう
39. ノルマを設定し、タスクを処理しよう
40. モチベーションを保てる環境を作ろう
41. マルチタスクに向いているタスクとそうでないタスクを分けよう
42. 燃え尽き症候群を乗り越えることでモチベーションと興味は再び湧いてくる
43. 時間を浪費するのは止めよう
44. 目標を達成するためのルーチンを毎日組み込もう
45. 良い習慣を身につけよう
46. タスクは細かく分解しよう
47. ハードワークは問答無用で手をつけよう
48. 行動しないことで人生に大きな影響を及ぼす

第5部

49. 広い視点を持って給料を運用しよう
50. 自分の価値を把握しよう
51. オプション取引の仕組みを知ろう
52. 不動産投資の方法を知ろう
53. 引退の計画を立てよう
54. 利益を生まない借金はやめよう
55. 早期引退はできるよ

第6部

56. 健康に気を配ろう
57. 健康に関する目標を立てよう
58. 消費、摂取カロリーを元に、体重を増減するための計画を立てよう
59. 健康へのモチベーションを高めよう
60. 筋トレの正しい知識を身につけよう
61. 体脂肪率に気を配ろう
62. ランニングのメリットはたくさんある
63. スケジュールやフィットネスプランを改善しよう
64. ガジェットを活用しよう

第7部

65. 思考は自分自身に強く影響を与える
66. プラス思考を身につけよう
67. 自己イメージを変えよう
68. 恋愛ゲーム戦略を考えよう
69. 優れた本を読もう
70. 失敗を恐れない
71. 他人が言ったことを鵜呑みにしてはいけない

書籍

ジョン・ソンメズ 『SOFT SKILLS ソフトウェア開発者の人生マニュアル』 長尾高弘訳、日経BP社、2016年

ネットワークインターフェイスの名前

MacBook Air でifconfigして表示されたネットワークインターフェイス一覧。

lo0
ループバックアドレス

gif0
トンネリングを行う

en0
Ethernet

en1
有線のEthernet

en1
Air Mac

stf0
IPv6パケットをIPv4ネットワークにルーティングする

p2p0
Air Dropの機能用

awdl0
Handoffの機能用

bridge0
仮想インターフェイスを外部ネットワークに接続する

vimで構文ハイライトをいじった

f:id:noy72:20170217200405p:plain
こんな感じに。

おしゃれしたい

競技プログラミングでよく使うマクロやデータ構造に色をつけたくなったので構文ハイライトをいじった。

これでforとrepが肩を並べるよう(同じ色)になり、デバッグ用のマクロが目立つようになった。
あと、色がついて気分が良くなる。正直、あまり意味はない。

構文ファイル

自分はデフォルトのカラースキームを利用している。
whichやls -lでvimフォルダを探し出し、その中のcpp.vimファイルを変更することでハイライトを変更できた。

syn keyword cppType vector map
syn keyword cppStatement rep range
syn keyword cppConstant INF
syn keyword cppRawStringDelimiter debug show

cppRawStringDelimiterが何を表しているかはわからないが、とにかく目立つ色なのでdebug用マクロに設定。
cppTypeだけ長くなったので省略。

無駄にカラフルになって読みにくくなりそうである。

sshでリモートマシンへログインする際にやったこと

ログインするだけなのに時間がかかった。
mac -> VMware CentOS7

yum install openssh-server
  • sshdサービスの起動
systemctl start sshd-service

ここでエラーが出て実行できなかった。SELinuxが原因な気がしたので、

setenforce permissive

で設定を変更した。
すると実行できた。

systemctl status sshd.service

で起動できているかを確認した。

その後sshで通信しようとするも、TLE。

firewall-cmd --list-all

これでファイアウォールsshを見逃してくれているかを確認。sshがservicesにあれば大丈夫っぽい。しかしログインできず。

自分はsshのポート番号を変更していたので、それもファイアウォールに示した。

firewall-cmd --permanent --add-port=<ポート番号>/tcp

その後、ログインできた。

とりあえずログインはできたので、次はセキュリティについて試す。

グラフ メモ

  • 連結

任意の2点間に辺がある。
連結グラフは、グラフ上の任意の2点間に辺があるグラフのこと。

  • 関節点

削除すると部分グラフが非連結になる点。

削除すると部分グラフが非連結になる辺。

  • 強連結

任意の2点間に有向路がある、という条件を満たしている有向グラフの頂点の部分集合を強連結であるという。

  • 強連結成分

強連結な集合Sに、どのような頂点集合を付け足しても強連結にならないとき、Sを強連結成分という。

典型探索問題を解く

問題の解法が浮かばないなら、とりあえず解法の全探索をすればいいと思った。

パラメータそれぞれに注目して解けるか考える。
DPなら、テーブルに何を持つかを全通り考えてみる。

AOJ ALDS1_4-D Search - Allocation

問題概要

数字がn個与えられる。それをk個のグループに分ける。
グループの数字の総和の最大値が最小となるように分ける。

なんか二分探索っぽいキーワードが。

制約

1 ≤ n ≤ 100,000
1 ≤ k ≤ 100,000
1 ≤ w_i ≤ 10,000

考え方
  • nに注目

i番目までの荷物をいれたときの最大値を求めていく、と考えて無理そうなので諦める。
これだと、どの数字をどのグループに入れたかも保持しないとできない。その上遷移もできなさそう。

  • kに注目

グループの数変えても仕方ない。

  • 総和の最大値に注目

総和の最大値がi以下のとき、グループにできる数字の個数、と考える。
iが大きければ、貪欲にグループを作れば良い。
→総和の最大値を全通り試してグループができるか調べればよい。
 →二分探索でいけそう。
  →できた。