くれなゐの雑記

例を上げて 自分で手を動かして学習できる入門記事を多めに書いています

Beginners CTF 2019 writeup

はじめてCTFにチームとして参加しました!!!!!

R19 というチームで参加してました! kurenaifと申します

常設じゃないCTFはやるのは初めてです!

知り合いにpwnをひたすら布教されていたので、CTFはpwnだと思っていたのですが、実はCryptoもあり、それが面白そうだったのでチームメイトに俺はCryptoをやるぞーーーー!!!と言ってCryptoだけやりました。

pwnもやってみたのですが、すべてを忘却していたため頑張って思い出そうと思います。

[Crypto] [warmup] So Tired

so_tired.tar.gz が渡されました中身は encrypted.txt だったのですがこれがとても長い… なんか最後の方に == とかついてますし、 base64 encode らしさがありますね というわけで

$ cat encrypted.txt | tr -d '\n' | base64 -d  > src

out を見てみると、よくわからないバイナリですね… よくわからないバイナリはとりあえず file を見てみましょう

$ file src
out: zlib compressed data

どうやらzlibだそうです!

#!/usr/bin/python3
# a.py
import zlib

f = open("src", "rb")
data = f.read()
f.close()

dc = zlib.decompress(data)
f = open("out", "wb")
f.write(dc)
f.close()

outを見てみると…

$ cat encrypted.txt | wc -c
373728
$ file out 
out: ASCII text, with very long lines, with no line terminators
$ cat out | wc -c
370052

あっ…(察し)

また base64 してみると、どうやらこれも zlib みたいです。 base64zlib をひたすらぐるぐるさせたのが、この暗号みたいですね。

それではさっきのPythonと組み合わせて

# a.sh
while true
do
cp out out.bak
cat out | tr -d "\n" | base64 -d > src
python3 a.py
wc -c out
done

これでエラーが出るまで待ち続けましょう!

base64: invalid input
Traceback (most recent call last):
  File "a.py", line 8, in <module>
    dc = zlib.decompress(data)
zlib.error: Error -3 while decompressing data: incorrect header check
37 out

エラーが出ました! いい文字数ですね!

$ cat out
ctf4b{very_l0ng_l0ng_BASE64_3nc0ding}

[Crypto] Party

どうやら、3組のpair、すなわち合計6つの数字が与えられるみたいですね。

  • coeffx
  • 出力された数字を y
  • partyr

とおくと、以下の式が成り立っていることがわかります!



\begin{bmatrix}
r_0^0 & r_0^1 & r_0^2 \\\ 
r_1^0 & r_1^1 & r_1^2 \\\
r_2^0 & r_2^1 & r_2^2
\end{bmatrix}

\begin{bmatrix}
x_0 \\\ 
x_1 \\\
x_2
\end{bmatrix}

=

\begin{bmatrix}
y_0 \\\ 
y_1 \\\
y_2
\end{bmatrix}

 x_0 がフラグですね

行列の形がわかれば、あとは行列を斜めにするやつをやるだけです! 少数型に落とすと情報が欠けそうで怖かったので、有理数クラスを使って解いてます。

#!/usr/bin/python3

import numpy as np
from fractions import Fraction
from Crypto.Util.number import long_to_bytes

def f(x, coeff):
    y = 0
    for i in range(len(coeff)):
        y += coeff[i] * pow(x, i)
    return y

def solve(mat):
    for row in range(len(mat)):
        tar = mat[row][row]
        for col in range(len(mat[row])):
            mat[row][col] /= tar
        for r in range(len(mat)):
            if r == row:
                continue
            boost = mat[r][row]
            for c in range(len(mat[r])):
                mat[r][c] -= mat[row][c] * boost
    return mat

N = 512
M = 3

r = [0]*3
y = [0]*3

file = open("src", "r")

for i in range(3):
    r[i] = Fraction(int(file.readline()))
    y[i] = Fraction(int(file.readline()))

mat = [
    [Fraction(1), Fraction(r[0]), Fraction(r[0]*r[0]), y[0]],
    [Fraction(1), Fraction(r[1]), Fraction(r[1]*r[1]), y[1]],
    [Fraction(1), Fraction(r[2]), Fraction(r[2]*r[2]), y[2]],
]

print(solve(mat))
for i in range(len(mat)):
    for j in range(len(mat[i])):
        print(mat[i][j], end=" ")
    print()

print(long_to_bytes(mat[0][-1]))

しっかり単位行列になってフラグが取れました!

1 0 0 175721217420600153444809007773872697631803507409137493048703574941320093728 
0 1 0 6759741750199108721817212574266152064959437506612887142001761070682826541920627672362291016337903640265385249474489124882116454124173716091800442011015857 
0 0 1 8559415203809303629563171044315478022492879973152936590413420646926860552595649298493153041683835412421908115002277197166850496088216040975415228249635834 
b'ctf4b{just_d0ing_sh4mir}  

Go RSA

RSA暗号d と encryptされたデータは教えてくれますが、 N をなくしてしまったみたいです!!!!!

Nないのにお前どうやって暗号化してんだよ!!!!

この問題、2つ気づくことに気づけばなんと瞬殺できます

  • まず一つ、数字が入力できること
  • そして、その数字に負の数が入ること

ガチャガチャ遊んでいたら、負の数を入ることを発見してしまいました。 -1 が通るならもう自明です。

RSA暗号の暗号化は

c = m^e MOD N

復号は

m = c^d MOD N

ですね。 このNがわからないので、復号できないという問題でした。

この問題では、フラグの c の他に、3回まで好きな整数の m を入力することができます。

では、 m-1 を入れたら…?

通常eは65537とか3とかです。

m = -1^e MOD N = -1 MOD N = N-1

なんと N-1 をもらえました!!!

これを +1 して、複合してやると…

from Crypto.Util.number import long_to_bytes

a = 19721739460005715839687258097463606567568088122562143766673559079928993888011218840527723736945976855276429750686840511245308087039361625859575588315010586932109088534073184785632230817871748507755371081564038161176335857405579592850018586825018841366905735384823298027525055483718836334184117597308146143832746609071410404320299844124897769731428479677374581456236061208983710496710928583658704287830103346312036579012291640838414960806920681837417786550306083430969817954317601886422446799325599439885265181833346633337600066770273573882073976043621513973625591205643086917193039382944499499255990087899534083558712
n = a + 1
d = 16012534574459681485963634139862001145411989213568735706066294645804685807634846967717788543366836663962557081706478331993745344148366136283532609515693857534590486442567835507091820407552582660881197653556068092746906439239029795613811114691641020613919176733171071476305533169723408153840900277253517317842880767356950185288540335520596457402867899206001172130409041175548610181861286325063434009922901699522599455879079648553315178156923597492552797606051253955520510125897947319770306996525090494984301910656673155680183032096435051027220919313430919758310229110059410508088941767032227875386851849410203872128257

