Yuulis.log

Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【VScode + WSL / Windows】C++ 用の AtCoder 向け環境構築をしてみた。(WSL導入からGitによるソースコード管理まで)

はじめに

以前、3年間使い続けた VScode をいったんリセットして、拡張機能などをすべて削除した。

yuulis.hatenablog.com

ということで、今回はこの VScodeC++ 用の AtCoder の環境構築をしていく。

私は今まで AtCoder の環境には Visual Studio を使用していた。確かにビルドやデバッグの操作は簡単に行えるのだが、とにかく重い。私の PC のスペックのせいもあるが、問題を解きながら裏でブラウザを使っていろいろ検索しようとするとスムーズにいかないことが時々あり、これが以前からの悩みの種だったのである。そこで、この機にどうせなら VScode に環境を移行してしまおうと思い立った。

...ここまではいいのだが、私が VScode 上で WSL を動かすのに慣れていなかったのもあり、予想以上に環境構築で沼ったため、約3日間を費やしてしまった。再びこの環境構築をする際に同じ目に合わないよう、ここに記録しておく。

環境構築の目標と前提条件

Windows 上に作ると元々の Windows の環境を汚してしまうことになりあまり好きではないので、 WSL を使うことで Linux 仮想環境上に C++ のローカル実行環境を構築していく。

どのような環境を作るのか

  1. コンテストが始まったら、 VScode 上でそのコンテストのディレクトリを作成し、各問題ごとに提出用ファイルを作成する。
  2. プログラムを書き終えたらそのプログラムをビルド。
  3. VScode 上で自動でサンプルケースを回し、結果を表示。
  4. 問題があれば適宜デバッグを実行。
  5. 最終的に VScode から提出を行い、結果を確認する。
  6. コンテスト終了後、 Git を利用してプログラムを Github リポジトリに記録・保存。

理想的な VScode 上のディレクトリ構成はこんな感じ。

root/
  └ AtcoderSolution/
                     ├ (コンテスト名)/
                     |    ├ (問題番号)/
                     |    |  ├ test/  # テストケース
                     |    |  |   ├ sample-1.in
                     |    |  |   └ sample-1.out
                     |    |  └ main.cpp  # 提出用ファイル
                     ├ a.out  # 実行用ファイル
                     └ debug.in  # デバッグ用のケース入力用ファイル

前提条件

  • OS が Windows である。
  • VScode をインストール済み。

WSL を VScode 上で使えるようにする

zenn.dev

こちらを参考にしながら、まずは VScode 上に WSL の環境を構築していく。

1. VScode 拡張機能「WSL」をインストール。

2. アクティビティバーに追加された「リモートエクスプローラー」をひらき、「WSLターゲット」>「ディストリビューションを追加する」>「Ubuntu (最新LTSバージョン)」を選択。
3. default UNIX user accountを作成。ユーザネームとパスワードを入力する。このとき、パスワードは入力しても表示されないので注意。
4. インストール完了後、左下の「≶」のようなボタンを押して Remote 環境に移行する。

WSL 環境に gcc と g++ をインストールする

前項で作成した WSL 環境に、 C++コンパイラである gcc と g++ をインストールしていく。

1. とりあえず、 gcc と g++ のインストール状況を確認。

$ gcc --version
$ g++ --version

2. インストールされていない場合は、以下のコマンドでインストールする。

$ sudo apt install gcc

3. fetch に関するエラーが出たら、apt-get(パッケージ管理コマンド)を更新。

$ sudo apt-get update

参考記事で記載されていた以下のエラーは起こらなかったので、先を進める。

E: Release file for http://archive.ubuntu.com/ubuntu/dists/jammy-backports/InRelease is not valid yet (invalid for another 20h 18min 53s). Updates for this repository will not be applied.

4. build-essentialをインストール。

$ sudo apt-get install build-essential

5. インストールの確認。バージョン情報が表示されれば成功。

$ gcc --version
$ g++ --version


2024/08/02 追記
上記のコマンド実行で gcc や g++ のバージョンが11.x.xだった場合は、 AtCoder のジャッジアップデートで対応した C++20 や C++23 の機能が使えない。こういうときは、以下の記事を参考にしてバージョン12.x.xコンパイラをインストールすることを推奨する。

yuulis.hatenablog.com

^^^^^ 追記ここまで ^^^^^

WSL 環境に C++ 用の拡張機能をインストールする

