たれながし

色々雑多に書きます

Nginxで遊んでみる2: 静的ファイルの公開・Redirect・Rewrite

はじめに

Nginxの基本機能をDocker環境で実験しながら理解します。今回は以下の3つを扱います:

  • 静的ファイルの公開
  • リダイレクト(301)
  • リライト(rewrite

環境構成

使用技術

  • Docker(公式 nginx:alpine イメージ)
  • 必要に応じて ImageMagick などでテスト画像を生成

ディレクトリ構成

.
├── docker-compose.yml
├── html/
│   ├── index.html
│   └── static/
│       ├── hello.txt
│       └── logo.png
└── nginx/
    └── default.conf
  • default.conf/etc/nginx/conf.d/default.conf にマウント
  • html/ 以下も Nginx に読み取り専用でマウント

静的ファイルの公開

まずは /static/ パスで静的ファイルを公開します。

location /static/ {
    alias /usr/share/nginx/html/static/;
    autoindex on;
}
  • alias により、リクエストパス /static/logo.png は内部で /usr/share/nginx/html/static/logo.pngマッピングされます
  • autoindex on; により、ディレクトリに index.html がない場合でも一覧表示が可能です

トップページとして、以下のような index.html を配置しました:

<!DOCTYPE html>
<html>
<head><title>Nginx Test</title></head>
<body>
  <h1>Hello Nginx</h1>
  <img src="/static/logo.png" alt="Logo">
</body>
</html>

リダイレクト設定

続いて、リダイレクトの設定です。

location /old-page {
    return 301 $scheme://$http_host/new-page;
}

$http_host とは?

  • $http_host は、クライアントから送られてくる Host ヘッダの値をそのまま使用する変数です
  • 例えば Host: localhost:8080 の場合、 $http_hostlocalhost:8080
  • 一方 $host はポート番号を含まず、localhost のみになります

そのため、ポート番号を含めたリダイレクト先を構築したい場合には、$http_host を使うのが良いです。

注意点

  • 301 は「恒久的な移動」としてブラウザにキャッシュされます。検証中は 302 にするか、シークレットモードで確認すると良いです(1敗。

リライト設定

最後に、URLの内部書き換え(rewrite)です。

location /rewrite-test/ {
    rewrite ^/rewrite-test/(.*)$ /static/$1 last;
}
  • クライアントは /rewrite-test/logo.png にアクセス
  • rewrite により内部的に /static/logo.png に書き換え
  • last により location マッチングが再実行され、 /static/ ブロックへ処理が移動
  • 結果として、実ファイル /usr/share/nginx/html/static/logo.png が返されます

lastbreak の違い

フラグ 処理内容 適した場面
break 書き換えたパスで 現在のlocation内 で処理継続 今の場所だけで完結する場合
last 書き換えたパスで 再度 location をマッチ 別のブロック(例:/static/)に処理を委ねたい場合

実際のところ、alias を使っていても、rewrite 後に別ブロックへ渡したいなら last を使うほうが自然です。


まとめ

  • 静的ファイルは alias により公開可能。パス構造とファイル構造を柔軟に分離できる
  • リダイレクトには $http_host を使うことで、ポート番号まで含んだ正確なURLを返せる
  • rewrite は文字列置換ではなく「書き換え+制御フロー」。breaklast を理解して使い分ける
  • location の書き方(末尾 / の有無)もマッチングに影響する

Nginxで遊んでみる1: リバースプロキシとかSNIとか

はじめに

Nginx触ったこと無いので触ります。

今回は、Docker + FastAPI を用いた構成で、リバースプロキシの基本からHTTPS、SNI(Server Name Indication)まで、ローカルで体験してみた記録をまとめます。


目次

  1. 背景と目的
  2. 構成概要
  3. リバースプロキシ基本設定
  4. ヘッダ操作とHostの挙動確認
  5. HTTPS + 自己署名証明書の導入
  6. mkcertでローカルCAによる認証を試す
  7. /etc/hosts でのDNS疑似体験
  8. まとめ

1. 背景と目的

  • Nginxの基本機能をDocker環境で体験したい
  • FastAPIをバックエンドに置きつつ、Nginxをフロントに
  • HTTPSの通信・証明書・SNIといった概念を自分の手で触る

2. 構成概要

  • Docker Composeを使用
  • Nginxコンテナ + FastAPIコンテナ
  • FastAPIは webapi サービスとして uvicorn で起動
  • Nginxがリバースプロキシで振り分け
localhost:443
  ├── example.local → FastAPI@localhost:8000 (web)
  └── api.local     → FastAPI@localhost:8001 (api)

3. リバースプロキシ基本設定

FastAPI側:

from fastapi import FastAPI, Request

app = FastAPI()

@app.get("/")
def read_root():
    return {"message": "Hello, World!"}

@app.get("/headers")
def get_headers(request: Request):
    return dict(request.headers)

Dockerfile:

FROM python:3.10.18-slim
WORKDIR /app
COPY main.py .
RUN pip install fastapi uvicorn
CMD ["uvicorn", "main:app", "--host", "0.0.0.0", "--port", "8000"]

docker-compose.yaml:

services:
  web:
    build: .
    ports:
      - "8000:8000"

  api:
    build: .
    ports:
      - "8001:8000"

  nginx:
    image: nginx:alpine
    ports:
      - "8080:80"
      - "443:443"
    volumes:
      - ./nginx.conf:/etc/nginx/nginx.conf:ro
      - ./certs:/etc/nginx/certs:ro
    depends_on:
      - web
      - api

Nginx設定:

http {
    server {
        listen 80;
        server_name example.local;

        location / {
            proxy_pass http://web:8000;
            proxy_set_header Host $host;
            proxy_set_header X-Real-IP $remote_addr;
        }
    }

    server {
        listen 80;
        server_name api.local;

        location / {
            proxy_pass http://api:8000;
            proxy_set_header Host $host;
            proxy_set_header X-Real-IP $remote_addr;
        }
    }
}

4. ヘッダ操作とHostの挙動確認

curl http://localhost:8080/headers -H "Host: example.local"
# → host: example.local (webコンテナ)

curl http://localhost:8080/headers -H "Host: api.local"
# → host: api.local (apiコンテナ)

→ $hostにより、ホストヘッダが入っているようですね。加えてserver_nameで適切なwebサーバにリクエストを割り振れています。

proxy_set_headerで遊んでみる

webコンテナの方は以下のように偽装し、apiコンテナの方は消してみます。

proxy_set_header Host fake.example.local; # 偽装名
curl http://localhost:8080/headers -H "Host: example.local"
# → host: fake.example.local

curl http://localhost:8080/headers -H "Host: api.local"
# → host: api:8000

proxy_set_header Host によって明示的に上書きしないと、proxy_pass のホストがそのまま使われている様です。

5. HTTPS + 自己署名証明書の導入

Host名云々の話をしているので、ついでにHTTPS通信も試します。

OpenSSLで自己署名証明書を作る:

openssl req -x509 -nodes -days 365 -newkey rsa:2048 \
  -keyout certs/example.local.key \
  -out certs/example.local.crt \
  -subj "/CN=example.local"

Nginx設定:

server {
    listen 443 ssl;
    server_name example.local;

    ssl_certificate /etc/nginx/certs/example.local.crt;
    ssl_certificate_key /etc/nginx/certs/example.local.key;

    location / {
        proxy_pass http://web:8000;
    }
}

確認:

curl https://example.local -k --resolve example.local:443:127.0.0.1
→ {"message":"Hello, World!"}

HTTPSで通信できましたが、-kでTLSの認証スキップしている点がややモヤモヤします。 → mkcertでローカルにCA建てて解決します。

6. mkcertでローカルCAによる認証を試す

mkcertは自己認証局を作成するツールです。

mkcert -install
mkcert example.local
mkcert api.local

Nginx設定:

server {
    listen 443 ssl;
    server_name example.local;

    ssl_certificate /etc/nginx/certs/example.local.pem;
    ssl_certificate_key /etc/nginx/certs/example.local-key.pem;

    location / {
        proxy_pass http://web:8000;
    }
}

server {
    listen 443 ssl;
    server_name api.local;

    ssl_certificate /etc/nginx/certs/api.local.pem;
    ssl_certificate_key /etc/nginx/certs/api.local-key.pem;

    location / {
        proxy_pass http://api:8000;
    }
}

確認:

curl https://example.local --resolve example.local:443:127.0.0.1
→ {"message":"Hello, World!"}

curl https://api.local --resolve api.local:443:127.0.0.1
→ {"message":"Hello, World!"}

-kなしでも通信できることを確認しました。

ここで--headerでホストヘッダを書き換えてHTTPS通信を試みます。

curl https://localhost:8080 -H "Host: example.local"
→ curl: (60) SSL: no alternative certificate subject name matches target host name 'localhost'

残念。 curlの--headerオプションはHTTP通信中の話で、TLSハンドシェイクのあとになります。 そのためSNIで使われるホストヘッダへの影響は無いようですね。

--resolveオプションの追加が面倒なので/etc/hostsにexample.local, api.localを追加してあげましょう。

7. /etc/hosts でのDNS疑似体験

以下を /etc/hostsに追記します。

127.0.0.1 example.local
127.0.0.1 api.local

これによりresolveオプションを追加しなくても接続できます。

curl https://example.local
curl https://api.local

8. まとめ

  • Docker + Nginx + FastAPIで簡単なリバースプロキシを構築
  • HTTPSやSNIなどのTLS基礎を実体験で理解
  • mkcert による信頼されたローカル証明書の生成
  • --resolve/etc/hosts によるDNSの制御

Nginxより証明書周りの方が比重大きかった気がします。次は静的ファイルの配信まわりをやります。

緑diff精進 その5 (2/19)

AtCoderの現在のレートが1111(ゾロ目!)になった。直近4回のうち、2回は勝利、2回は変動ほぼ無しといった感じで安定感ある結果を残せている。 特にABC340については初めて6完できたし、ABC341では遅延セグ木をちゃんと使いこなせたのでとても成長を感じている。精進してないけど。

2/20現在のatcoderのレート

ところで、この緑diff精進についてだが、今回からRust中心で解いていこうと思う。やっぱABC341 EでPythonで書いた遅延セグ木がTLEし、Rustで書き直したら300ms台でACできた経験が大きい。再帰や遅延セグ木で殴れるがTLEが怖いなぁというお気持ちがやっぱ辛いので、制約が厳しい問題向けにRustの習熟度を上げていきたい。(あとRustで解ける問題は(BTreeSetとか使わなければ)大体Pythonでも楽に解けそうなので)

解いた問題

  • ABC016 C - 友達の友達
  • ABC311 D - Grid Ice Floor
  • ABC075 C - Bridge
  • ABC124 D - Handstand
  • ABC057 C - Digits in Multiplication
  • ABC293 D - Tying Rope
  • ABC334 E - Christmas Color Grid 1
  • ABC273 D - LRUD Instructions

ABC016 C - 友達の友達

atcoder.jp

感想 (解答中に考えたこと)

  • なんかめちゃくちゃ制約が緩いので、とりあえず全探索すれば良い

提出コード

atcoder.jp

ABC311 D - Grid Ice Floor

atcoder.jp

感想 (解答中に考えたこと)

  • 無難にBFSが通りそう。停止した位置についてBFSして、使ったマスを埋めていく。

提出コード

atcoder.jp

ABC075 C - Bridge

atcoder.jp

感想 (解答中に考えたこと)

  • 過去に解いた記憶があるが…… UnionFindで橋判定したいもの以外を繋げて、sameかどうかを見れば橋かどうかがわかる。

提出コード

atcoder.jp

ABC124 D - Handstand

atcoder.jp

感想 (解答中に考えたこと)

  • 最近のABCでセグ木の問題の設定に似てる。反転操作は境界部分を持てば区間更新を1点更新にできる。
  • よく読んでみるとそんな難しいことしなくても良さそう。ランレングス圧縮したあとの Sは必ず...01010101...という格好になるので、[10101...01]のような区間で、0 K個含まれていてかつこの区間が最長なものを出力してあげれば良い事がわかる。しゃくとり実装すればok。

提出コード

atcoder.jp

ABC057 C - Digits in Multiplication

atcoder.jp

感想 (解答中に考えたこと)

  •  Nの制約がちょっと大きい。とはいえ N = A \times Bなので、 Aについて全探索すればせいぜい 10^5回の計算なので通る。

提出コード

atcoder.jp

過去解いてたらしい(覚えてない)

ABC293 D - Tying Rope

atcoder.jp

感想 (解答中に考えたこと)

  • これは解いた記憶がある。ロープに色が云々言っているが、つまり2頂点がとある辺で繋がっているグラフが N個与えられていて、それを M個の辺で繋ぐことを考えれば良い。
  • ある頂点は3つ以上の辺を持たないことは問題の制約により言えるので、環状の判定はUnionFindで繋ぐ際にsameかどうかを判定すれば良い。

提出コード

atcoder.jp

ABC334 E - Christmas Color Grid 1

atcoder.jp

感想 (解答中に考えたこと)

  • これはそもそも出たコンテストの問題ですね。緑のマスをUnionFindで繋げて、赤のマスが緑になった際にUnionFind#groupsの長さがどう変化するかを考えてあげれば良い。
  • 4方のマスを新たなUnionFindで繋げて、groupsの長さを見れば繋げた際にいくつ緑の連結成分数が変化するかが求められる。

提出コード

atcoder.jp

コンテスト中はUnionFindで繋げず、各緑の連結成分にid振ってたらしい。

ABC273 D - LRUD Instructions

atcoder.jp

感想 (解答中に考えたこと)

  • どうせ愚直シミュレーション……と思い制約を確認してみるとあまりにも大きすぎてひっくり返った。
  • 結局これはある進行方向に対して、直近の壁はどこにあるのかを求めることができれば良い。
  • 縦軸・横軸毎にHashMapを用意し、各要素ごとにBTreeSetで壁の情報を追加する。進行方向は4方位のどれかなので、現在地点から進行方向にある壁のBTreeSetについて二分探索で直近の壁を求めてあげればなんとかなる。

提出コード

atcoder.jp

Rustでセグメント木に乗せる際のメモ

Rustで競プロしててセグメント木・遅延伝搬セグメント木を使いたいことってありますよね。 大体ac-library-rsに実装されているものを使うと思うんですけれど、MonoidやMapMonoidというモノイドの実装をする必要があり、割と大変そうなので自分用にメモを残します。 (大嘘担当大臣していたらひっそりと教えてください)。

TL;DR

  • たぶんこれを読むのが一番はやい(わかりやすい)と思います。 betrue12.hateblo.jp

セグメント木

Monoidトレイトを継承した構造体を実装します。

struct MyMonoid;
impl Monoid for MyMonoid {
    type S = usize; // セグ木自体に乗せるオブジェクトの型
    fn identity() -> Self::S {
        // 単位元
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        // 演算操作
    }
}

fn main() {
    let mut tree = Segtree::<MyMonoid>::from(vec![0; N]); // こんな感じに定義
}

usizeにおける加法の実装例

struct Add;
impl Monoid for Add {
    type S = usize;
    fn identity() -> Self::S {
        0_usize
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        a + b
    }
}

fn main() {
    let mut tree = Segtree::<Add>::from(vec![0; N]);
}

atcoder.jp

ちなみに最大・最小・加法・乗法についてはビルトインで実装済みなので、それを利用するのが賢いと思います。

遅延伝搬セグメント木

概要

  • 区間更新・区間クエリを効率的に捌ける便利なデータ構造
  • 計算量
    • 構築:  O(N)
    • 区間更新・区間クエリ:  O(\log N)
      • 定数倍が遅いので注意が必要。
  • 各ノードは以下の情報を持つ
    • data: S
    • lazy: F
      • 子ノードの遅延している更新情報
  • 以下の演算の定義が必要
    • binary_operation: (S, S) -> S
      • data同士の演算操作
    • mapping: (F, S) -> S
      • 親(あるいはクエリ)からの更新情報 F を自分のノードのdataに作用させる演算操作
    • composition: (F, F) -> F
      • 親(あるいはクエリ)からの更新情報 Fを子ノードに伝える必要がある場合に、lazy同士を合成する演算操作
        • 複数回の更新操作を1度の更新操作にまとめるという意味
        • (新しい操作 f, 過去の操作 g)になる。つまり f\circ g(x) =f(g(x))という事ですね。
  • 区間更新
    1. 更新情報 F を受け取り、過不足なく区間を覆える要素にmapping操作でdataを更新する
    2. 子ノードが存在する場合、自身が持つlazyと更新情報Fをcomposition操作で更新する

利用方法

MapMonoidを継承したクラスを構造体を実装する。

struct MyMapMonoid;
impl MapMonoid for MyMapMonoid {
    type M = MyMonoid; // 通常のセグメント木で使うモノイドの情報 data同士の操作やdata自体に関する定義
    type F = usize; // 遅延更新情報の型
    fn identity_map() -> Self::F { // 遅延更新情報の単位元
        0_usize
    }
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
        // 親ノードor区間更新クエリから渡された更新情報(F)を自身が持つdata(S)に作用させる演算操作 ((F, S) => S)
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F {
        // 親ノードor区間更新クエリから渡された更新情報(F1)を子ノードへ伝える更新情報(F2)とマージさせる演算操作 ((F, F) => F)
    }
}

usizeにおける加法の実装例

struct MapMax;
impl MapMonoid for MapMax {
    type M = Max<usize>;
    type F = usize;
    fn identity_map() -> Self::F {
        0_usize
    }
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
        *f.max(x)
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F {
        *f.max(g)
    }
}

fn main() {
    let mut lazyTree = LazySegtree::<MapMax>::from(vec![0; W]);
}

atcoder.jp

lazyに区間長を持たせたい場合

mappingの引数に区間長が与えられていないため、区間更新で"範囲内の要素に +aする"みたいなことができなさそう。 しかしセグ木に乗せるデータ構造を以下のように工夫すればうまくいく。

#[derive(Clone)] // Cloneのサブクラスである必要がある
struct MyData {
    value: usize,
    length: usize
}

fn main() {
    let mut lazyTree = LazySegtree::<MyMapMonoid>::from(vec![MyData { value: 0, length: 1 }; N]); // 利用するデータの範囲にlength=1を与えないとvalueが更新できない
}

struct MyMonoid;
impl Monoid for MyMonoid {
    type S = MyData;
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        MyData {
            value: a.value + b.value,
            length: a.length + b.length
        }
    }
    fn identity() -> Self::S {
        MyData { value: 0, length: 0 }
    }
}
struct MyMapMonoid;
impl MapMonoid for MyMapMonoid {
    type M = MyMonoid;
    type F = usize;
    fn identity_map() -> Self::F {
        0_usize
    }
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
        MyData {
            value: x.value + f * x.length,
            length: x.length
        }
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F {
        f + g
    }
}

cf. AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA

緑diff精進 その4 (1/26)

解いた問題

  • ABC045 C - Many Formulas
  • ABC102 C - Linear Approximation
  • AGC005 A - STring
  • APC001 B - Two Arrays
  • ABC114 C - 755
  • ARC140 B - Shorten ARC

ABC045 C - Many Formulas

atcoder.jp

感想 (解答中に考えたこと)

  1. evalで解けてしまいそうだが、本質じゃないので使わない。
  2. 各数字がどの桁で幾つ現れるかを考えれば良い。
  3. 基本的にどの数字も n桁目は 2^{|S|-n-3}\left( = C(n)\right)個現れる。ただし C(n)を現れる回数とする。
  4. また各数字が使える回数は数式のパターンの数分なので 2^{|S|-1}で、 Sにて k桁目であった数字が k+1桁目以降に現れるはずがない。よって k桁目の数字を S_{k}として、その寄与は \sum_{n=1}^{k-1}S_{k}\times 10^{n-1}\times C(n)\;\left(k\geq 2\right)。最後に S_{k}\times\left(C(k) - \sum_{n=1}^{k-1} C(n)\right)\times 10^{k-1}の分を補正すれば良い。

提出コード

まぁbit全探索で良い atcoder.jp

ABC102 C - Linear Approximation

atcoder.jp

感想 (解答中に考えたこと)

  1. 絶対値の和の最小化なので、どうせ中央値あたりを考えれば良さそう。
  2.  \sum |A_{i} - b - i| = \sum | B_{i} - b |のように変形すれば、 B_{i}の中央値を求めれば終わり。

提出コード

なんと、 B_{i}のソートを忘れていたらしく……(3WA) しかし数列の長さが偶数のケースを無視していたが、通ってしまった。 atcoder.jp

AGC005 A - STring

atcoder.jp

感想 (解答中に考えたこと)

  1. 左から消去っていうのが効いてきそう?とりあえずランレングス圧縮する。
  2. 左端の文字がTである場合は無視すれば良いので、Sから始まる文字列のみ考えれば良い。
  3.  nSが連なっているものを S(n)Tが連なっているものを T(n)とする。
    •  S(n)T(m)\;\left(n\leq m\right)であれば、消去操作は n
    •  S(n)T(m)\;\left(n\geq m\right)であれば、消去操作は m回で、次のSのまとまりの個数に n-mを加える。
  4.  |X| - 消去回数\times 2が答えになる。

提出コード

左から捜索して特定の文字列になったら削除はStackで管理、めちゃ典型だ……。 atcoder.jp

APC001 B - Two Arrays

atcoder.jp

感想 (解答中に考えたこと)

  1. APCなんてものがあるんですね……。 c_{i}=a_{i}-b_{i}で表される c_{i}からなす数列 Cを考える。ここで操作は以下のように言い換えられる。
    •  i, j \in \left[1, N\right]を選び、 c_{i}に2を加算。 c_{j}に-1を加算。
    • 上の操作によって全ての c_{i} 0にすることが目標。
  2. このことから x=-\sum_{i=1}^{N}c_{i}としたとき、 xが操作回数になる。これ以上操作をすると Cの和が1以上になるので一致することはなくなる。同様に x未満の操作回数でも一致しない。
  3.  Cの各要素から最短で 0にする方法を考える。また、 +2する回数と -1する回数を分けてカウントする。
  4.  c_{i}が正数であるならば、 -1をその数だけ繰り返せば良い。
  5.  c_{i}が負数であり、偶数であるなら +2をその数/2回繰り返す。奇数ならば(その数+1)/2回 +2を繰り返した後に -1を1回行う。
  6. 最後に +2 -1の回数および xから判定をする。
    •  -1の回数が +2よりも大きければNo
    •  +2の回数が -1よりも大きい場合、余剰分を +2を1回と +1を1回で繰り返せば Cの要素は全て0になる必要条件を満たし、操作回数が xと同じになればYes
    • その他回数が同じだった場合や xが負数の場合の処理を書けば良い

提出コード

ABC114 C - 755

atcoder.jp

感想 (解答中に考えたこと)

  1. 上位の桁を固定しながら和を取るのが簡単そうだが、同様のもので桁DPがある。練習がてら桁DPで解いてみる。
  2.  dp(i, j, k):=上から i桁目を見た時、数字の使われ方が状態 j (ビット)である場合の数。ただし kは上位 i桁目まで一致しているかどうかのbool値。
  3. 上位の桁を0埋めする場合が考えられ、また3057のように途中に0を入れてはいけないので、bitで探索するときも0のみ特別に扱う必要がある。
  4. あとは i桁目の数字と jの状態から丁寧に丁寧に丁寧に状態遷移を実装してあげれば良い。

提出コード

苦しすぎた…… atcoder.jp

ARC140 B - Shorten ARC

atcoder.jp

感想 (解答中に考えたこと)

  1. ARCであればどのタイミングで操作してもよく、AARCCであれば奇数回目で操作すると偶数回目でACまで変化できて嬉しい。つまりAARCCARCの個数がわかればよいのでは? -> WA
  2. 考えてみたがわからんので解説をチラ見。なるほど、A...ARC...Cを常に奇数回目で操作するようにすれば、両端のAあるいはCの個数の小さい数ぶん操作が可能になる。
  3. つまりランレングス圧縮する過程でA...ARC...Cの塊の情報を整理すれば見通しが良くなりそう。
  4. あとは奇数回目であればARC以外のものを優先して操作し、偶数回目であればARCを優先して操作することが必要になる。
  5. 実装方法に迷ったが、操作回数は高々 N回で抑えられるだろう(操作することにより、1文字あるいは2文字消去なので)。なのでpriority_queueを使って愚直に勘定するのが良い。

提出コード

atcoder.jp

緑diff精進 その3 (1/25)

解いた問題

  • ABC052 D - Walk and Teleport
  • ABC053 D - Card Eater
  • ABC239 E - Subtree K-th Max
  • ABC276 E - Round Trip
  • ABC177 E - Coprime
  • ABC115 D - Christmas
  • ABC194 E - Mex Min

ABC052 D - Walk and Teleport

atcoder.jp

感想 (解答中に考えたこと)

  1. 貪欲かDP。DPは制約的に無理そうなので貪欲の方針にする。
  2. 1------2-3-4 みたいな町で B = A + 3くらいの条件で考えてみると、234のまとまりにテレポートした方が良い。また、3にテレポートして 3 -> 2 -> 3(経由) -> 4とすると2 -> 3(経由)分が無駄になるので、一番近い場所にテレポートするのが良い。
  3. よって \rm{dist}_{i} = X_{i} - X_{i-1}として、 \sum_{i=2}^{N} \min \left\{\rm{dist}_{i} \times A, B\right\}で良さそう。

提出コード

atcoder.jp

ABC053 D - Card Eater

atcoder.jp

感想 (解答中に考えたこと)

  1. 何を消すかを管理すれば良い?
  2. 同じカードの枚数が偶数ならば2枚、奇数ならば1枚残る。
    • 操作の対象はカードの枚数を Mとして M \geq 3であって、操作1回につき2枚ずつ減るので
    • この時の操作の回数は \lfloor \frac{M-3}{2} \rfloor + 1 \; \left(M \geq 2\right)
  3. 偶数枚あるカードの種類の数を Lとする。
    1.  Lが奇数のときは1枚まで減らせるため、残った1枚を最小あるいは最大とできるように3枚を選択すれば良いので、操作回数は \lfloor \frac{L}{2} \rfloor + 1
    2.  Lが偶数の時は2枚まで減らせる。ここでこの2枚を同時消しできる可能性があるので、偶数枚あるカードのうち最小値 L_{\rm{min}}および最大値 L_{\rm{max}}を残すように選択する。 \left(L_{\rm{min}}, L_{\rm{max}}\right)に含まれる奇数枚のカードが存在すれば操作回数は \lfloor \frac{L}{2} \rfloor。存在しなければ \lfloor \frac{L}{2} \rfloor + 1
  4. 操作回数を Kとすれば、 N - K \times 2が残るカードの枚数。

提出コード

atcoder.jp

ABC239 E - Subtree K-th Max

atcoder.jp

感想 (解答中に考えたこと)

  1.  Kの制約がそこまでキツくないので、部分木を O(1)で出力できれば十分そう。
  2. 木はとりあえずlist[set[int]]で管理し、根からBFSで子 -> 親のパスを消し飛ばしておく。
    • これは不要で、DFSの引数に親を追加し、親 = 子の場合にcontinueすれば良い。
  3. DFSで根から探索し、各ノードに上位20件の数字のリストを持たせていく。
    • つまり葉であれば[X[n]]を返し、そうでなければ子ノードの返り値とX[n]を合わせて降順ソート & limit = 20で良い
  4. あとは O(1)で答えが出る。テーブルの構築にはDFSでの構築部分とクエリ部分で O(Q + NK\log K)かかってると思う(たぶん)。

提出コード

部分木といえばオイラーツアーがあったなと反省……。 atcoder.jp

ABC276 E - Round Trip

atcoder.jp

感想 (解答中に考えたこと)

  1. BFSでvisitedがTrueのものがあればYes? しかし戻るパターンを除去するのが面倒くさい。
  2. だらだら実装してサンプルが合わないので解説を少しだけ読む。色分けかぁ……これは思いつきたい。
  3. visitedをbooleanではなく数値で管理し、S#扱いにして4方向にBFSするだけになった。

提出コード

atcoder.jp

ABC177 E - Coprime

atcoder.jp

感想 (解答中に考えたこと)

  1. setwise coprimeはgcd(*A) == 1で一発で判定可能。つまりpairwise coprimeの判定が肝になる。
  2. 当然のことながら全探索は無理。ところで、 \gcd{\left(a, b\right)} =1って \frac{a}{b}が既約分数なので、共通の素因数を持たないと解釈できそう。
  3. つまり集合 Aの素因数を全部調べて重複があるかを判定すれば良い。
  4. エラトステネスの篩をつかって \max{\left\{A_i\right\}}\left(=A\right)までの素数を列挙し、素数をkeyとしてkeyが素因数として出てきたかを持つboolをvalueとして持つHashMapを用意する。素因数分解 O(\sqrt{N})のものを使う。素因数分解については指数の要素はいらないので、素因数の集合を返すように改造しておく。
  5. あとは出てきた素因数をHashMapに記録し、既にTrueのものがあればpairwiseになる。
  6. これ計算量 O(N\sqrt{A}) 10^9じゃないですか?落ちそう -> ACした。

提出コード

エラトステネスの篩で素数を列挙している途中で、 D\left[n\right]:=nを落とした素数とすることで試し割り(2 ~  \sqrt{N}まで割る方法)をする必要がないので O(\log A)でできるらしい。天才では???? atcoder.jp

ABC115 D - Christmas

atcoder.jp

感想 (解答中に考えたこと)

  1. 明らかに再帰関数の実装を求めていそうな問題。とはいえバーガーの高さとパティの枚数は普通に漸化式を解けば O(1)で出る。
  2. レベル nバーガーをg[n]、バンズをB、パティをPとすればレベル nバーガーはBg[n-1]Pg[n-1]Bと書ける。
  3. レベル nバーガーに対して、 Xが下部のレベル n-1バーガーの領域を超えている場合のみその分のパティを加え、その分の高さを Xから引いていけば求まる。
    • レベル kバーガーの区切りが良いところから始める必要があるので。真ん中のパティを特別に扱わないとバグる。
    • パティが存在する領域よりも高い Xである場合、レベル0バーガーの探索を終えても Xは0よりも大きくなるので、ループの条件に レベル >= 0が必要 (1敗)

提出コード

正直上記の説明じゃ何も伝わってないと思う……説明難しい……。 atcoder.jp

ABC194 E - Mex Min

atcoder.jp

感想 (解答中に考えたこと)

  1. しゃくとりっぽく、区間をずらした際に出ていく数字・入る数字を管理すれば高速で \rm{mex}求められそうじゃない?(根拠なし)
  2. 使える数字をSortedListで管理し、区間にある数字をHashMapで管理する。区間にある数字について、個数が0になったものがあればSortedListにその数字を追加し、個数が1以上になったものがあればSortedListからdiscardする。
  3. あとはSortedListの先頭をchminすれば良い。これで計算量は O(N\log N)なはず。定数倍の遅さにビビりながらsubmit。

提出コード

atcoder.jp

緑diff精進 その2 (1/24)

解いた問題

  • ABC260 D -Draw Your Cards
  • ABC075 C - Bridge
  • ABC191 C - Digital Graffiti
  • ABC166 E - This Message Will Self-Destruct in 5s
  • ABC194 D - Journey
  • CodeFestival 2016 qual A C - Next letter

ABC260 D -Draw Your Cards

atcoder.jp

感想 (解答中に考えたこと)

  1. 愚直にシミュレーションする問題っぽい。場を表す配列を容易したとして、何も考えずに実装すると O(N^2)で間に合わない。
  2. 要求されるデータ構造は、場に見えるカードの数を管理していて、ある数 X以上で最小の数を O(N)よりも速く見つけられるようできるもの。
  3. 後者の条件は二分探索でいけそう。つまり、SortedListで場に見えるカードの種類を管理し、実際の束はHashMapで管理するとうまくいきそう。
  4. 二分探索はSortedListのbisect_leftを利用する。これによって O(N\log{N})で解ける。
  5. 実装したがTLE。というのもhashmap[key] = hashmap[otherkey] + [new_value]としたところが遅いようだった。hashmap[key] = hashmap[otherkey]の後にhashmap[key].append(new_value)をするとACした。
    • 以下のように初期化と一緒にappendっぽいことをしようとすると参照渡しじゃなくなる。まぁhashmap[0] + [7]で新しいリストに変わってるのは確かに納得。

hashmapのid変化の確認

提出コード

atcoder.jp

ABC075 C - Bridge

atcoder.jp

感想 (解答中に考えたこと)

  1. UnionFindっぽい雰囲気。特定の辺を除いてmergeしたあとにグループの数が2以上かどうかで判定可能。
  2. 成約がとても緩いので、各辺を選択してからそれ以外の辺を結んで判定する O(M(M+N))が間に合う。

提出コード

atcoder.jp

ABC191 C - Digital Graffiti

atcoder.jp

感想 (解答中に考えたこと)

  1. 難読では……? ちょっと調べてみて納得したが、もう少しサンプルほしい……。
  2. 辺の向きのベクトル(辺の方向と垂直な向き)が変わるたびにカウントするも、サンプルすら合わない。
  3. 解説ACした。辺が生じるときは角が必ず存在するので、zip(range(H-1), range(W-1))の範囲で 2\times 2で角かどうか (つまり黒または白のマスが1つだけ)を判定し、その数を出力すれば良い。難しいが、思いつけるようになりたい……。

提出コード

atcoder.jp

ABC166 E - This Message Will Self-Destruct in 5s

atcoder.jp

感想 (解答中に考えたこと)

  1.  |i-j|=A_{i} + A_{j}の組を見つける問題。前提として O(N^2)は無理。 i jに分けると、 i - A_{i} = j + A_{j} \; (i > j), i + A_{i} = j - A_{j} \; (j > i)
  2. また組の数が分かれば良いので、 i > jのような条件に固定しても問題ない。
  3. 以上のことから、 i + A_{i}をkeyにHashMapにその個数を保存し、 i - A_{i}\; (i = 1, 2, 3, ... N)で検索して個数の和を出力すれば良い。

提出コード

atcoder.jp

ABC194 D - Journey

atcoder.jp

感想 (解答中に考えたこと)

  1. 漸化式をそのまま実装すればできるのでは…?つまり N個の頂点があって n個目の頂点をつなげる期待値を E(N, n)として、  E(N, n+1) = E(N, n) + \frac{N-n}{n}\sum^{\infty}_{i=1}\left(\frac{n}{N}\right)^{i}i = E(N, n) + \frac{N}{N-n}
  2. 開始位置と終わりの位置に気をつけて実装する。

提出コード

atcoder.jp

CodeFestival 2016 qual A C - Next letter

atcoder.jp

感想 (解答中に考えたこと)

  1. 前から貪欲にaに変えていけば良い。変えられない場合は嬉しくない変形になるのでスルーし、次の文字の変形にトライする。
  2. 最後の文字の場合はKになるまで操作を行えば良い。(それ以外の文字で操作すると嬉しくない)

提出コード

なんかめっっっっちゃバグらせた

atcoder.jp