日本語 | 英語 | 学んだこと |
n頂点の木 | a tree with N nodes | withですね |
高さlog n | a height of log N | ofですね |
木の高さはn | a tree has a height of N | |
どんな頂点から根にもlog nで行ける | You need to visit at most log N nodes to reach root node from any other node | any otherのあとは基本単数。log N nodesのように数を前置してもよい。nodeはvisitするもの。たどり着くにはreachを使う。 |
根 | root node | rootじゃだめ?→いいらしい |
いろんなクエリがO(log n)になる。 | Many queries can be done with O(log n) complexity | queryはdoするもの。processとかじゃあだめ?complexityはO(log n) complexityのように前置できる。complexityにはtheはいらない |
いろんな操作がlog nでできる | We can do a lot of operations with O(log n) complexity | |
ある頂点からある頂点まで移動する距離が最悪O(n)オーダーになっちゃう | In the worst case, we have to visit O(N) nodes to move from one node to another node. | |
頂点Aから頂点Bへのパスに載った頂点の値を全て計算せよ | calculate the sum of all node values on the path from A to B | all node valuesにtheがつかないのなんで…?pathにはonするもの。node A, node Bとは余り言わないみたい。 |
AとDの距離はN/2 | We need to visit N/2 nodes to travel from A to D | travel A to Dだったり、reach D from Aだったりまあいろいろパターンがあるね |
あるノードからあるノードへ移動するのには、最悪O(N)かかってしまう | Moving from one node to another node is up to O(N) complexity | いま、ノードがどこなのかについては確定していないので、theはつかないっぽい。moving is complexityなの面白くないですか、moving takes complexityではないらしい。あと、最悪計算量をup to O(N)みたいに言うことがあるみたい。 |
この木を、3つの列に分解する | We break the tree into 3 chains. | break intoか…decomposeとはいわない?? |
この木は、N/3の長さの3つの列に分解されました | the tree is decomposed into 3 chains each of size N/3 | decomposedとも言うらしい。というか、3 chains each of size N/3って一体なんですか。google 翻訳的にはOKらしいけど |
頂点Aと頂点Bは同じ列にある | A and B belong to the same chain | belong to the same hogeは汎用性ありそう |
BからDのパスはBからT3とT4からDに分解される | Path from B to D can be broken as B to T3 and T4 to D | 長ったらしくなる時はfromを省略してもいいらしい。多分the path from A to Cがめんどくなって、A to Cになったのだと思う。broken asとは…? |
BからT3までの総和も、T4からDまでの総和も、log nで計算できる | We can calculate the required sum in O(log n) for B to T3 and O(log n) time for T4 to D | めんどくなったら、forで主題を限定してしまえ。the sum for the pathのように。あと、O(log n)計算量で、の別の言い方として、in O(log n) timeというのもあり |
競プロ勢は「log」が好き | Competitive programmers always love the log factors | logとかexpみたいなやつはfactorと呼ばれるらしい…?? |
どの頂点もただひとつの列にのみ含まれる | No two chains has a node in common | えぇ… |
どの頂点から根までのパスも、それを分解して、複数の列のどれかに含まれるように分解することができる | THe path from any node to the root node can be broken into pieces such that the each piece belongs to only one chain. | decompose A into Bs, such that B is ...という形式は結構汎用性がありそう。固定を表す英語表現。 |
クエリはO(log n)で可能。 | queries can be answered with O(log n) complexity | queryとanswerの相性が良いらしい |
ある頂点の子の中で、最も部分木のサイズがでかいものを特別な子と呼ぶ。 | Among all child node of a node, the one with the maximum sub-tree size is considered as Special Child. | the oneのようにして一つを限定することができる。maximumにはその後に何がmaximumなのかを説明することができる。部分木はsub-treeだし、部分木のサイズはsub-tree size |
葉ではない頂点は全て唯一の特別な子を持つ | Each non leaf node has exactly 1 special child. | eachは視点の固定のためによく使われるっぽい。葉ではない頂点をnon leaf nodeと呼ぶのは面白い。唯一の、と言った時にuniqueと言うよりexactly 1と言ったほうがカジュアルで読みやすいね。 |
頂点Aと頂点Bのエッジ | The edge connecting A with B | |
全頂点に関して、特別な辺をその頂点とその頂点の特別な子をつなぐ辺とする。 | For each non-leaf nodes, the edge connecting the node and its Special Child is considered as Special Edge. | For each non-leaf nodes、などfor each結構使いやすいね。そういえば、「〜とする」をis consideredと呼ぶの結構わかりやすい。 |
その辺は2つの列をつなぐ | The edge will be the connector between chains | connectorはbetween. Edgeはconnect A and Bだったりconnector between A and Bでよく使うらしい。 |
今このような遷移で得られたものは、根から始まる列となる | What you just traveled is a chain which starts from the root node | どうやらアルゴリズムが動くのではなくて、自分が動いているらしい。 |
根にはm個の子があるとしよう | Let us assume that the root node | root nodeという単語、何故か無冠詞になっているけど、Wikipediaを見る限りはa root nodeとかthe root nodeとか言わなければいけないらしい。やはり固有な感じなので、the root nodeと呼ぶのが普通みたい |
サイクルを持たないグラフ | a graph without having any cycle | anyなあ… |
他のm-1個の子は、別の列の開始点となっている | Other m-1 child nodes | starting nodesという表現が開始点を表すらしい。便利そう。というか、子はやっぱりchildrenとは言わなくて、child nodesなんだなあ |
ある頂点の普通の子の部分木のサイズは、元の部分木のサイズの1/2以下になっている。 | When you move from a node to any of its normal child, the sub-tree size is at most half the sub-tree size of the current node | moveというと、その後の脳内の頂点が一個動いているみたい。theと言った時のノードが変わる。あと、halfの使い方がすごい巧妙なのでちゃんと習得したい。あと、moveはfrom toで移動の前後を表せる。プログラムポインタのyou。any of its hogeは結構便利っぽい。sub-treeはsub-treeであってsubtreeではない。half the sizeとか、直接くっつけることができるの面白い。3 chains each of sizeみたいに、sizeがなんか前置詞っぽく働いてるの面白い。 |
考えられるなかで最小の特別な子の部分木サイズは? | What is the least sub-tree size possible for special children? | 考えられる中で、というのはpossibleを使って表現する。また、possible forで〜考えられるうち…みたいな感じになる |
| | |
| | |
| | |
| | |