以下の拡張機能を好みに応じてインストールする。太字のものは必須の拡張機能

  • C/C++ Extension Pack (C/C++, C/C++ Themes, CMake, CMake Tools が同梱)
  • Command Runner
  • Intellicode
  • Intellicode API Usage Examples (Intellicode 導入で自動インストール)
  • Project Manager
  • zenkaku
  • Path Autocomoplete
  • Markdown Preview Enhanced
  • Material Icon Theme
  • indent-rainbow
  • Include Autocomplete
  • Git Extension Pack
  • Git History
  • gitignore
  • GitLens — Git supercharged
  • Open in GitHub, Bitbucket, Gitlab, VisualStudio.com !

AtCoder Library (ACL) を導入する

ACL とは、AtCoder 公式が提供している C++ 用のライブラリである。 AtCoder の問題でよくみられるアルゴリズムやデータ構造をライブラリ化したもので、これはジャッジサーバにもあらかじめ組み込まれているので、 AtCoderC++ を使っている人は導入しておいて損はないだろう。

1. AtCoder 用のディレクトリを作成する。理想のディレクトリ構成の図に従って、ここではAtCoderSolutionとした。

$ mkdir AtCoderSolution

VScode のコマンドパレットを開き、「WSL: Open Folder in WSL...」>「/home/(user-name)/AtCoderSolution」を選択。以降はこのディレクトリ下でコマンドを実行する。

2. 続いて、 ACL を以下のリンクからzip形式でダウンロード。わかりやすいところに展開しておく。

atcoder.jp

WindowsエクスプローラーでAtCoderSolutionディレクトリを開く。

$ explorer.exe .

ダウンロードしたac-libraryフォルダをAtCoderSolutionディレクトリにコピー。

atcoder-cli (acc) と online-judge-tools (oj) をインストールする

qiita.com

次にこの記事を主に参照しながら、VScode 上からテストケースのダウンロード、ソースコードの提出を自動で行えるようになる acc と、テストケースの自動実行をしてくれる oj を WSL 環境にインストールしていく。ここで、 npm を導入していない場合は、上記記事中で紹介されているこの記事を参考にする。

qiita.com

また、pip3 も導入していない場合は、以下に示す acc 開発者のブログを参考にすると良い。

tatamo.81.la

1. とりあえず pip3 と npm のバージョンを確認する。

$ pip3 --version
$ npm --version

2. インストールされていない場合は、以下のコマンドでまずは pip3 からインストールする。

2024/08/25 追記
WSL 環境に導入した Ubuntu のバージョンが 24.04 の場合、デフォルトで Python3.12 がインストールされるので、以降の処理で PEP668 に関するエラーが起こるようになる。

blog.jp.square-enix.com

これを回避するために、以下の記事を参考にして Python3.10.14 をインストールする。

macocci7.net

インストール後は

$ pyenv global python3.10.14

というコマンドを実行しておく。その後、

$ sudo apt-get install python3

というコマンドは実行せずにスキップして、 pip3 のインストールを行う。

^^^^^ 追記ここまで ^^^^^

この2つのコマンドを実行する。

$ sudo apt-get install python3
$ sudo apt install python3-pip

3. 続いて、 npm をインストールする。

$ curl -o- https://raw.githubusercontent.com/creationix/nvm/v0.33.11/install.sh | bash

実行後、一度ターミナルを再起動し、以下のコマンドを実行する。

$ nvm install node
$ npm install -g npm

4. 再び pip3 と npm のバージョンを確認する。

$ pip3 --version
$ npm --version

バージョン情報が表示されれば成功。

5. 次に、acc をインストールし、ヘルプコマンドを実行して動作確認。

$ npm install -g atcoder-cli
$ acc -h

使用可能コマンド一覧が表示されれば成功。

6. さらに、oj をインストールする。

$ pip3 install online-judge-tools

このとき、私の環境では以下のような警告が出た。

WARNING: The script normalizer is installed in '/home/(user-name)/.local/bin' which is not on PATH.
Consider adding this directory to PATH or, if you prefer to suppress this warning, use --no-warn-script-location.
WARNING: The script jsonschema is installed in '/home/(user-name)/.local/bin' which is not on PATH.
Consider adding this directory to PATH or, if you prefer to suppress this warning, use --no-warn-script-location.
WARNING: The script oj-api is installed in '/home/(userr-name)/.local/bin' which is not on PATH.
Consider adding this directory to PATH or, if you prefer to suppress this warning, use --no-warn-script-location.
WARNING: The script oj is installed in '/home/(user-name)/.local/bin' which is not on PATH.
Consider adding this directory to PATH or, if you prefer to suppress this warning, use --no-warn-script-location.

念のため

$ oj -h

を実行するも、

oj: command not found

となってしまう。どうやら、 PATH が通っていないらしい。ということで、root/home/(username)/.bashrcを開き、以下の内容を追記。

export PATH="$PATH:/home/(user-name)/.local/bin"

再び