x = 4166307417617957284869321340663074830305356736973969287118610781379422763896670624160917668898929485302592913693740635487274812853279249498082813735026859474333821827825022846601676094308501172617202223248824318344700000867606631910692133738577886686239665573753583206491647139406448572619516253202158832537788022928614879944248391229292623896316715442295616471480180228286163207028450461678895309475635821698950149318482145068775702644341882119883921129616029519739738868428874523531712307489141815448685352233906955519708655061860955347613402457489376739490167812575480528575373033977959010646084855165180428882395
print(long_to_bytes(pow(x,d,n)))

いえい!

b'ctf4b{f1nd_7he_p4ramet3rs}'

これ、あってんのか?と思ってましたがどうやら想定解放で、周りを眺めていたら少数派っぽいです…

別解(天才解法)

qiita.com

zeosutt.hatenablog.com

[crypto] bit_flip

元の数字があり、 nc でつなぐたびに、下1/4くらいのランダムな1bitを変えて、暗号化した数字を返してくれます。 難しいです。 これはRSAなのですが、

Nec はわかるのですが、dを教えてくれません。ただの公開鍵の情報です

もしこれで復号できたら、RSA暗号を解読したことになります。まともに解いてられません。

考察1 e が小さい

eが3なので、ワンチャン 3乗した結果が N より小さければ 3乗根を求めるだけで解けます。

... 無理でした

考察2 1bitしか変わっていない

もとの数字を x として、i bit目が変わったとすると


(x + 2^i)^3 \mathrm{or} (x - 2^i)^3

が大量に渡されるので、なんとかして連立方程式を解けないかと考えました

...無理でした

実はできた

qiita.com

考察3 Flanklin-Reiter Related Message Attack

RSAの暗号の脆弱性を調べていると見つけました。

2つのメッセージ m1m2 の差がわかれば解けるという問題です。

1024/4 = 256 bitのうち、1bit変えただけなので、差のパターン数は 256^2 そんなに多くありません。

差は、 xor をとっているので

abs((1 << i) - (1 << j)) or (1 << i) + (1 << j)

の2択です。

2つの差分がわかれば、あとはその全てに対して複合するだけです。

ももいろテクノロジー様のソースコードを使わせていただいて、

inaz2.hatenablog.com

以下のようになりました

# coppersmiths_short_pad_attack.sage

# reference: http://inaz2.hatenablog.com/entry/2016/01/20/022936
import sys


# reference: http://inaz2.hatenablog.com/entry/2016/01/20/022936
def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1
    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()

    kbits = n.nbits()//(18)
    print(h.small_roots(X=2^kbits, beta=0.5))
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]  # find root < 2^kbits with factor >= n^0.5

    return diff

# reference: http://inaz2.hatenablog.com/entry/2016/01/20/022936
def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]

