グラフ系アルゴリズム：Union-Find 木

先日書いた記事の

katoufujibanana.hatenadiary.jp

にて、グラフ上のある２点が接続しているかどうかの判定アルゴリズムとして、Union-Find の名前を出しましたが、どのようなアルゴリズムだったかは触れなかったので今回は Union-Find を取り上げます。

まずは、Union-Find を使わず、深さ優先探索や幅優先探索で２点の接続判定を行う場合、最小計算量 、最悪計算量 になります。

Union-Find を使う場合、最小計算量 、最悪計算量 となります。さらに、Union-Find は接続判定を行えば行うほど、計算量 で計算できる点の組が増えていきます。すごい。

その代償として連結しているか否かの判定に特化するために、グラフ構造をすごい勢いで破壊していきます。元のグラフ構造に基づいた処理もしたい場合は Union-Find 用のデータと別にグラフを保持するデータを持っておくようにしてください。

以下スクリプトです。

class UnionFindTree:
    def __init__(self, n):
        self._n = n
        self.parent = [-1] * n

    def merge(self, a, b):
        x = self.leader(a)
        y = self.leader(b)

        if x == y:
            return x

        if -self.parent[x] < -self.parent[y]:
            x, y = y, x

        self.parent[x] += self.parent[y]
        self.parent[y] = x

        return x

    def same(self, a, b):
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        path = []
        for _ in range(self._n):
            parent = self.parent[a]
            if parent < 0:
                break
            path.append(a)
            a = parent

        for p in path:
            self.parent[p] = a

        return a

では、スクリプトを１行ずつ見ていきましょう。

class UnionFindTree:
    def __init__(self, n):
        self._n = n
        self.parent = [-1] * n

コンストラクタです。n はグラフのノード数です。

Union-find では、グラフの正確な構造は保持せず、あるノードが接続する親のノードのみ記憶します。これを記憶する配列が self.parent です。初期値は -1 であり、これはどのノードも親を持たないことを表します。

self.parent は、接続する親のノードだけでなく、自分が接続しているグラフのサイズも表現します。値が正の値である場合は自分の接続先の親ノード、負の値である場合は自分が接続しているグラフのサイズを表現します。後述の merge メソッドや、leader メソッドで self.parent を更新しますが、このルールが守られるように更新されていることに注意してください。

    def merge(self, a, b):
        x = self.leader(a)
        y = self.leader(b)

        if x == y:
            return x

        if -self.parent[x] < -self.parent[y]:
            x, y = y, x

        self.parent[x] += self.parent[y]
        self.parent[y] = x

        return x

merge メソッドの説明に入ります。leader メソッドの詳細は後に回しますが、とりあえず、「a からグラフを親方向に辿って行ったときの一番上のノード」を返すメソッドであると理解いただければ大丈夫です。

merge メソッドを実行するのは、ノード a とノード b の間に辺が追加されたときです。merge メソッドによって Union-find のデータ構造を更新します。

        if x == y:
            return x

すでに、a と b が同じ leader を持つ場合、データ構造は更新しません。

        if -self.parent[x] < -self.parent[y]:
            x, y = y, x

        self.parent[x] += self.parent[y]
        self.parent[y] = x

そうでない場合、「x のサイズに、y のサイズを可算」し、「y の親を x」にします。

前段の処理として、サイズが大きい方にサイズが小さい方を接続するようにすると、leader メソッドの計算量が抑えられるので、お互いのサイズを比較して大きい方に接続できるように必要に応じて x と y を入れ替えておきます。

    def same(self, a, b):
        return self.leader(a) == self.leader(b)

same メソッドは、a と b が接続しているか否かを判定します。

    def leader(self, a):
        path = []
        for _ in range(self._n):
            parent = self.parent[a]
            if parent < 0:
                break
            path.append(a)
            a = parent

        for p in path:
            self.parent[p] = a

        return a

leader メソッドです。

    def leader(self, a):
        path = []
        for _ in range(self._n):
            parent = self.parent[a]
            if parent < 0:
                break
            path.append(a)
            a = parent