$ oj -h

を実行して、バージョン情報が表示されれば成功。

WSL 環境上で AtCoder にログインする

前項で示した記事、あるいは以下に示す acc 開発者のブログを参考に進める。

tatamo.81.la

1. まず、acc と oj の連携状態を確認する。

$ acc check-oj

availableと表示されればOK。

2. acc で AtCoder にログインする。以下のコマンドで、AtCoderのユーザネームとパスワードを入力し、ログインする。なお、パスワードは入力しても画面に表示されない。

$ acc login

3. oj でも AtCoder にログインする。以下のコマンドを実行。先ほどと同様に AtCoder のユーザネームとパスワードを入力する。

$ oj login https://beta.atcoder.jp/

このとき、私の環境では

[ERROR] Selenium is not installed. Please run $ pip3 install selenium

というエラーが出たが、無視しても大丈夫なようだ。

atcoder-cli の設定をする

1. まず、コンテスト開始時にコマンドを実行した際、1回で全ての問題用ファイルを生成するように設定を変更する。

$ acc config default-task-choice all

2. 次に、提出用ファイルのテンプレートを作成する。 acc の設定ファイルが配置されたディレクトconfig-dirに移動する。

$ cd acc config-dir

3. このディレクトリにcppというディレクトリを作成。この名前がテンプレート名となる。そのディレクトリ下に、テンプレート用の C++ ファイル (今回はmain.cppとした) とtemplate.jsonを作成。template.jsonには以下の内容を記述する。

{
  "task":{
    "program": ["main.cpp"],
    "submit": "main.cpp"
  }
}

4. テンプレート用の C++ ファイルに内容を記述後、そのテンプレートが認識されているか確認する。

$ acc templates

cppという項目が表示されていれば成功。

5. 以下のコマンドで、今のテンプレートをデフォルトのテンプレートに設定する。

$ acc config default-template cpp

C++コンパイル設定をする

以下の記事を参考に C++ コンパイル時の設定をする。

qiita.com

1. AtCoderSolutionディレクトリ上に適当な C++ ファイルを作成し、それを選択している状態でCtrl + Shift + Bでビルドを試みる。すると、.vscode/tasks.jsonが生成される。

2. tasks.jsonを以下のように書き換える。

{
    "version": "2.0.0",
    "tasks": [
        {
            "label": "c++ build for AtCoder",
            "type": "shell",
            "options": {
                "cwd": "${fileDirname}"
            },
            "command": "g++",
            "args": [
                "-I",
                "${workspaceFolder}/ac-library/",
                "-g",
                "-O0",
                "-Wall",
                "-Wextra",
                "${file}",
                "-o",
                "${workspaceFolder}/a.out"
            ],
            "group": "build"
        }
    ]
}

コンパイルオプションについては、以下の記事を参照。

triple-four.hatenablog.com

2024/03/16 追記
このままだとコンパイル時にACLを読み込めないエラーが出るので、tasks.json"args"に以下を追加した。

"-I",
"${workspaceFolder}/ac-library/",

^^^^^ 追記ここまで ^^^^^

IntelliSense 設定をする

1. コマンドパレットをから「C/C++:Edit Configurations(JSON)」を選択。すると、.vscode/c_cpp_properties.jsonが生成される。
2. c_cpp_properties.jsonを以下のように書き換える。

{
    "configurations": [
        {
            "name": "WSL",
            "intelliSenseMode": "gcc-x64",
            "compilerPath": "/usr/bin/gcc",
            "includePath": [
                "${workspaceFolder}/**",
                "${workspaceFolder}/ac-library/"
            ],
            "defines": [],
            "cStandard": "c11",
            "cppStandard": "c++17"
        }
    ],
    "version": 4
}

2024/08/25 追記
C++23 を導入した場合は、上述の json"cppStandard"c++23になる。

^^^^^ 追記ここまで ^^^^^

コマンド割り当てとショートカットキーの設定

以下の記事を参考にし、 acc と oj コマンドを簡単なショートカットキーで実行できるようにする。

seiseiengineering.com

Command Runner にコマンドを割り当てる

先ほどインストールした拡張機能「Command Runner」のsettings.jsonを開き、以下の内容を追記する。

"command-runner.commands": {
        "oj test": "oj test -c ${workspaceFolder}/a.out -d ${fileDirname}/test",
        "acc submit": "cd ${fileDirname} && acc submit ${file} || cd ../../",
},

2024/08/25 追記

最近の AtCoder では、出力時の末尾の空白や改行の有無は無視されるようになっている。例えば、ジャッジケースが

```
1␣2␣3↵
```

だった場合、

```
1␣2␣3␣
```