if __name__ == '__main__':
    n = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331
    e = 3

    c1 = 38448272237964375371726759592758385386616013779162822338653392077256549091123869239648616008586564655973797454298230191967696840378043670012083704181791314856097307077627229165947387478341901251979390480932220983592258282304304001581658323909165412718287474168394422138841873902714319309538983680281287491186
    c2 = 51531223430957857733934880383408638185102108212202467189651292360878470909281785640325226719442938173566544600753270928156891865771525435019551126712738055654692625329783768014054928002128679874456939510971058344318886221948942145053253549048822643888005377157270281027834500602254102431820137131985798724504

    for bit1 in range(1024//4):
        for bit2 in range(bit1):
            sys.stderr.write(str(bit1) + "," + str(bit2) + "\n")
            a = (1<<bit1)
            b = (1<<bit2)
            for diff in [(a+b), (a-b), -(b-a)]:
                # print bit1, bit2
                # print "difference of two messages is %d" % diff

                m1 = int(related_message_attack(c1, c2, diff, e, n))
                m2 = m1 + diff

                pos = []
                i = 0
                while i < 1025: 
                    bm1 = ((m1 >> i) & 1)
                    bm2 = ((m2 >> i) & 1)
                    if bm1 != bm2:
                        pos.append(i)
                    i += 1
                
                if len(pos) != 2:
                    continue

                print(m1)
                print(m1 ^^ (1 << pos[0]))
                print(m1 ^^ (1 << pos[1]))
                print(m1 ^^ (1 << pos[1]) ^^ (1 << pos[0]))

あとは出てきた数字をすべてbyte文字列に戻すと…?

見つかりました!

f:id:kurenaif:20190528005152p:plain

[misc] Dump

休憩時間にときました。 いっぱいパケットがありますが、 wireshark の機能を使えば実はhtmlだけ取り出せます!

`File>Export Objects>HTTP...>Packet 3193`

hexdumpの8進数なので、 あとはこれをdecodeするだけですね

import struct

file = open("src", "r")

lines = file.readlines()

nums = []
for line in lines:
    nums += list(map(lambda x: int(x, 8), line.split()))

with open("out", "wb") as fout:
    for x in nums:
        print(x)
        fout.write(struct.pack("B", x))

[misc] Sliding puzzle

幅優先探索で出来るくらいの計算量ですが、ちょっと書くのが辛かったので先人のコードをお借りしました。

host = '133.242.50.201'
port = 24912
bufsize = 4096

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect((host, port))

while True:
    a = sock.recv(bufsize).decode()
    print(a)
    rows = a.split('\n')[1:4]

    rows = list(map(lambda x:x.split('|')[1:-1], rows))
    for i in range(len(rows)):
        for j in range(len(rows[i])):
            rows[i][j] = int(rows[i][j])
    ans = checkio(rows)
    res = ",".join(ans)
    sock.send(res.encode())

所感

Crypto たのしい!!!!!!! pwnwebreversingは完全に人に任せていたので、反省です。 今度反省会をするので、そのときにコツを教えてもらいます!

新卒就活体験記

会社名に関しては隠したり隠さなかったりしているが今回は念の為隠す方針にする。 もし興味がある人は直接聞いてほしい。

全体

基本的には逆求人(アカリク、Gスタイラス)を通じて会社の人事さんとつながってそこから選考~という感じ。 特に下調べはせずに、人事さんやあったエンジニアさんの話、会社の雰囲気を中心に就活を始めた。 検討した会社は逆求人等で会った会社は多分20社くらいで検討した会社は7社くらい。 自分のキャパやスケジュール調整能力的に7社が限界だったけど本当はもっといろんな会社を見たかった B3くらから動けばよかったとちょっと後悔。 2月から7月間で長い間研究と並行で進めた。 基本的にいっぱい受けて受かった企業から選ぶつもりだった。

全体の面接対策等

逆求人ベースなので、逆求人で説明するために資料を用意してそれをベースに話した。 情報系以外の人でもわかるような話と、短時間では情報系の人にしか伝えられないような深い内容の話の2通りがあり、前者を優先すると後者があまり満足せず、後者を優先すると前者が満足しない。 自分は両方を満たすことが出なかったので、技術的な話を優先して話した。

自己アピールのトピックとしては、

  • 中学生からプログラミングをしており、当時は簡単なものしか作れなかったが一応ロボカップジュニアで全国大会に行ったこと
  • 高専時代で作ったゲーム用のライブラリの話
  • 高専時代の卒論(ロボットの歩行アルゴリズム)の話
  • 高専時代は一応複数人での開発を経験しているよという話
  • 大学で成績が良かったよいう話
  • 大学では競技プログラミングちょっとやってて一応青コーダーだよという話
  • 競技プログラミングだと何故かペアプロが得意だよという話
  • 大学院の研究室ではサーバー管理等やっているよという話
  • 大学院の研究では先生のコードがバグってるので大量に直したよという話
  • イラストレーターとも交流があって50人規模の企画を動かしてたよという話

があり、これをさっと流しながら面接官のリアクション等を見ながら雑談をした。 大体「いろいろやってるね」というリアクションが帰ってくる。

面接中にも情報を色々仕入れた。 20社以上に今会社の困っていることを聞くと、結構似たようなことに困っていることに気づいた。 それに対する解決法等も色々で面白かった。

競技プログラミングを長くやっているので、競技プログラミング中心で話をした。

それぞれの会社

A社とかC社とかD社とかG社とかF社とか書いてるけど実際に受けた企業の頭文字とは関係ないよ

A社

プログラミングテストがあったので、気軽に受けてみたら通ってしまった。 面接に関して良くない噂が流れていたが、ゲーム会社だけあってやはりゲーム(ライブラリ自作)の話がずいぶん盛り上がった。

B社

最終面接で落ちた。 最終面接までは楽しく技術面接等をしてきたが、最後の面接で僕のできること/やりたいことと会社でやることが微妙にマッチしていないことに気づく。 社員がとにかく忙しそうだった。 忙しいと思って働きたくないので、ちょっとそれもミスマッチだった。 英語が喋れなさすぎた。

C社

逆求人の人におすすめされたので、受けてみた。 会社の作っている製品や、やっている内容にとても興味があったが、業績がちょっと不安だったのと知り合いからの評判がイマイチだったのでお断りしてしまった。

D社

遊びにおいでよ!と言われて遊びに行ったら面接だった。 準備してなくてコミュ症が発動してしまい1次で落ちてしまった。

E社

ここに受かればここに行っていた。みんなも知ってるあの会社。 面接で前泊をさせてくれたが、現地に行ったら3万の激ヤバホテルでびっくりした。 めったに落ちないと言われる最終選考で落ちてしまい、正直受かったと思っていたのでかなり大きなショックを受けた。 ちょっと英語が喋れた。

F社

ここに受かればここに行っていた第2社。 E社の選考待ちで精神不安定状態になり、簡単なはずの面接で力が出ずに落ちた。 英語が喋れなかった。 メンタルを鍛えたい。

G社

インターンに行った会社。 受けてないけど考えてはいたので一応。 低レイヤ系はめちゃめちゃ消耗するので、体が耐えきれないと思って後回ししていて、そのまま終わってしまった…。 ごめんなさい…

H社

最終的にここにした。 自分と似たスキルを持つ人が多く感じており、楽しく働いていそうだった。

おわりに

Atcoderをやっていたおかげで、某社を除いた会社でコーディングテストに困ることはなかった。 ただ、青コーダーなので、自分より上のレートの人は世の中にいっぱいいる。 「うちの会社にはもっと上のレートの人もいますけど」みたいな返しをしてくる会社も当然いる。 トップクラスならいいけど、中の上くらいであれば他にも武器は持っておいたほうがいい。

「〜できますか?」という曖昧な質問がよくあるが、この質問に対する答えは相対的なもので決まる。 入門書を読んで、簡単なものを作った程度の人でもやっていない人に比べればそれはできることになる。 入門書レベルから趣味で普段から使っているレベル、業務レベル、研究レベル等色々なレベルがあるが、何がどれくらいできて何ができないのか 相手の企業の事業内容やリアクションを見ながら武器をたくさん見せたほうが良いと感じた。 入門書レベルでも、自力で興味を持って勉強をすることはかなり大きな価値があると思う。

大学の成績は一社で提出させられたけど、それ以外はまったく役に立っている感じはなかった。 趣味の開発もいいけど大学で真面目に勉強した分評価される世の中になってほしい。

合同誌主催を振り返って 〜花札合同運営の裏方〜

記事のモチベーション

おそらくこのタイトルでこのブログに到達する人ははじめましてだと思います。

合同誌を主催したり、競技プログラミングの問題を解いているkurenaif(f.くれなゐ)と申します。 この記事では二度合同誌を主催し、この機会を通じて様々な反省があったので自身の今後の様々な活動や、また他の合同誌主催をしたいと思っている方の参考に少しでもなればと思い、筆を取りました。

普段はこんなブログを書いています。もし興味があれば覗いてみてください。 かなり難しい問題を解説していると思います。

kurenaif.hatenablog.com

自己紹介・主催した合同誌の概要

自分が主催した合同誌は 東方花札風イラスト合同 〜幻想二十四の花かるた〜東方花札合同 百華蒐集 です。

前者の合同は両面ポストカードサイズ12枚のもので、各月に対して両面2人ずつ、その月のテーマの札をデザインしていただく合同で、後者の合同は名刺サイズ48枚で花札の各札に対して1枚ずつ割り当てて札をデザインしていただくといった合同になっています。

実はここだけの話なのですが、花札合同第1段の企画をした次点で第2段の予定は少し立てていました。(一定以上部数売れたり、満足する完成度のものができれば第2段をするつもりでした)

他の一般的な合同誌と違い、以下の点で大きく異なっていると思います。

  • 一人でも人数の過不足が合ってはならない。
  • 本ではないので、パッケージング等は自力で行わなければならない。
  • 本ではないので、編集は意外と楽
  • 全員同じテーマでイラストを書くわけではない

総じて、合同主催の負担としては編集は楽ですがその他でそれ相応の負担を被ることになります。 なので、私の主催した合同ではそのあたりの工夫が必要になってきますね。

合同誌主催として、最低限気をつけなければならないこと

これに関しては既存の記事が非常に優秀なので、私から言うことは特にありません。 特に、以下の記事が参考になりました。 自分から強調して言いたいことは

  • 合同参加者の工数もかなり多く取りますし、お金に関してはよく相談しましょう。
  • 人の募集から頒布まで、予算や期間についてきっちり目処を立ててから募集をかけよう。

の二点ですね。

www.clipstudio.net

blog.kasei-san.com

合同誌主催として次点で気をつけなければならないこと・心がけ

最低限のことを気をつけた上で、次点で気をつけなければならない点を紹介します。 必ずしも守らなくていいとは思いますが、気をつけるとスムーズにことが進むと思います。

文章は「短く・端的に」を 意識しすぎてはいけない

文章はよく「短く・端的に」とよく言うと思います。 間違ってはいませんし、重要なことだと思います。 特にtwitterのDMのようなインターフェイスでは特に短く書こうと努力すると思います。 しかしながら、私のように普段文章を書かない人は文章の推敲の際に短く書こうとしすぎて、必要な情報を削りすぎてしまう場合があります。 二度合同誌をした経験から、私のような素人が無理に短く書くよりも、長くても良いのでわかりやすいと思う文章のほうがミスが少なく、また質問も少なかったです。

「わかりやすさ」と「短さ」というのはトレードオフの関係にあると思います。悩んだ場合は「わかりやすさ」を優先しましょう。 大丈夫。 合同誌参加者は長くてもちゃんと読んでくれます。

25人規模を超える場合twitterのDMを過信しない

多くの参加者はtwitterのDMでの連絡を取りたい方が多いと思います。 自分も過去そう思い、二度の合同でそのようにしました。 しかしながら、大人数の合同では

twitterのDMはAPIがキツすぎる問題」

が発生します。「API」とはtwitterの機能を使う窓口みたいなものなのですが、あることをすれば窓口がスパム扱いするのです。 例えば、同じメッセージを何度も送るとスパム扱いだったり、一気にDMを送るとスパム扱いだったり… 体感25人あたりから""""キツい""""です…

大人数の場合はメールでの連絡を推奨しましょう

文章は5%前後くらいの確率で誤解されてると思え

この5%はあくまで僕の文章力です。人によって違うと思います。 このブログみたいな文章力だと5%くらいの人が誤読するってことですね。 合同誌を主催すると、自分がどれだけ物事を正確に伝える力があるのか定量的に測れてとてもいいです。 かなり貴重な経験ですね。

誤読・誤解・勘違いをしたまま進行することを防ぐために工夫をするのも合同誌主催の仕事です。 最低限、わかっていてほしいことは参加者自身の手で二重確認させるように設計しましょう。

余裕があればメッセージを共有する前に参加者に確認してもらうといいですね。

参加者自身のチェック: 募集のチェックの例

以下は募集の際に設けたチェックボックスです。 要項にも書いているのですが、募集の際に最も重要な「金銭面・誤解されやすい点・締め切り」をこのような形で二重チェックさせています。

f:id:kurenaif:20190102214319p:plain

参加者自身のチェック: 配置のチェックの例

配置ミスはこの合同で最も気をつけなければならない点です。 スプレッドシートを用いて参加者全員の配置をお互い確認できるようにし、 また確認した配置を自らDMで復唱していただくことで、さらなるミスを防止しています。

そのようなDMが来ない場合はリプライとかで促します。 ここは妥協すると本当にめんどくさくなるので最大限注意しました。

あとがきと原稿の提出は同時にお願いしよう

タイトル通りです。 「あとがきは後でもいい」スタイルは絶対忘れます。 これは先人の知恵でもあり僕もやったら忘れました。 ごめんなさい。

提出要項ウェブページを作ろう

最終的にウェブサーバーを借りて合同誌の宣伝をするのですから、早い間にウェブサーバーを借りて参加者のためのページを作っちゃいましょう。 以下が自分の作ったページの例ですね。

ここを見ると合同の提出に関するすべてが細かな注意点を含めて書いてあります。 質問等もここにまとめておき、主催や参加者の質問をする手間を減らします。

大きな手間ではありません。 メールやDMなどで内容を書くよりも、以下のメリットがあります。

  • twitterが凍結等されてもウェブページさえあれば原稿の提出方法の確認ができる
  • 太字や色を使うことができるのでDMよりも見やすい
  • 画像等を使った丁寧な説明ができる
  • リンクを貼ることができる(twitterDMではかなり制限されます)
  • テンプレートをサーバー上に置くことでいつでもダウンロードすることができる
  • twitterのDMと違い、重要性の低い内容を送信するリスクが少ない(メールやDMではどうでもいい情報のせいで重要な情報が流れてしまいます)

あとは「内容を更新したのでウェブページ見てね」とDMで告知したら終わりです。 参加者的にも主催者的にもいいですね。

f:id:kurenaif:20190102215425p:plain

f:id:kurenaif:20190102220757p:plain

メッセージの書き方

基本的に論文書くときと同じ心得だと思っています。誰しもが読んで誤解のない文章を書くべきです。 以下の本がおすすめです。あまり内容は数学的ではないので、是非読んでみてください。

メッセージのスタイル

メッセージはtwitterDM、pixivメッセ、メールで以下のスタイルで書きました。

(伝えたい内容の概要)
締め切りまであとN日になりました。hogehogeについて、以下2点確認をよろしくお願いします。

(伝えたい内容の箇条書き)
1. XXXXについて
2. YYYYについて

1. XXXXについて
(XXXXについての詳細)
(やってほしい理由)

2. YYYYについて
(YYYYについての詳細)
(やってほしい理由)

以上2点、よろしくお願いします。

僕の場合文章が長くなりがちなので、構造的に内容をわけられるよう考慮した結果がこうなりました。 このスタイルの書き方の利点としては、以下の4点があります。

  1. 詳細や理由を添えることで、誤読や勘違いを減らす
  2. 内容が箇条書きで書かれており、メッセージの概要がひと目でわかる。
  3. 番号をつけることで、内容の参照が可能になる
  4. 伝えたい内容の個数がわかるので、理解した内容の確認が容易になる
1. 詳細や理由を添えることで、誤読や勘違いを減らす

書いてあるとおり、作業内容を書くだけではなく、や「なぜそれが必要なのか」を付け加えます。

ただただ「端的に短く」やってほしいことを書いてもらってもいいのですが、「なぜそうしなければならないか」という「冗長性」を付け加えることで、誤読のリスクを減らす役割があります。

これがあるのとないのでは体感で相当な誤読が減りました。

2. 内容が箇条書きで書かれており、メッセージの概要がひと目でわかる。

1.で詳細や理由を付け加えたことにより、文章が長くなってしまいました。この冗長性は必要なもので削ってはいけないものです。 でも、長い文章はやはり短く書かれたものよりも読みにくいです。

なので、内容を端的に短く書いた目次のようなものを追加しましょう。それが

1. XXXXについて
2. YYYYについて

この両方を書き、番号でお互いにリンクさせることで短い箇条書きの文章と長い文章の利点の両立を図っています。

3. 番号をつけることで、内容の参照が可能になる

あえて難しい言葉で書いてみました。 2.で目次を作りましたが、例えば「3番がわかりにくいなぁ」と思ったら「3番の詳細(今読んでいるこれ)」を読めばよいのです。

これが3番の伝えたい内容です。過去の文章で

1.で詳細や理由を付け加えたことにより

であったり

2.で目次を作りましたが

みたいに番号で他の内容を参照することができます。これが「・」の箇条書きではなく番号の箇条書きを使う理由の一つです。

4. 伝えたい内容の個数がわかるので、理解した内容の確認が容易になる

文章を読み終わった後、最後に自分の理解した内容を再確認します。 そのときに数がわかると便利です。

ここまでの内容を読んだあなたは最後に

1. 詳細や理由を添えることで、誤読や勘違いを減らす
2. 内容が箇条書きで書かれており、メッセージの概要がひと目でわかる。
3. 番号をつけることで、内容の参照が可能になる
4. 伝えたい内容の個数がわかるので、理解した内容の確認が容易になる

の4点が理解できたことを確認するのではないでしょうか? 3点しか理解してなかったらそれは理解が不足しているということです。

最後に

以上N点、よろしくお願いします。

のように書き加えることで、何点相手に理解してほしいかを強調する文章を書いています。

まとめ

これがこのスタイルの文章の書き方の利点です。 大学のサークルや合同誌等の連絡で色々試行錯誤した結果これが一番誤解が少なかったっぽかったので私はこのスタイルを採用しています。

おわりに

1回目の反省点を活かし2回目では様々な工夫をしてかなりの誤読や誤解を減らせたと思います。 この記事ではその中でも特に効果が合ったと思う部分を紹介させていただいています。

今回の合同では誤読しても問題ない部分では少しだけトラブルが起き、問題がある部分は全くトラブル等は起きなくスムーズに進行できたと自負しています。

しかし、まだまだトラブルが全く起きなかったわけではないので軽微なミスも0にするようマネジメントを模索していきたいと思います。 こういう知見を集めるために合同誌主催が集まるオフ会みたいなの企画してみたいですね。

使用例とともに学ぶvimコマンド5選

問題

この記事は多分kosen10sアドベントカレンダーの15日目の記事です。

adventar.org

vimを勉強するモチベーション

今様々な便利な便利なIDEやエディタが登場しており、わざわざvimを使う必要はないのでは?という気持ちになります。 実際、vimで快適にコーディングする環境を整えることは比較的難しく、また機能を追加すればするほど起動が重くなりトレードオフを取るのがなかなか難しいです。

しかしながら、様々なIDEやエディタが登場したがゆえ、環境によってそれぞれのエディタのショートカットキーを覚えなければならないという難点もあります。

そのような背景の中、vimキーバインドは多くのエディタの拡張機能として実装されており、統一されたキーバインドとして勉強するのもありかな?と思っています。 少なくとも、emacsが入っていないサーバー環境等ではどうしてもvimは避けられないですしね

vimを学習するときの壁(この記事について)

おそらく今の多くのコーディング初心者は、マウスでカーソルを合わせ、マウスホイールでスクロールし、入力するような形態を取っていることが多いと思います。

そのような状態からvimを入門した後、"移動"と"挿入モード等の切り替え"、"保存終了"を勉強し終わったあとに、次にどうすればいいのかわからないという気持ちになると思います。この記事はその後の勉強について、少しでもその壁を突破する手助けになればと思います。

この記事の対象

  • vimは何をするものかを知っている
  • 挿入モード、ノーマルモードを知っている
  • vimを起動し、文字を入力し、保存終了ができる
    • 上記を満たさなくても、動画をみてvimでこういうことができるのかと思っていただく読み方は可能です。

vimのコマンド紹介

この記事では大文字と小文字を区別します。注意してください。

  • 大文字はshiftを押しながらの入力を表します。
  • c-hogehogectrl を押しながらhogehogeを入力することを示します。

o/O

oノーマルモードで入力すると、以下の処理を一気に行ってくれます。

  1. 行末に移動する($コマンド相当)
  2. 挿入モードに移行する(aコマンド相当)
  3. 改行を行う

これらの処理を行った後、その行と次の行の間に一行空行が生まれることになります。

f:id:kurenaif:20181222195923g:plain

また、oコマンドは下に空行を作るのに対し、Oコマンドは上に空行を作ります。

このコマンドは意外と酷使します。一例をいかに示します。次はOコマンドを使う例です。

f:id:kurenaif:20181222200019g:plain

この記事中にもこのコマンドは大量に現れるので、しっかり頭に入れましょう。

i/a

この記事の冒頭で述べた条件に入っているコマンドです。 え?なんで知っている内容をわざわざ説明するの?と思われるかもしれませんが、結構このコマンド奥が深いです。

多くのvimmerやemacserは方向キーの入力を嫌います。 方向キーは多くのキーボードでホームポジションから遠くにあるので入力が遅くなる原因になるためですね。(マウスも同様の理由で嫌われています。) emacserは方向キーを捨てる代わりに、ctrlキーを多用する道を選びましたが、vimmerノーマルモードを導入する道を選びました。

おそらくご存知の通り、ノーマルモードでブロックが表示されると思いますが、そのブロックの左側に文字を入力するのがi、右に入力するのがaです

では挿入モードからノーマルモードに移行し、iで左側に文字を挿入するとどうなるでしょうか? それを利用したのがこちらの動画です。この動画のように入力することで、方向キーなしで左に1文字移動することができました。

f:id:kurenaif:20181222200056g:plain

また、vimではコマンドの前に数字を入力すると、そのコマンドを数字回実行してくれます。

例えば、一行削除するddコマンドの前に3をつけ3ddのように入力すると今あるカーソルを含めて下向きに3行削除してくれます。

ではaの前に数字を入力したらどうなるでしょうか?正解はその文字が複数回入力されます この動画をご覧ください。

f:id:kurenaif:20181222200126g:plain

使用用途としては、以下の動画のようにハイフンで線を書く場合に使えます。 動画では

50a-<esc><esc>

と入力することでハイフンの線を作っています。 さらに、yyコマンドで一行コピー(ヤンク)し、ペーストコマンドであるpを三回行うことを意味する

3p

を入力することで、さらに3つ複製しています。

他にもこういう使い方ができます:

競技プログラミングではint型に入る大きな素数として、1e9+7がよく使われています。 しかしながら、1e9+7という数字はc++などの言語ではdouble型として入力されるので、本来は1000000007のように入力したいです。

先ほど紹介したaコマンド、そしてこの動画で使用している数字を1インクリメントするctrl+aコマンドを使用することで、動画のようにこの数字を作ることができます!

f:id:kurenaif:20181222200157g:plain

f/F/;

かなりvim特有のコマンドに思えます。 f[x]コマンドはそのカーソルより右にある、最初にヒットした[x]に移動してくれます。 [x]の内容は記号数字アルファベット(大文字小文字区別)なんでもいいのですが、1文字に限定されます。

右にヒットするのがf、左にヒットするのがFです。

例えば、スネークケースのように単語が_で区切られているような場合は、f_で次々右に飛ぶことが可能です。 また、f_f_f_f_と入力するのはつらいので、二度目の入力以降はf_;;;;のように;が以前のfの移動を繰り返してくれます。

f:id:kurenaif:20181222200224g:plain

スネークケースの他にも飛びたい文字の近くに特殊な文字があればfで一気に飛べば方向キーを連打する回数も減らせるでしょう。 forの不等号の向きを変更する動画を以下に示します。 動画内で出てくるxはいまカーソルにある文字を1文字消すコマンドです。

f:id:kurenaif:20181222200248g:plain

ctrl+o

前ジャンプしたところに戻る機能です。何回もctrl+oを入力すると、更に前へ戻ることができます。

例えば以下の動画のように、includeを追加して戻ってきたいときのように使えます。 ggはファイルの最初の行に移動するコマンドですね。

includeを追加したときに最初に紹介したoコマンドも使用していますね。 octrl+oは全然別物なので、注意しましょう。

f:id:kurenaif:20181222200312g:plain

q/@

複雑な編集をするときに手放せないコマンド q です。 excelのマクロ機能のような機能で、q[x]<様々なコマンド>qと入力すると、[x]<様々なコマンド>が保存されます。 そして保存した<様々なコマンド>@[x]のようにして使用します。

本当にいろいろな使い方があるのですが、一例を紹介します。

以下の動画は、resがバグっているのでそれぞれの項をcoutしたいときの例です。a

次に現れる+<< '+' <<に変更する

処理を仕込んでおり、@aを繰り返し呼ぶことですべての+を置換しています。 (この処理は文字の置換でも可能です。)

f:id:kurenaif:20181222200405g:plain

次はスネークケースをキャメルケースに変更するケースです。 マクロには

次に現れる_を削除し、カーソル上にある文字を大文字に変更する

という内容が入っています。 マクロも他のコマンドと同様に、前に数字を入れると何度も繰り返し適応することができます。

f:id:kurenaif:20181222200508g:plain

まとめ

ただの紹介では他の記事と同じになってしまうので、 いくつか酷使しているvimキーバインドを、その使用例とともに紹介しました。 かなり汎用性の高いコマンドばかりですので、他にもいろいろな使い方ができます。 慣れてきたら新しいコマンドを見つけて、そのコマンドが使えるタイミングを探しながらコーディングしてみましょう。 oコマンドを知る前は$a<enter>を入力していたので、だいぶ入力が高速化されました。

ACM-ICPC 2018 Asia Yokohama Regional 参加記

ACM-ICPC 2018 Asia Yokohama Regional に参加してきました。 神戸大学で、getting_over_32というチームでした。 チームメイトは私kurenaifとcormoranさん、takeoさんです。

チーム名の由来としては、Asiaに生きたいねということで予選で確実に突破できる32位を通過したいという気持ちと、私が当時getting_over_it with bennett foddyにハマっていたのでそれらを連結させました。 今年でAsiaは初参加です。

1日目

同期は早生まれの人でない限りいないはずなので、ぼっちだろうなぁと思っていたらコーチでdrafearさんとか大阪大学の友人とか、あとはスタッフ側できゅうりさんなどに会った。久々に会ったのでテンションが上った。

1日目はリハーサルということでA-Dまでの、本戦とは関係ない問題を解く。 最近記憶がすぐ無くなる傾向があり、問題は忘れてしまったがDが制限付きで最小全域木を構成する問題だった気がする。 右前にいたチームがすぐ通していてやばかった。

ctrlとcapsを入れ替えたかったが、コマンドをメモしておらずかつ忘れるという悲しい事件があったので、そこでかなりの時間を食った。 特にtakeoさんにlinuxコマンドの使い方をなれてもらいたく、この日は長く使ってもらえるように指示した。

その夜、中華街でTikeさんが予約をとってくれた店で10名今日でご飯を食べた。 ご飯でNimが始まりかけたのが面白かった(やりがちらしい)

2日目

いよいよ本戦。 開幕は準備: cormoranさん、A:coromoranさん(with takeoさん)、B:私、C:takeoさん(with coromoranさん(?))みたいな感じで動いた。 Bを読んでいたら知らん間にAが通っていたので、Bを実装した。

B問題

Bはざっくり、数列が与えられるので、そのうちから任意の N 個を取り出し、等差数列を作る問題で、 Nを最大化させる問題だった。 結論から言うと、N^2 logN は実装によりけりで、N^2は確実に通るみたいな問題で、油断してN^2 log Nを実装していたらTLEを吐いてしまった。

log Nの部分はmapでかかるのだが、ココをlower_boundにすることでAC


そのあと、残りの問題を読んでいたらC問題がACしていたので、Standingsを見つつ、D,G,Kに注目する流れに D問題はパット見た感じ、なんか見たことあるなぁという気持ちになった(実際見たことあった)のだが、すぐ解法を思いつかないのでとりあえずパス。 G問題がよく解かれていたので、G問題を考察

G問題

バブルソートの交換回数を求めるのだが、あるindexまでは昇順ソート、あるindexまでは降順ソートみたいな感じで山形のソートを行う問題。山の頂上の位置はどこでも良くて、最小となるような位置で答えを求める。

問題を見たときに、とりあえず転倒数は必要そうだったので、転倒数は merge_sort を使う方法と BIT を使う方法があることをチームメイトに伝え、今回の問題はさらに中に入っている数字が大きくないのでBITが適切な可能性が高いことも共有しておいた。

最初は、山の頂上に位置するindexを決めたら答えが求まるかなと思ったが、その情報自体は余り大事ではないらしく考察が進まなかった。 こういう問題の基本は、「わかりそうなものから順番に決めていく」という感じなので、バブルソートらしく小さい順に値を見ていくことにした。 すると、実験をしていくと小さい数字は右と左のうち、近い方によっていくことが判明した。 この時点で、priority_queueを使った実装を思いつくが、もう少し軽そうなので議論を進めた。 takeoさんが、「今注目している数字より大きな数字がある分だけ移動する」という確信めいたことをつぶやいてくれたので、考察を整理した。 これらを組み合わせると、それぞれのindexについて、「その数字より左にあるその数字大きなものの数」と「その数字より右にあるその数字より大きなものの数」のうち、小さな方を、すべてのindexについて足していくと良いことがわかる。

これはBITを使うと楽なので、BITで実装。英字キーボードでのタイピングが遅いので、coromoranに実装をお願いしようと思ったが、厳しそうだったので私が担当した。→AC


G問題を書いてACしている間に、K問題をtakeoさんが読んでいた。自分も読もうとしたが、疲れておりもう何も英語が読めなかったのでtakeoさんに全て教えてもらった。 何もわからんとのことなので、少し自分も考えてみることにした。

K問題

さっくり問題を要約することが難しいので、問題文を読んでほしい。

辞書順最大のものを求める問題で、この手の問題は貪欲に求めるとよい典型があるのでそのように求める。

貪欲+判定で何も考えずに実装すると、N^3logN になるので、なにかしらの方法でN^2 logN くらいに抑える必要がある。(ちなみに、N^2 log^2Nは通らない)

ウーンと悩んでいたところ、一つのindexに注目して一つ一つ値を調べていくのにNかかるが、そこは二分探索で良いことに気づいたので、そこでNlogNにすることができた。 しかし、実装がうまくいかず、サンプルが通らず終わってしまった。 ちなみに、同じ方針を神戸大学のもう一チームもやっていて、TLEしたのでサンプルが通っていても無理だった。 判定部分でしゃくとりなどを使用し、logNを落とす必要があった。


合計でABCGの4完 まあまあチームに貢献できたのではと思っている。


懇親会

まさかの高専時代の後輩に遭遇。前から大学を変えると言っており、大学院で大学を変更していた。 indeedがビンゴ企画をやっており、色んな人と適当には話ながらbingoを埋めていった。 好きなプログラミング言語にRustと書いていたが、思いの外おらずさまよっていたらRust勢を発見した。 Rustの同志を見つけたことに対して強い喜びを感じていたら、あとでよく見ると実はwataさんだった(ICFPCのUnagiの人)。ガチプロだった。 きゅうりともダベり、前々から見せたかった等身大きゅうりの画像を見せるミッションに成功したのでOKだった(ゾッとしたと言われた)

3日目

MUSIN, PFN, BitFlyer

どこまで話していいのかわからないため詳細は省略するが、とてもおもしろかった。 どこの会社もやばかったが、PFNがやはり意味不明レベルだった。やばい。 質問が思ったより来ず人事さんとかも困っている感じだったのでひたすら質問攻めにした。

反省点

チームの連携がまだ微妙に不足していた感じはあった。 これは全員大学院生で時間が取れなかったため仕方がないとは思う。 D問題は完全に僕が速攻で思いつかなければならないジャンルだったので、猛反省。精進します。

Codeforces Round #520 (Div. 2) E. Company

問題

codeforces.com

問題概要

めええええええっちゃ問題文長いけど、実は言っていることは以下のとおりである。

Treeが与えられる。また、以下のクエリがQ回与えられる。

lからrまでの間のノードを一つ無視した上で、Lowest Common Ancestor(LCA)を求める。 無視するノードは、LCAがLowestになるものを選択する。(最も深くなるように選択する)

これを各クエリについて出力する

方針

まず、lからrまでのLCAを求めることを考えてみる。LCAオイラーツアーをして、RMQを発行すれば求めることができる。

LCAやRMQについては、

www.slideshare.net

ABC014 D「閉路」 - RMQを用いたLCA | クリエイティヴなヴログ

がわかりやすい。

これらの記事では、ある2つの間のノードのLCAを求めているが、今回の問題で求められているのは[l,r]LCA

LCAの求め方を整理すると、

2つのノードに対応する2つのindexを求めて、その間にある最大のdepthを求める

という感じである。

これを[l,r]のすべてのLCAに拡張すると、

[l,r]のうち、すべての2点間に関して、2つのindexを求めて、その間にある最小のdepthを求める。

という感じになる。これを全探索すると、O(N2 logN)かかってしまうので、もう少し高速化する。

実は、[l,r]に対応するindexのうち、左端と右端のもののみを調べれば、最小のdepthを求めることができる。

よって、[l,r]LCAの求め方は、

[l,r]のすべてのindexに対して、その最小値と最大値を求める。最小値のindexと最大値のindexの間にあるdepthのうち、最小のものを求める。

と言った感じでO(log N)に収めることができた。

次に、depthが最大になるように頂点を一つ無視しなければならない。LCAの求め方から、左端のindexに対応する頂点か、右端に対応する頂点を無視するのが良いことがわかる。(真ん中のindexに対応する頂点を除いても結局発行されるRMQは同じなので)

最小のindexに対応する頂点をVl、最大をVrとすると、

  • Vlを無視する場合は[l,Vl-1], [Vl+1,r]
  • Vrを無視する場合は[l,Vr-1], [Vr+1,r]

LCAを求め、そのうちdepthが大きくなる方を出力すればAC。

それぞれ区間が2つに分かれてしまったが、この2つの区間のindexをそれぞれ求めて、その最小値と最大値の間にあるdepthの最小値を同様に求めればLCAを求めることができる。

template<class T>
class segtree {
private:
    int n;
    vector<T> dat;

    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return numeric_limits<T>::max();

        if (a <= l & r <= b) return dat[k];

        T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);

        return min(vl, vr);
    }