この for ループで、a を起点として親方向にノードを辿っていき、parent の値が負になったとき、つまり一番上のノードにたどり着いた際に break し、ループを抜け出します。値の更新の流れから、ループを抜け出したときの a が一番上のノードを表します。

ループの中で、path という配列に、辿っていくノードを保存しています。

        for p in path:
            self.parent[p] = a

        return a

一番上のノードが確定した後は、path に格納されているノード（つまり、今までに辿ってきたノード）のすべての親を、一番上のノードに設定しなおします。
この工夫により、一番上のノードとの距離の小さくなるノードが増えてゆき、leader メソッドの計算量をどんどん抑えていくことができるようになっています。

具体的に計算量がどれくらい抑えられているのかは、またいつか別の記事で。

グラフ+bitDP：巡回セールスマン問題

今回は巡回セールスマン問題（Traveling Salesman Problem: TSP）のコードを書きます。グラフ上のすべてのノードをめぐる最小距離を求める問題です。どちらかというとグラフの探索アルゴリズムというよりかは、DP 的側面の強いアルゴリズムという印象。

素朴に書こうとすると、ノード数を としたとき、

1. グラフ上のすべての２点間の最短距離を求める（素朴に書くと の計算量）

2. 巡回する順序を全パターン総当たりする（ の計算量）

総和としては、 の計算量となります。

今回ご紹介するスクリプトを使用すると、計算量は になります。まあまあましになりますね。 を自然数としたとき、 で の方が小さくなります。

こちらが出発点は０番ノード固定、かつ出発点に戻ってくる必要のない場合の巡回セールスマン問題を解くスクリプトです。出発点が０番ノード以外であったり、出発点に戻ってくる必要がある場合はスクリプトを改変すれば対応できるので、臨機応変にお使いください。

import math

class TravelingSalesman:

    def __init__(self, costs):
        self.costs = costs
        self.n = len(costs)
        self.s = 2 ** self.n

    def solve(self):
        dp = [[math.inf for _ in range(self.n) ] for _ in range(self.s)]

        dp[1][0] = 0

        for s in range(1, self.s):
            for u in range(self.n):
                u_bit = 2 ** u 
                if s & u_bit == u_bit:
                    for v in range(self.n):
                        s2 = s | 2 ** v
                        dp[s2][v] = min(dp[s2][v], dp[s][u] + self.costs[u][v])

        return min(dp[self.s - 1])

使い方は以下のようになるかと思います。

n = int(input())
m = int(input())