のように出力しても問題ないということだ。 oj におけるテストケースチェックでもこの対応をするには、コマンドオプションとして-S -Nを追加する必要がある。

^^^^^ 追記ここまで ^^^^^

oj のコマンド詳細は以下を参照。

github.com

ショートカットキーの設定

1. Ctrl + K → Sを入力してキーボードショートカット一覧を開き、右上のファイルアイコンをクリックしてkeybindings.jsonを開く。
2. keybindings.jsonに以下の内容を追記する。

    {
        "key": "ctrl+alt+t",
        "command": "command-runner.run",
        "args": {
            "command": "oj test"
        }
    },
    {
        "key": "ctrl+alt+s",
        "command": "command-runner.run",
        "args": {
            "command": "acc submit"
        }
    },
    {
        "key": "ctrl+alt+b",
        "command": "workbench.action.tasks.build",
        "when": "taskCommandsRegistered"
    }

ここでは、「ビルド」をCtrl+Alt+B、「サンプルケース実行」をCtrl+Alt+T、「ソースコード提出」をCtrl+Alt+Sとした。

C++デバッグ環境を構築する

1. ターミナル上で以下のコマンドを実行し、 C++ のデバッガである gdb をインストール。

$ sudo apt install gdb

2. tasks.json作成時と同様に、適当な C++ ファイルを開いた状態でF5を入力すると、.vscode/launch.jsonが生成される。
3. launch.jsonを以下のように書き換える。

{
    // IntelliSense を使用して利用可能な属性を学べます。
    // 既存の属性の説明をホバーして表示します。
    // 詳細情報は次を確認してください: https://go.microsoft.com/fwlink/?linkid=830387
    "version": "0.2.0",
    "configurations": [
        {
            "name": "(gdb) Launch",
            "type": "cppdbg",
            "preLaunchTask": "c++ build for AtCoder",
            "request": "launch",
            "program": "${workspaceFolder}/a.out",
            "args": [
                "<",
                "${workspaceFolder}/debug.in"
            ],
            "stopAtEntry": false,
            "cwd": "${fileDirname}",
            "environment": [],
            "externalConsole": false,
            "MIMode": "gdb",
            "miDebuggerArgs": "-q -ex quit; wait() { fg >/dev/null; }; /bin/gdb -q --interpreter=mi",
            "setupCommands": [
                {
                    "description": "Enable pretty-printing for gdb",
                    "text": "-enable-pretty-printing",
                    "ignoreFailures": true
                },
                {
                    "description": "Set Disassembly Flavor to Intel",
                    "text": "-gdb-set disassembly-flavor intel",
                    "ignoreFailures": true
                }
            ]
        }
    ]
}

私の環境では"externalConsole": falseの部分をtrueとすると、デバッグがうまく実行されなかった。

また、デバッグ終了時に、ターミナルに

[1] + done /usr/bin/gdb --interpreter=mi --tty=${DbgTerm} 0</tmp/Microsoft-MIEngine-In-ndptacu6.2ri 1>/tmp/Microsoft-MIEngine-Out-9278nini .hzx

のような謎の文字列が表示されることがある。デバッグに関して直接的な影響はないのだが、この表示を消したい場合は上記のように

"miDebuggerArgs": "-q -ex quit; wait() { fg >/dev/null; }; /bin/gdb -q --interpreter=mi"

を追記しておくこと。詳しくは Github 上の下記 Issue を参照。

github.com

WSL 環境上に Git を導入する

以下の記事を参考に、 WSL 環境上に Git を導入していく。
ylabdesk.com

Git の初期設定

以下のコマンドで、 Git を使うユーザのEメールアドレスとユーザネームを登録する。

git config --global user.email "(GitのEメールアドレス)"
git config --global user.name "(Gitのユーザネーム)"

WSL から GithubSSH接続する

1. root/home/(username)/.sshを作成し、そのディレクトリ下で次のコマンドを実行。秘密鍵と公開鍵のペアが作成される。

$ ssh-keygen -t rsa