public:
    segtree(int n_) {
        n = 1;
        while (n < n_) n *= 2;
        dat.resize(2 * n - 1);
        for (int i = 0; i < 2 * n - 1; ++i) dat[i] = numeric_limits<T>::max();
    }

    // value[k] = a
    void update(int k, int a) {
        k += n - 1;
        dat[k] = a;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }

    // min(value[[l,r)])
    int query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
};

void DFS(vector<vector<int> >&G, int node, int depth, vector<pii>& node_depth, vector<bool>& memo) {
    if (memo[node]) return;

    node_depth.emplace_back(node, depth);
    memo[node] = true;

    for (auto &dst : G[node]) {
        if (not memo[dst]) {
            DFS(G, dst, depth + 1, node_depth, memo);
            node_depth.emplace_back(node, depth);
        }
    }
}

vector<pii> DFS(vector<vector<int> >&G){
    vector<pii> node_depth;
    vector<bool> memo(G.size());
    DFS(G, 0, 0, node_depth, memo);
    return node_depth;
}

// [left_node, right_node)
int LCA(vector<int>& node2index, segtree<int>& depth_RMQ, segtree<int>& index_RMinQ, segtree<int>& index_RMaxQ, int left_node, int right_node, int kick) { // -> depth
    // [left_node,kick)
    int left_first = std::numeric_limits<int>::max();
    int left_last = std::numeric_limits<int>::min();
    if (left_node < kick) {
        left_first = abs(index_RMinQ.query(left_node, kick));
        left_last = abs(index_RMaxQ.query(left_node, kick));
    }
    // [kick+1, r+1)
    int right_first = std::numeric_limits<int>::max();
    int right_last = std::numeric_limits<int>::min();
    if (kick + 1 < right_node) {
        right_first = abs(index_RMinQ.query(kick + 1, right_node));
        right_last = abs(index_RMaxQ.query(kick + 1, right_node));
    }

    // [left_node,kick) or [kick+1, r+1)
    int first_index = min(left_first, right_first);
    int last_index = max(left_last, right_last);
    int depth = depth_RMQ.query(first_index, last_index+1);
    return depth;
}