costs = [[math.inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    ai, bi, ci = map(int, input().split())
    costs[ai][bi] = ci
    costs[bi][ai] = ci
tsp = TravelingSalesman(costs)
print(tsp.solve())

以下スクリプトの解説です。

import math

TravelingSalesman クラスの solve メソッド内で、DP テーブルを math.inf で初期化したかったがための import です。解く DP によっては初期値が math.inf でないこともあるので、適宜書き換えてください。

class TravelingSalesman:

    def __init__(self, costs):
        self.costs = costs
        self.n = len(costs)
        self.s = 2 ** self.n

コンストラクタです。使い方にもある通り、引数には重み付きグラフの行列表現を渡してください。渡されたグラフの配列長（= グラフのノード数）と、それを２の指数に持ってきたものを格納しておきます。役割は後続のステップにて。

    def solve(self):
        dp = [[math.inf for _ in range(self.n) ] for _ in range(self.s)]

        dp[1][0] = 0

        for s in range(1, self.s):
            for u in range(self.n):
                u_bit = 2 ** u 
                if s & u_bit == u_bit:
                    for v in range(self.n):
                        s2 = s | 2 ** v
                        dp[s2][v] = min(dp[s2][v], dp[s][u] + self.costs[u][v])

        return min(dp[self.s - 1])

巡回セールスマン問題を解くメソッドです。細かく分解してみていきましょう。

        dp = [[math.inf for _ in range(self.n) ] for _ in range(self.s)]

DP テーブルを初期化します。
テーブルサイズは、グラフのノード数を として です。
１次元目（ の方）は、今までに到達したノードを表現します。ノードが 個ある場合、そのうちどれに到達したかは boolean を 個保持すればよいので、 で表現可能です。
２次元目（ の方）は、今どのノードにいるかを表現します。ノードが 個なので、 で表現可能です。

        dp[1][0] = 0

DP テーブルに開始点の情報を入力します。
０番ノードから開始するため、に累計コスト を設定します。

        for s in range(1, self.s):
            for u in range(self.n):
                u_bit = 2 ** u 
                if s & u_bit == u_bit:
                    for v in range(self.n):
                        s2 = s | 2 ** v
                        dp[s2][v] = min(dp[s2][v], dp[s][u] + self.costs[u][v])

DP の遷移です。配る DP を行います。テーブルを辿っていく順番は、
,
,
,

,
,
,

,


です。

                u_bit = 2 ** u 
                if s & u_bit == u_bit:

と の組み合わせによってはありえない組み合わせがあることもあるので、そこを省略します。例えば は、１次元目が「１番のノードにのみ到達済み」と言っているのに２次元目が「今０番ノードにいる」と言っており不整合が起きています。そのような DP テーブル内の値からの遷移は考えないものとします。

                    for v in range(self.n):
                        s2 = s | 2 ** v
                        dp[s2][v] = min(dp[s2][v], dp[s][u] + self.costs[u][v])

が次に移動する先のノード番号、 は 到達後の到達済みノードの集合のバイナリ表現です。もし、到達済みノード の状態で から に移動した結果の総コストが、今 に格納されている値より小さかった場合、 を更新します。

        return min(dp[self.s - 1])

self.s - 1 の値は です。そして、 に格納されている値は、「全ノード到達済みで、現在 番目のノードにいるときの最小総コスト」です。
そのため、この式で返される値は、全ノードを辿る場合の最小総コストとなります。

ゲーム理論：フォーク定理

今日はゲーム理論に関する記事を書きます。表題の通りフォーク定理（folk theorem）に関する記事です。１回の記事だと紙面が足りなくなるので何回かに分ける予定です。

戦略形ゲームにおいてすべてのプレイヤーが戦略を（自分一人だけ）変えるインセンティブを持たない戦略の組であったり、進化ゲームにおける安定的な状態の戦略の組であったりするナッシュ均衡解について、一般にパレート最適は保証されないことが知られています。

「しょうがないね、だってナッシュ均衡なんだもん」

と割り切ってもよいのですが、やはりより好ましい選択肢があるのならそちらを取りたくなるのが人情というもの。 さらに、実社会ではナッシュ均衡解とパレート最適解が一致しないようなゲームに近似できる条件下で、ナッシュ均衡解ではなくパレート最適解の方が実現する場合があることも観察されていました。

フォーク定理はプレイヤーの合理性に制限を加えることなく、この現象を説明することができます。 *1

フォーク定理が要請する条件は以下の２つです。

• ゲームが無限回繰り返し構造を持つこと

• 将来利得の割引率が十分に大きいこと、ないしは存在しない（= 常に１）であること

この条件下では、

• トリガー戦略は、無限回繰り返しゲームのナッシュ均衡解かつパレート最適解となり、

• Fudenberg と Maskin が提示した戦略（https://www.jstor.org/stable/1911307）は、無限回繰り返しゲームの部分ゲーム完全ナッシュ均衡解かつパレート最適解

となります。

プレイヤー同士がお互いトリガー戦略を採用したり、Fudenberg と Maskin の戦略を使用した場合、均衡パス上で実現されるひとつひとつのゲームの結果は、そのゲームのナッシュ均衡解以外の解になることができます。

ここからは、一番簡単な

• 将来利得の割引率が存在しない（= 常に１）場合の

• トリガー戦略

が、無限回繰り返しゲームのナッシュ均衡解かつパレート最適解となることを示します。

まずは繰り返されるひとつひとつのゲームについて、
プレイヤー の戦略の集合を とおきます。
戦略自体は小文字で と表すことにします。

各プレイヤーの戦略で構成されるベクトルは

と表記します。
略記表現として、プレイヤー 以外のプレイヤーの戦略で構成されるベクトルを

と表記することとします。

プレイヤー の利得関数は となります。プレイヤー の戦略と、それ以外の戦略ベクトルに着目して という書き方も許容することします。
利得関数の値域は と書くことにします。

プレイヤー が最適応答をした際の の利得 を最小化させる を と書くことにします。
定義より明らかに となります。

この最小化されたプレイヤー の利得を と書くこととして、

と書くこととします。

次に、無限回繰り返しゲームの利得の評価について、 回目のゲームの利得を と書くことにします。
プレイヤー の利得を評価するにあたって素直に利得の総和 で評価しようとすると値が発散してしまう場合があるので、平均利得 で評価することにします。

各プレイヤーの無限回繰り返しゲームの平均利得のベクトルを、

とすると、このとき の集合内でパレート最適であり、 をパレート支配するような が存在します。これを と書くことにします。

トリガー戦略を以下のように定義します。

1. ゲーム開始時点からは、 を実現するような戦略を全プレイヤーは選択する。
2. から逸脱する戦略をプレイヤー が選択した場合、次回以降 以外のプレイヤーは を選択し続ける。

ちなみに同時に2名以上のプレイヤーが から逸脱した場合は、1. を続行します。

誰も逸脱しない場合のプレイヤー の無限回繰り返しゲームの平均利得は となります。

次に、プレイヤー が逸脱する場合、逸脱した回で多くの利得を得られはしますが、ゲームを無限に繰り返す場合は高々有限回数の利得が平均利得に与える影響は０となるため、プレイヤー の無限回繰り返しゲームの平均利得は となります。

は をパレート支配するので、明らかに です。プレイヤー は を逸脱するインセンティブを持ちません。

以上より、割引率が存在しない（= 常に１）場合のトリガー戦略が無限回繰り返しゲームのナッシュ均衡解かつパレート最適解となることが示されました。

*1:逆にプレイヤーの合理性に制限を加えるアプローチによってこの現象を説明する方法もあります。

AtCoder Beginner Contest 201

Mynavi Programming Contest 2021（AtCoder Beginner Contest 201） - AtCoder

たびたび参加はしていましたが、リアタイ更新は約一年ぶり。

結果：4AC（1WA）
1020 位。

問題 A

ソートして条件満たすかどうか見て Yes か No 吐いて終わり。

問題 B

ソートして２番目の要素アクセスして終わり。sort 関数に渡す key を自前で用意する必要がある。

問題 C

なんとなーく、o の個数や ? の個数から解析解がありそうな気がしたけれども、「この程度の個数だったら全探索してもよいのでは...？」という悪魔のささやきに唆され、o と ? の数字だけ使ったパスワードを全部生成して、o の数字がすべて入っているかを判定して突破。

解説見たら 0000 から 9999 全探索してましたね。

問題D

色々悩みましたが、木とみて DFS でもよいですし、dp テーブル出現させてゴール側から埋めていくでもよいですけれども、
「右（下）に行ったら勝てる or 負ける　→　だから右（下）に行こう」をゴール側からぱたぱたやっていく問題でした。

一回目の提出の際、間違えて自分の得点を最大化するように動かしてしまったので WA いただきました。
しかも状態を自分の得点と相手の得点を保持させることになっていたので、計算量も増加したのか一部のテストケースにて TLE。

マスの移動含めて勝ち負けを判定するには、得点差だけ格納しておけばよいので、コード書き換えて AC。

問題E

は がすべて求まっていたらすぐ出せるなー、 全部埋めるのは BFS 使って で出せるなーくらいまでは分かりましたが、
愚直に出そうとすると計算量 行っちゃうんですけど...？　となってそのまま時間切れ。

解説みました。うぇーん、鮮やか...。

問題F

見てない。

感想

bit 演算はスニペット用意してどうこうするタイプの対策にはならないので、bit 演算絡みで成り立つ諸性質のお勉強ですね...。

グラフ探索アルゴリズム：深さ優先探索の行きがけと帰りがけ

グラフを探索するアルゴリズム、深さ優先探索。英語でいうと Depth-first Search (DFS)。深さ優先探索にはタイトルの通り、行きがけと帰りがけのバリエーションがあります。

前回の記事では Python の deque クラスを使用した、深さ優先探索と幅優先探索の実装を公開しました。 前回の実装は行きがけのスクリプトとなります。

今回は行きがけの深さ優先探索と、帰りがけの深さ優先探索を表現するスクリプトをご用意いたしました。

引き続き自分にとっての備忘のためと、「競技プログラミング始めたよ！」という人のため、アルゴリズムを実装した Python スクリプトと、簡単な解説を公開します。

import sys
sys.setrecursionlimit(1000000)


def dfs(n, graph, reached):
    for i, e in enumerate(graph[n]):
        if e == None or reached[i]:
            continue
        reached[i] = True
        dfs(i, graph, reached)


def main():
    graph = [[None] * n for _ in range(n)]
    reached = [False for _ in range(n)]
    reached[0] = True

    dfs(0, graph, reached)

今回のスクリプトでは、関数の再帰呼び出しを使います。

一行ずつスクリプトを追っていきましょう。

import sys
sys.setrecursionlimit(1000000)

Python の sys モジュールをインポートし、setrecursionlimit メソッドを実行します。
Python は関数の再帰呼び出しを行う際、呼び出せる回数に制限がかけられています。この制限を設定できるのが、sys.setrecursionlimit メソッドです。
setrecursionlimit の引数には、呼び出せる回数の上限を渡してください。問題にもよりますが、 もあれば十分です。*1

def main():
    graph = [[None] * n for _ in range(n)]
    reached = [False for _ in range(n)]
    reached[0] = True

    dfs(0, graph, reached)

先に、main 関数を見ます。
二次元リスト表現の graph と到達済みノードの格納リストを宣言し、探索開始ノード（ここでは 0 番ノード）の到達済みフラグを立てています。 最後に dfs 関数を呼び出し、探索を開始します。

def main():
    graph = [[None] * n for _ in range(n)]
ココ>>>>
    reached = [False for _ in range(n)]
    reached[0] = True
ココ>>>>

    dfs(0, graph, reached)

グラフの初期化を行うのは、この２か所のどちらかになると思います。

def dfs(n, graph, reached):
    for i, e in enumerate(graph[n]):
        if e == None or reached[i]:
            continue
        reached[i] = True
        dfs(i, graph, reached)

最後に dfs 関数です。n は現在見ているノードの番号です。graph と reached はそれぞれ main 関数から呼び出す際に渡した、グラフと到達済みノードを表すリストです。
前回と同じように、まずは他のノードへの辺が存在するどうか、そして辺が存在するならば到達済みか未到達かを評価します。
辺が存在しない、もしくは到達済みの場合は無視（continue）します。未到達の場合はそのノードを到達済みにし、第一引数をそのノードの番号にして再帰的に dfs 関数を呼び出します。

def dfs(n, graph, reached):
ココ>>>>
    for i, e in enumerate(graph[n]):
        if e == None or reached[i]:
            continue
        reached[i] = True
        dfs(i, graph, reached)

行きがけに探索する場合は、ここに処理を入れてください。

def dfs(n, graph, reached):
    for i, e in enumerate(graph[n]):
        if e == None or reached[i]:
            continue
        reached[i] = True
        dfs(i, graph, reached)
ココ>>>>

帰りがけの場合は、ここに処理を入れてください。

以上、行きがけの深さ優先探索と、帰りがけの深さ優先探索の Python スクリプトとその解説でした。

*1:ノードの個数、つまり n あれば十分です。気持ちそれより多めに、2 * n とかでよいかもしれません。

グラフ探索アルゴリズム：深さ優先探索と幅優先探索

グラフを探索するアルゴリズム、深さ優先探索と幅優先探索。
英語でいうと Depth-first Search (DFS)、Breadth-first Search (BFS)。

競技プログラミング頻出のアルゴリズム（基礎レベル？）ですが、知らないと自力でひらめくのは難しいはず。いわゆる”知識”として押さえておきたいアルゴリズムの一つ。

自分にとっての備忘のためと、「競技プログラミング始めたよ！」という人のため、アルゴリズムを実装した Python スクリプトと、簡単な解説を公開します。

from collections import deque

graph = [[None] * n for _ in range(n)]
reached = [False for _ in range(n)]

d = deque()
d.append(0)
reached[0] = True

for _ in range(n):
    v = d.pop()
    for i, e in enumerate(graph[v]):
        if e == None or reached[i]:
            continue
        reached[i] = True
        d.append(i)
    if not d:
        break

こちらが深さ優先探索のスクリプトです。

    v = d.pop()

を

    v = d.popleft()

にすると、幅優先探索になります。

グラフの初期化処理は割愛しています。
もし入れるとしたら変数の宣言箇所から考えてこの辺りになります。

graph = [[None] * n for _ in range(n)]
reached = [False for _ in range(n)]

    <<<<ココ

d = deque()
d.append(0)

適宜問題に合わせて柔軟に書き換えてください。

このままだと本当にグラフの各ノードを辿るだけで終わってしまいます。競技プログラミングで求められる「グラフを辿りながら、何かを数えたり、何かを更新したりする」場合は

    for i, e in enumerate(graph[v]):
        if e == None or reached[i]:
            continue
ココ>>>>
        reached[i] = True

reaced[i] = True の一行上に、for ループ直下のスコープで処理を入れてください。*1 *2

一行ずつスクリプトを追っていってみましょう。

from collections import deque

Python の deque クラスをインポートします。
以下は公式ドキュメントからの引用です。重要なのは太字にした箇所です。

Deque とは、スタックとキューを一般化したものです (この名前は「デック」と発音され、これは「double-ended queue」の省略形です)。Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。

list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。

graph = [[None] * n for _ in range(n)]
reached = [False for _ in range(n)]

グラフ構造を表現する二次元リストと、到達済みノードを表現する一次元リストを宣言します。graph を list の dict*3 や set の dict*4 にしてもよいですし、reached を set にしても動きますが、体感的に TLE になることが多いです。原因は謎です。

d = deque()

deque をインスタンス化します。

d.append(0)
reached[0] = True

探索を開始するノード（に該当するインデックス番号）を deque に追加し、到達済みであることを示すフラグを立てます。

for _ in range(n):
    v = d.pop()
    for i, e in enumerate(graph[v]):
        if e == None or reached[i]:
            continue
        reached[i] = True
        d.append(i)

深さ優先探索の場合、deque の末尾に追加されているノードを調べます。幅優先探索の場合は deque の先頭のノードを調べます。
deque から取り出したノードについて、そのノードから他のノードへの辺が存在するどうか、そして辺が存在するならば到達済みか未到達かを評価します。
辺が存在しない、もしくは到達済みの場合は無視（continue）します。未到達の場合はそのノードを到達済みにし deque の末尾に追加します。

    if not d:
        break

deque の中に要素がなくなったら、探索を終了します。グラフが連結である場合、すべてのノードを探索できているはずです。逆にこれを用いてグラフが連結かどうかを判定することも可能ですが、Union-find を使った方がよい場合が多い感じがします。

以上、DFS と BFS の Python スクリプトとその解説でした。

（追記）続きました。

katoufujibanana.hatenadiary.jp

*1:中の if reached[i]: 下のスコープではないことに注意！

*2:問題によってはここ以外に処理を入れることもあるので、そこは臨機応変に。

*3:{[k: [] for k in range(n)]}

*4:{[k: set() for k in range(n)]}

1x Engineer

何かの折で見かけたこちらのページなのですが、探してみると和訳がなかったので和訳することにしました。

一見、平凡なエンジニアであることの自虐であるかのように見えますが、実態は、本文中でも言及されている 10x Engineer に対するアンチテーゼ、そしてそれを吹聴する人々への反発です。

1x.engineer

今でも更新が続けられているようで、以下の和訳はコミットハッシュ 71821ac の断面になります。また日が開いて本家が更新されたら、和訳も更新しなおしましょうかね。

以下和訳です。もし間違えていても、責任は負いかねます。ごめんね。
原文英文を引用符でくくって、その下に和訳を書いていきます。

---

What is a 1x Engineer? You might have already heard of a 10x engineer. Probably too often, actually. If there's such a thing as a 10x engineer, surely there must be a 1x engineer, too?

Of course there is! Let's dig into a non-exhaustive list of what qualities make up a 1x engineer.

1x Engineer とは何でしょうか？　10x Engineer でしたらあなたも耳にしたことがあるかもしれません。実際のところ、頻繁に耳にしたことがあるかもしれません。もし、10x Engineer なんてものがあるとするならば、きっと 1x Engineer も存在するはずじゃないでしょうか。

その通り。存在します！　どんな性質が 1x Engineer を作り上げているのか、その一例を掘り下げていきましょう。

A 1x Engineer...

1x Engineer は...

Searches Google, Duckduckgo, Bing, or wherever they like when they're not sure what's up.

何が起きているかわからないとき、Google や DuckDuckGo、Bing、その他自分の好きな検索エンジンで検索します。

Copy/pastes code snippets from Stack Overflow, Glitch, Codepen, or wherever they find answers.

Stack Overflow、Glitch、Codepen、そのほか、解答を見つけた場所がどこであれ、そこにあったコードスニペットをコピペします。

Gives credit where credit is due.

認めるべき功績を認めます。

Creates community and shares knowledge.

コミュニティを作り、知識を共有します。

Spends time on things outside of engineering, like hobbies, friends, and family.

エンジニアリング以外の物事（趣味や友人、家族といった）にも時間をかけます。

Has a schedule that allows them to maintain a healthy work-life balance, and respects others' time-boundaries, too.

予定を守ることで健康的なワークライフバランスを保つことができ、同様に他人の時間的な制約も尊重します。

Isn't measured by arbitrary contribution scores on any website, and doesn't judge others for theirs either.

あらゆる web サイトのどんな貢献度スコアによっても測られることはなく、またそれによって他人を判断することもありません。

Writes code that — gasp — has bugs.

バグがあるコードを書きます。

Writes code that others can read.

他人が読めるコードを書きます。

Reads the Docs.

ドキュメントを読みます。

Updates the Docs.

ドキュメントを更新します。

Doesn't need to be passionate about the code they write or the problems they solve, but may be.

自分の書くコードや、取り組んでいる問題に熱心になる必要はありません。しかしながら、熱心になることもあります。

Doesn't act surprised when someone doesn’t know something.

誰かが何かについて知らなくても、驚くことはありません。

Is willing and able to collaborate with others.

他人と協力することができ、そうする意思もあります。

Publicly celebrates others for their wins.

他人の成功を公的に称賛することができます。

Ask questions before providing critical feedback.

批判的なフィードバックをする前には、いくつかの質問をします。

Gives tough feedback privately.

厳しいフィードバックは、他の人に見えないように行います。

Treats others how they would like to be treated.

自分がして欲しいように、他人に接します。

Provides code reviews and feedback to their peers that are constructive, helpful, and presented tactfully, helping their peers to grow personally and professionally.

建設的かつ有用かつ巧妙な表現で、同僚が個人的にそして職業的に成長するのを手助けできるような、コードレビューとフィードバックを行います。

Expresses appreciation for code reviews and feedback from their peers that are constructive and helpful.

同僚からの、建設的で有用なコードレビューとフィードバックに感謝します。

Sometimes feels hurt by critical feedback, but doesn't react destructively.

ときには、批判的なフィードバックには傷つくこともあります。しかし破壊的な反応はしません。

Sometimes takes short breaks to clear their head.

頭を整理するために、短い休憩を取ることがあります。

Makes mistakes from time to time, and finds growth in those mistakes.

何度も何度も失敗をします。が、その失敗の中から成長していることが見て取れます。

Willing to admit when they're wrong, and aren't afraid to say "I don't know."

自身の過ちを認めることができ、「わかりません」ということを恐れません。

May or may not like writing documentation, but does it anyway for future maintainers.

資料を書くのが好きでも好きではなくても、未来にメンテナンスをする人のためにそれを書きます。

May or may not like writing tests, but tries to learn to do so if the team or project needs it.

テストを書くのが好きでも好きでなくても、チームやプロジェクトでそれが必要ならば、それができるように努力します。

Thanks others for their time, effort, and energy.

他人の時間、努力、気力や行動力に感謝します。

Can have colorful desktop backgrounds.

デスクトップの背景をカラフルにすることができます。

Supports code in production, even if they did not write it.

たとえ自分が書いたものでなくても、本番稼働しているコードを保守します。

Can feel like an imposter at times, and understands others may, too.

時には、自分が詐欺師であるかのように感じてしまうことがあります。他人もそうであることを理解しています。

Believes that everyone in the room is equally as smart and capable as they are.

同じ部屋にいるみんなが、同じくらい賢く能力のある人だと信じています。

Will help level-up others, and asks for help when they need it.

他人の能力向上を手伝うことができるし、必要なときは、他人に助けを求めることができます。

Never stops learning, but can feel totally overwhelmed by the amount of learning there is to do.

学びを決して止めません。しかし、学ばねばならばい事柄の総量に完全に圧倒されてしまうこともあります。

Tries to keep discussions productive and lets others have their say before the team makes a decision.

ディスカッションが生産的なものであるように努め、チームが決定をする前には他人の意見を聞きます。

Is willing to leave their comfort zone.

自分の殻を破る意思があります。

Contributes to the community in their own way when possible, and appreciates the ways that others contribute when they can.

自分の方法でできる限りコミュニティに貢献し、そして、他人の貢献の仕方の良さも認めます。

Can be a slow coder.

遅いコーダーかもしれません。

Has productive and unproductive days.

生産的な日とそうでない日があります。

Doesn't take themselves too seriously.

あまり深刻に考えすぎません。

Says, "I've never heard of that," in lieu of nodding and pretending.

頷いたり、分かったふりをしたりする代わりに、「それは聞いたことがないです」と言います。

Is trustworthy.

信頼に値します。

Works to live, rather than living to work.

働くために生きるというよりも、生きるために働いています。

Sometimes loses their work.

ときには、職を失います。

Doesn't have to have the entire codebase memorized.

全てのソースコードを覚える必要はありません。

Respects and upholds community Codes of Conduct.

コミュニティの行動規範に敬意を表し、支持します。

May work from home, the office, a coffee shop, or where ever else best works for them.

家、オフィス、コーヒショップ、その他もっともよく仕事ができる場所で仕事をします。

Doesn't hate on tools, processes, or languages that they'd rather not use, or that others are using.

自分が使いたくなかったり、他人が使っているツールやプロセス、言語を嫌いません。

Is not defined by the computer they're using.

使っているコンピュータによって定義されません。

May decorate their laptop and workspace in any way they like, and is respectful of others' decor (or lack thereof), too.

ラップトップや仕事場を、自分の好きなように飾り立てても構いません。同様に他人の飾り付け(や、逆に飾りがないこと)を尊重します。

Isn't defined by myopic Tweetstorms by clueless VCs.

無知な VC*1 達よる、近視眼的な Twitter の流行りによって定義されません。

Doesn't riddicule entire professions within engineering, especially not when in a position of leadership.

エンジニアリングに関わる全ての職業を馬鹿にしません。特にリーダーシップを発揮すべきポジションに就いているときは。

Notice something missing from the list? 1x engineers are often humble and willing to accept Pull Requests to fix mistakes. If you feel like you've got something that's missing from the list, feel free to open a Pull Request against the website's repo.

リストに不足しているものに気が付きましたか？　1x Engineer は多くの場合、謙虚なので、誤りを修正するためのプルリクエストを受け入れるつもりです。
もしリストに足りないものがあると感じたら、webサイトのリポジトリに遠慮せずプルリクエストを送ってください。

---

以上、1x Engineer でした。
GitHub の URL はこちら。 github.com

*1:何の略称か確証が得られていないですが、おそらく Venture Capital ？