2. Enter file in which to save the key (/home//.ssh/id_rsa):と聞かれるので、鍵の名前を入力する (デフォルトではid_rsa) 。
3. Enter passphrase (empty for no passphrase):と聞かれるので、パスワードを入力する。入力したパスワードは表示されないので注意。空白の場合はパスワードを設定しないことになる。
4. 以下のページにアクセスして、 Github に先ほど生成した鍵の公開鍵の方を登録する。

github.com

「New SSH Key」をクリックし、「Title」には何のSSH鍵なのか分かりやすいように適当に付ける。また、「Key」には、次のコマンドを実行してグリップボードにコピーされる先ほど作成した公開鍵をペーストする。

$ cat ~/.ssh/id_git_rsa.pub | clip.exe

入力が終わったら、「”Add SSH key」で公開鍵を登録する。

作成した秘密鍵は絶対に第三者に漏洩しないように注意すること。漏洩した場合、 Githubへの不正アクセス及びソースコード盗用の恐れあり。公開鍵は最悪漏洩してもセーフ。

5. .ssh/configを開き、以下の内容を追記する。

Host github
HostName github.com
IdentityFile ~/.ssh/(秘密鍵の名前)
User git

6. 以下のコマンドで権限の修正をする。

$ chmod 600 ~/.ssh/config

7. 以下のコマンドで接続の確認をする。

$ ssh -T git@github.com

Hi (githubアカウント名)! You've successfully authenticated, but GitHub does not provide shell access.と表示されれば成功。

Github 上のリモートリポジトリと紐づける

初回の push 時に限り、特別な操作を行う必要がある。以下の記事を参考に進めていく。また、この段階で既に WSL 環境上に Git はインストールされているはずである。

qiita.com

1. ローカルのリポジトリを初期化する。

$ git init

2. (必要があれば) ローカルのブランチ名をmasterからmainに変更する。

$ git branch -m main

3. .gitignoreを作成し、以下の内容を追記する。

.vscode/**
!c_cpp_properties.json
!launch.json
!tasks.json

ac-library/**

*.in
*.out

4. VScode 上 の Git の UI から、「変更をステージ」>「コミット」を選択。
5. Github 上でリモートリポジトリを作成し、そのurlをコピーしておく。今回はこのリポジトリを作成した。

github.com

6. 次のコマンドを順に実行する。Github リポジトリのurlは、最後に.git が付いたものである。

$ git remote add origin (Github上のリポジトリのurl)
$ git fetch origin
$ git merge --allow-unrelated-histories origin/main
$ git push origin main

おわりに

以上で、冒頭に示した環境を構築することができた。

工程が非常に多いので、予期せぬエラーなどで途中で詰まってしまうことが十分に考えられる。エラーが出てきたら自分で調べてみるのはもちろんだが、それでもなかなか解決しないかもしれない。行き詰ったら最初からやり直してみるのも一つの手であろう。幸いなことに、今回は仮想環境上で環境構築を行っているので、簡単にリセットすることができる。詳細は《おまけ》の項を参照してほしい。

実戦で使いにくいところがあれば適宜修正しながら、以降はこの環境で精進していこうと思う。

15000字の記事とか久しぶりに書いたな...

《おまけ》WSL のディストリビューションを削除してやり直す場合

次の記事を参考に、WSL のディストリビューションを削除して、「WSLターゲット」>「ディストリビューションを追加する」を選択するところからやり直すことができる。

zenn.dev

1. 既存のディストリビューションを確認。

$ wsl -l -v

2. 削除したいディストリビューションNAMEを指定して削除。

$ wsl --unregister (削除したいディストリビューション名)

3. 削除されたことを確認。

$ wsl -l -v

以降はこちらと同じ。

【AtCoder】ABC 411 D - Conflict 2 | 緑コーダーが解くAtCoder

atcoder.jp

配点: 425 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1018 / NoviSteps: 1Q

問題概要

 1 台のサーバーと  N 台のPCがある。サーバーおよび各PCはそれぞれ1つずつ文字列を保持しており、最初は全て空文字列である。

 Q 個のクエリが与えられるので、全てのクエリを与えられた順に処理したときの最終的なサーバーの文字列を求めよ。各クエリは以下のいずれかの形式である。

  • 1 p:PC  p の文字列をサーバーの文字列で置き換える。
  • 2 p s:PC  p の文字列の末尾に文字列  s を追加する。
  • 3 p:サーバーの文字列をPC  p の文字列で置き換える。

制約

  •  N,Q は整数
  •  1\leq N,Q \leq 2\times 10^5
  • 全てのクエリについて、 p は整数であり  1 \leq p\leq N を満たす
  • 全ての2種類目のクエリについて、 s は英小文字からなる長さ  1 以上の文字列
  • 全ての2種類目のクエリに対する  s の長さの総和は  10^6 以下

考察

3つのクエリ操作で配列全体に関わるようなものはないので、愚直にシミュレーションしても通りそうだが...

https://atcoder.jp/contests/abc411/submissions/66950771

さすがはD問題。そんなにうまい話はない。

実は、クエリ1や3において文字列のコピーが発生しているのが原因である。

qiita.com


これを回避するために、2つの解法を紹介する。

永続配列を利用する

通常のデータ構造で、更新をするときに更新前の状態のデータも保存しておけるデータ構造を「永続データ構造」という。今回は、その配列版を用いることにする。

具体的には、以下のような「状態」を要素に持つ配列を作成する。

  • この状態の更新元になった状態の  \mathrm{id} と、新たに追加される文字列  s とのペア :  (\mathrm{id}, s)

図にするとこんな感じ。木構造をイメージした方が分かりやすいかもしれない。

サンプルケース1

サーバーや各PCは、この配列(木構造)の index (頂点番号) を参照するようにする。つまり、各クエリでは以下のような処理を行う。

  • クエリ1 :  \mathrm{pc}_{p} = \mathrm{server} とする。
  • クエリ2 : 新たな状態  (\mathrm{pc}_{p}, s) を作成する。その後、  \mathrm{pc}_{p} の参照をその状態の index とする。
  • クエリ3 :  \mathrm{server} = \mathrm{pc}_{p} とする。

これで、各クエリの処理は  O(1) の計算量で済ますことができた。


次に、最終的なサーバーの文字列を復元していく。

これは、全クエリ処理後の  \mathrm{server} が参照している状態の index から始めて、各状態の  \mathrm{id} を辿っていけばよい(木構造で、葉から親に向かってさかのぼるイメージ)。

実装においては、文字列のコピーが発生しないように注意すること(1敗)。実装例の59行目から71行目を参考にするとよい。

クエリを逆読みする

この問題ではサーバーと各PCは同一視できるので、便宜上サーバーをPC  0 とする。

その上で、  q 番目のクエリ処理後のPC  i \: (0 \leq i \leq N) の文字列の状態を  (q, i) とする。これらの状態は、各クエリで以下のように変化する。

  • クエリ1 :  (q, p) = (q-1, 0), \quad i \neq p を満たす全ての i に対して (q, i) = (q-1, i)
  • クエリ2 :  (q, p) = (q-1, p) + s, \quad i \neq p を満たす全ての i に対して (q, i) = (q-1, i)
  • クエリ3 :  (q, 0) = (q-1, p), \quad i \neq 0 を満たす全ての i に対して (q, i) = (q-1, i)

最終的に求めたいのは  (Q, 0) であるが、これは  Q 個のクエリを逆から見ていくことで、結果的に  (0, i) まで到達できる。

この初期状態に到達するまでに、経由したクエリ2にて追加される文字列  s を逆順にして末尾に結合していき、最後に全体を反転させれば答えを得ることができる(実装例を参考のこと)。

実装例

考察1

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

struct Node
{
    int prev;
    string str;
};

int main()
{
    int N, Q;
    cin >> N >> Q;

    int server = 0;
    vector<int> pc(N);
    vector<Node> list;

    list.push_back({-1, ""});

    while (Q--)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int p;
            cin >> p;
            p--;

            pc[p] = server;
        }
        else if (t == 2)
        {
            int p;
            string s;
            cin >> p >> s;
            p--;

            int cur = pc[p];
            pc[p] = list.size();
            list.push_back({cur, s});
        }
        else if (t == 3)
        {
            int p;
            cin >> p;
            p--;

            server = pc[p];
        }
    }

    vector<string> ans;
    int current_id = server;
    while (current_id != -1)
    {
        if (!list[current_id].str.empty())
        {
            ans.push_back(list[current_id].str);
        }

        current_id = list[current_id].prev;
    }

    reverse(all(ans));

    for (auto &&s : ans)
    {
        cout << s;
    }
    cout << endl;

    return 0;
}

atcoder.jp

考察2

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
#define rrep(i, start, end) for (auto i = (start); (i) >= (end); (i)--)

// ======================================== //

struct Query
{
    int type;
    int p;
    string str;
};

int main()
{
    int N, Q;
    cin >> N >> Q;
    vector<Query> queries(Q);
    rep(i, 0, Q)
    {
        int t, p;
        cin >> t >> p;
        if (t == 2)
        {
            string s;
            cin >> s;
            queries[i] = {t, p, s};
        }
        else
        {
            queries[i] = {t, p, ""};
        }
    }

    string ans = "";
    int current_id = 0;
    rrep(q, Q - 1, 0)
    {
        if (queries[q].type == 1)
        {
            if (current_id == queries[q].p)
            {
                current_id = 0;
            }
        }
        else if (queries[q].type == 2)
        {
            if (current_id == queries[q].p)
            {
                reverse(all(queries[q].str));
                ans += queries[q].str;
            }
        }
        else if (queries[q].type == 3)
        {
            if (current_id == 0)
            {
                current_id = queries[q].p;
            }
        }
    }

    reverse(all(ans));

    cout << ans << endl;

    return 0;
}

atcoder.jp

実装時間: 45分

コメント

永続データ構造についての参考記事はこのあたりが分かりやすかった。

trap.jp

qiita.com

【AtCoder】ABC 411 C - Black Intervals | 緑コーダーが解くAtCoder

atcoder.jp

配点: 350 点 / 実行時間制限: 3 sec / メモリ制限: 1024 MB / Difficulty: 234 / NoviSteps: 3Q

問題概要

左右一列に  N 個のマスが並んでおり、最初すべてのマスは白く塗られている。  Q 個のクエリを順に処理せよ。

 i 個目のクエリでは  1 以上  N 以下の整数  A_i が与えられ、次の操作を行う。

  • 左から  A_i 番目のマスの色を反転させる。その後、黒く塗られたマスが連続している区間の個数を求める。

制約

  •  1\leq N,Q\leq 5\times 10^5
  •  1\leq A_i\leq N
  • 入力はすべて整数

考察

「指定されたマスの色を反転させてから、その都度  N 個のマスを全走査して黒いマスの連続区間の個数を求める」ような愚直な方法では、計算量が  O(NQ) となって TLE してしまう。


そこで、指定されたマスとその左右のマスの状況に注目してみる。これは、全部で8通り存在する。なお、以下ではwを白いマス、bを黒いマスとした。

  • www -> wbw : 黒の連続区間 +1
  • bww -> bbw : 黒の連続区間 \pm 0
  • wwb -> wbb : 黒の連続区間 \pm 0
  • bwb -> bbb : 黒の連続区間 -1
  • bbb -> bwb : 黒の連続区間 +1
  • bbw -> bww : 黒の連続区間 \pm 0
  • wbb -> wwb : 黒の連続区間 \pm 0
  • wbw -> www : 黒の連続区間 -1

したがって、クエリで指定されたマスをその左右1マスずつを見てカウンターを更新することで、各クエリを  O(1) の計算量で処理することが可能となる。

以上から、全体として  O(Q) の計算量で解くことができた。


実装時は、  A_i = 1 または  A_i = N となったときのために、予め長さ  N + 2 のマス目をシミュレートする配列を用意しておき、左右端を番兵として活用するのが簡単だろう。

※ 上述のように、左右のマスのどちらか一方がwでも黒の連続区間の個数の変化に影響はないため。

実装例

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N, Q;
    cin >> N >> Q;
    vector<int> A(Q);
    rep(i, 0, Q) cin >> A[i];

    vector<bool> v(N + 2, false);
    int ans = 0;
    rep(q, 0, Q)
    {
        int a = A[q];

        if (!v[a])
        {
            v[a] = true;
            if (!v[a - 1] && !v[a + 1])
            {
                ans++;
            }
            else if (v[a - 1] && v[a + 1])
            {
                ans--;
            }
        }
        else
        {
            v[a] = false;
            if (v[a - 1] && v[a + 1])
            {
                ans++;
            }
            else if (!v[a - 1] && !v[a + 1])
            {
                ans--;
            }
        }

        cout << ans << endl;
    }

    return 0;
}

atcoder.jp

実装時間: 20分

コメント

左右端に番兵を置くのは、このツイートを参考にさせていただいた。

【AtCoder】ABC 411 B - Distance Table | 緑コーダーが解くAtCoder

atcoder.jp

配点: 200 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 32 / NoviSteps: 6Q

問題概要

 1, 駅  2,  \dots, 駅  N が直線上にこの順に並んでいる。ここで、 1\leq i\leq N-1 について、駅  i と駅  (i+1) の間の距離は  D_i である。

 1\leq i \lt j\leq N をみたす整数の組  (i,j) それぞれについて、駅  i と駅  j の間の距離を求めよ。

制約

  •  2 \leq N \leq 50
  •  1 \leq D_i \leq 100
  • 入力はすべて整数

考察

やることはそこまで複雑ではないが、出力形式が少し面倒くさい。

以下のような2重ループのアルゴリズムで解くことができる(0-indexed)。


  1.  i = 0, 1, \dots, N-2 について、以下を繰り返す。
    1.  d = 0 とする。
    2.  j = 0, 1, \dots, N - i - 2 について、以下を繰り返す。
      1.  d D_{i+j} を加える。
      2.  d を出力する。

実装例

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<int> D(N - 1);
    rep(i, 0, N - 1)
    {
        cin >> D[i];
    }

    rep(i, 0, N - 1)
    {
        int dist = 0;
        rep(j, 0, N - i - 1)
        {
            dist += D[i + j];
            cout << dist << " ";
        }
        cout << endl;
    }

    return 0;
}

atcoder.jp

実装時間: 5分以内

コメント

B問題なので難しく考えすぎないようにしたい。

【AtCoder】ABC 411 A - Required Length | 緑コーダーが解くAtCoder

atcoder.jp

配点: 100 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 11 / NoviSteps: 8Q

問題概要

英小文字のみからなる文字列  P が与えられるので、  P の長さが  L 以上であるか判定せよ。

制約

  •  P は英小文字のみからなる長さ  1 以上  100 以下の文字列
  •  1 \leq L \leq 100
  •  L は整数

考察

問題文そのままをやるだけ。

C++なら、P.size() >= Lの真偽で判定できる。

実装例

#include <bits/stdc++.h>
using namespace std;

// ======================================== //

int main()
{
    string P;
    int L;
    cin >> P >> L;

    if (P.size() >= L)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

atcoder.jp

実装時間: 5分以内

コメント

久しぶりにやるだけのA問題だった。

【AtCoder】ユニークビジョンプログラミングコンテスト2025 夏(AtCoder Beginner Contest 411) - 参加記 | 緑コーダーが解くAtCoder

atcoder.jp

コンテスト時間: 2025-06-21(土) 21:00 ~ 2025-06-21(土) 22:40 (100分)

A - Required Length

Difficulty: 11 / NoviSteps: 8Q

解答時間: 1:17


  • 英小文字のみからなる文字列  P が長さ  L 以上であるか判定せよ。

  • C++なら、P.size() >= Lの真偽を確かめればよい。

B - Distance Table

Difficulty: 32 / NoviSteps: 6Q

解答時間: 2:56


  •  N 個の駅が直線上に並んでおり、  1\leq i\leq N-1 について、駅  i と駅  (i+1) の間の距離は  D_i である。  1\leq i \lt j \leq N をみたす整数の組  (i,j) それぞれについて、駅  i と駅  j の間の距離を求めよ。

  • 制約が小さいので、二重ループで駅間距離を順次出力していけばよい。

C - Black Intervals

Difficulty: 234 / NoviSteps: 3Q

解答時間: 20:24


  • 左右一列に  N 個のマスが並んでおり、最初すべてのマスは白く塗られている。  Q 個のクエリを順に処理せよ。  i 個目のクエリでは  1 以上  N 以下の整数  A_i が与えられ、次の操作を行う。
  • 左から  A_i 番目のマスの色を反転させる。その後、黒く塗られたマスが連続している区間の個数を求める。

  • 左から  A_i 番目のマスと、その左右のマスの色の状態は6通りに分類され、それぞれ黒の連続区間の個数  c は以下のように変動する(黒のマスをo、白のマスをxとした)。
    • ooo -> oxo :  c +1
    • xoo -> xxo :  c \pm 0 (左右反転も同様)
    • xox -> xxx :  c -1
    • oxo -> ooo :  c -1
    • xxo -> xoo :  c \pm 0 (左右反転も同様)
    • xxx -> xox :  c +1
  • このように考えれば、各クエリは  O(1) の計算量で処理できるので、全体として  O(Q) の計算量で解くことができる。

  • 左右の範囲外参照を防ぐための処理で手間取った。

D - Conflict 2

Difficulty: 1018 / NoviSteps: 1Q

解答時間: 48:57 + WAx2


  •  1 台のサーバーと  N 台の PC があり、サーバーおよび各 PC はそれぞれ1つずつ文字列を保持しており、最初は全て空文字列である。  Q 個のクエリが与えられるので、全てのクエリを与えられた順に処理したときの最終的なサーバーの文字列を求めよ。各クエリは以下のいずれかの形式である。
    • 1 p:PC  p の文字列をサーバーの文字列で置き換える。
    • 2 p s:PC  p の文字列の末尾に文字列  s を追加する。
    • 3 p:サーバーの文字列をPC  p の文字列で置き換える。

  • 愚直にクエリ処理をシミュレーションすると、クエリ1や3で長さ  |s| の文字列のコピーが発生するため、テストケースによっては TLE または MLE となってしまう(2敗)。
  • そこで、「直前の状態と末尾に追加される文字列」を1つの状態とした、木構造のようなものを考える。
  • クエリ2を処理するときに新しい状態が生成され、クエリ1や3では、サーバーおよび各 PC が参照している状態の id を更新すればよい。
  • 最終的なサーバーの文字列の復元は、最終時点でのサーバーが参照する状態 id から木の根に相当する状態まで遡っていけばよい。

  • ブロックチェーンやGitのバージョン管理みたいなイメージ。
  • データ構造としてはTrie木に相当する?

algo-logic.info

結果

Performance: 1079

1093 → 1092 (-1)

atcoder.jp

「TLEの原因が文字列のコピーにある」ことに気づくのが遅くなって、D問題に時間がかかり過ぎた。