void solve() {
    int N, Q; cin >> N >> Q;
    // pre
    vector<vector<int> > G(N);
    FOR(i, 1, N) {
        int prev; cin >> prev;
        --prev;
        G[i].push_back(prev);
        G[prev].push_back(i);
    }

    vector<pii> node_depths = DFS(G);
    segtree<int> depth_RMQ(node_depths.size());
    segtree<int> index_RMinQ(N);
    segtree<int> index_RMaxQ(N);
    vector<int> node2index(N);
    vector<int> node2depth(N);
    RREP(i, node_depths.size()) {
        int node = node_depths[i].first;
        int depth = node_depths[i].second;
        depth_RMQ.update(i, depth);
        node2index[node] = i;
        node2depth[node] = depth;
    }

    REP(node, N) {
        index_RMinQ.update(node, node2index[node]);
        index_RMaxQ.update(node, -node2index[node]);
    }

    // query
    REP(i, Q) {
        int l, r; cin >> l >> r;
        --l, --r;
        int first_index = abs(index_RMinQ.query(l, r + 1));
        int first_node = node_depths[first_index].first;
        int last_index = abs(index_RMaxQ.query(l, r + 1));
        int last_node = node_depths[last_index].first;

        //[0,first_node) or [first_node+1, r+1) : first_node is ignored
        int depth1 = LCA(node2index, depth_RMQ, index_RMinQ, index_RMaxQ, l, r+1, first_node);
        //[0,last_node) or [last_node+1, r+1) : last_node is ignored
        int depth2 = LCA(node2index, depth_RMQ, index_RMinQ, index_RMaxQ, l, r+1, last_node);

        int select_node = 0;
        if (depth1 > depth2) { // first_node can be ignored
            select_node = first_node;
        }
        else { // last_node can be ignored
            select_node = last_node;
        }
        cout << select_node + 1 << " " << max(depth1, depth2) << endl;
    }
}

Educational Codeforces Round 54 E. Vasya and a Tree

問題

codeforces.com

問題概要

Tree(重み付きではない)が与えられ、木の各頂点に数字を書き込む。最初は0. 以下のM個のクエリも与えられる。

v, d, x: 頂点vと、その部分木のうち、vからの距離がd以内に含まれる頂点にxを足す。

昔似た方針で解いた記憶がある。リアルタイムimosって感じ。

DFSで頂点を見ていく。DFSでは、一個前の頂点で書き込んだ数字を引数として持っておく(sとする)。 見た頂点から、d,xなクエリが発行されていたら、sxを一通り足す。 同時に、木の最大の深さ分の配列を用意しておいて、今見ている頂点の深さに、dを足した先にxを足してメモしておく。 式で表現すると、今見ている頂点の深さをdepthとすると

memo[depth+d] += x

みたいな感じ。xを一通り足したら、memoでメモされている分を引く。(そのクエリの範囲外に到達するため)

また、今見ている頂点が見終わったら、memoに足した分は無効化されるので、最後に引いて終了しないといけない。(ソースコード参照)

vector<vector<int> > G;
vector<vector<pii> > dist_value;
vector<int> res;
vector<int> imos;

vector<bool> is_visited;
void DFS(int node, int depth, int sum){
    if (is_visited[node]) return;
    is_visited[node] = true;

    for (auto &dx : dist_value[node]) {
        int d, x; tie(d, x) = dx;
        int right = min(size_t(depth + d + 1), G.size());
        imos[right] -= x;
        sum += x;
    }

    sum += imos[depth];
    res[node] = sum;

    for (auto &dst : G[node]) {
        DFS(dst, depth + 1, sum);
    }

    for (auto &dx : dist_value[node]) {
        int d, x; tie(d, x) = dx;
        int right = min(size_t(depth + d + 1), G.size());
        imos[right] += x;
    }
}

void solve() {
    int N; cin >> N;
    G.resize(N);
    dist_value.resize(N);
    res.resize(N);
    imos.resize(N+1);
    is_visited.resize(N);

    REP(i, N-1) {
        int x, y; cin >> x >> y;
        --x, --y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    int M; cin >> M;
    REP(i, M) {
        int v, d, x; cin >> v >> d >> x;
        --v;
        dist_value[v].emplace_back(d,x);
    }

    DFS(0, 0, 0);

    REP(i, res.size()) {
        cout << res[i] << (res.size() == i + 1 ? '\n' : ' ');
    }
}