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 332 C - T-shirts | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 161

問題概要

これから  N 日間の予定が0, 1, 2からなる長さ  N の文字列  S が与えられる。  S_i が表す予定の内容は以下の通り。

  •  S_i =0のとき、  i 日目には予定がない。
  •  S_i =0のとき、  i 日目には食事に行く予定がある。
  •  S_i =0のとき、  i 日目には競プロのイベントに行く予定がある。

今、洗濯済みの無地のTシャツを  M 枚持っている。これに加えて、次の条件を満たすように行動できるように、 AtCoder のロゴ入りのTシャツを何枚か購入することにした。

  • 食事に行く日には、無地のTシャツ1枚またはロゴ入りのTシャツ1枚を着用する。
  • 競技プログラミングのイベントに行く日にはロゴ入りのTシャツ1枚を着用する。
  • 予定がない日にはTシャツを着用しない。加えて、その時点で着用済みのTシャツを全て洗濯する。洗濯したTシャツは翌日から着用できる。
  • 一度着用したTシャツは次に洗濯するまで着用できない。

 N 日間のうち予定が入っている日全てについて、条件をを満たすTシャツを着用できるようにするために、最低何枚のTシャツを購入する必要があるか求めよ。ただし、購入したTシャツも1日目の直前の時点で全て洗濯済みの状態で存在するものとする。

制約

  •  M, N は整数で、  1 \leq M \leq N \leq 1000 を満たす。
  •  1 \leq G \lt M \leq 1000

考察

本問では次のような貪欲的解法が成立する。

  •  i 日目の予定が何もないとき、着用済みのTシャツをすべて選択する。
  •  i 日目の予定が食事のとき、
    • もし洗濯済みの無地のTシャツが存在するならば、それを着用する。
    • そうではなく、もし洗濯済みのロゴ入りTシャツが存在するならば、それを着用する。
    • そうではないとき、新たにロゴ入りTシャツを1枚購入してそれを着用する。
  •  i 日目の予定が競プロイベントのとき、
    • もし洗濯済みのロゴ入りTシャツが存在するならば、それを着用する。
    • そうではないとき、新たにロゴ入りTシャツを1枚購入してそれを着用する。

証明は公式解説を参考のこと。


実装においては、2種類のTシャツについてそれぞれ洗濯済みと着用済みの変数を持っておき、それを操作すれば良い。

コード

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

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

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

int main()
{
    int N, M;
    cin >> N >> M;
    string S;
    cin >> S;

    int cleaned_plain = M, dirty_plain = 0, cleaned_logo = 0, dirty_logo = 0;
    rep(i, 0, N)
    {
        if (S[i] == '0')
        {
            cleaned_plain += dirty_plain;
            dirty_plain = 0;
            cleaned_logo += dirty_logo;
            dirty_logo = 0;
        }
        else if (S[i] == '1')
        {
            if (cleaned_plain == 0)
            {
                if (cleaned_logo == 0)
                {
                    dirty_logo++;
                }
                else
                {
                    cleaned_logo--;
                    dirty_logo++;
                }
            }
            else
            {
                cleaned_plain--;
                dirty_plain++;
            }
        }
        else
        {
            if (cleaned_logo == 0)
            {
                dirty_logo++;
            }
            else
            {
                cleaned_logo--;
                dirty_logo++;
            }
        }
    }

    cout << cleaned_logo + dirty_logo << endl;
}

atcoder.jp

実装時間 : 15分

【AtCoder】ABC 332 B - Glass and Mug | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 76

問題概要

容量が  G ml のグラスと  M ml のマグカップがあり、最初はグラスとマグカップはいずれも空である。以下の操作を  K 回繰り返した後のグラスとマグカップの水の残量をそれぞれ求めよ。

  • 操作 :
    • グラスにちょうど  G ml 入っている (水で満たされている) とき、グラスの水をすべて捨てる。
    • そうではなく、マグカップが空であるとき、マグカップを水で満たす。
    • 上のいずれでもないとき、マグカップが空になるかグラスが水で満たされるまで、マグカップからグラスに水を移す。

制約

  • 入力はすべて整数。
  •  1 \leq K \leq 100
  •  1 \leq G \lt M \leq 1000

考察

 K 100 以下と小さいので、操作を逐一シミュレーションしていけばよいだろう。

コード

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

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

int main()
{
    int K, G, M;
    cin >> K >> G >> M;

    int glass = 0, cup = 0;
    while (K--)
    {
        if (glass == G)
            glass = 0;
        else if (cup == 0)
            cup = M;
        else
        {
            int tmp = min(G - glass, cup);
            glass += tmp;
            cup -= tmp;
        }
    }

    cout << glass << " " << cup << endl;
}

atcoder.jp

実装時間 : 5分

【AtCoder】ABC 380 A - 123233 | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 16

問題概要

6桁の正整数  N が与えられる。この整数が以下の条件を全て満たすか判定せよ。

  •  N の各桁のうち、 1 は丁度1つである。
  •  N の各桁のうち、 2 は丁度2つである。
  •  N の各桁のうち、 3 は丁度3つである。

制約

  •  N は整数で、  100000 \le N \le 999999 を満たす。

考察

 N を文字列として受け取り、各文字を見て1, 2, 3の個数をそれぞれ数えればよい。

コード

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

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

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

int main()
{
    string N;
    cin >> N;

    int cnt1 = 0, cnt2 = 0, cnt3 = 0;
    rep(i, 0, N.size())
    {
        if (N[i] == '1')
            cnt1++;
        else if (N[i] == '2')
            cnt2++;
        else if (N[i] == '3')
            cnt3++;
    }

    if (cnt1 == 1 && cnt2 == 2 && cnt3 == 3)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

atcoder.jp

実装時間: 5分以内

【AtCoder】ABC 380 B - Hurdle Parsing | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 27

問題概要

長さ  N の正整数列  A を使って、次のように文字列  S を生成した。

  •  S=|から始める。
  •  i=1,2,\cdots,N の順に、次の操作を行う。
    •  S の末尾に- A_i 個追加する。
    • その後、  S の末尾に|を1個追加する。

ここで、生成された文字列  S が与えられるので、正整数列  A を復元せよ。

制約

  • [tex: 3 \leq |S| \leq 100

考察

 S の生成方法を逆算すればよい。具体的には、

  •  S_1 から順に各文字を見ていく。
  •  S_i =-ならば、  S_i =|となるまでカウンターを増やす。その後カウンターの数字を出力し、  0 に戻す。

コード

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

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

int main()
{
    string S;
    cin >> S;

    vector<int> A;
    rep(i, 1, S.size())
    {
        int cnt = 0;
        while (S[i] != '|')
        {
            cnt++;
            i++;
        }
        A.push_back(cnt);
    }

    rep(i, 0, A.size())
    {
        cout << A[i] << " ";
    }
    cout << endl;
}

atcoder.jp

実装時間: 5分以内

【AtCoder】ABC 380 C - Move Segment | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 223

問題概要

0, 1のみからなる長さ  N の文字列  S が与えられる。 S の中で先頭から  K 番目の1の塊を、  K-1 番目の1の塊の直後まで移動した文字列を出力せよ。なお、  S には1の塊が  K 個以上含まれることが保証される。

制約

  •  1 \leq N \leq 5\times 10^5
  •  2 \leq K

考察

まずは0の塊と1の塊をデータとして持っておきたい。こういうときはランレングス圧縮が有効だ。pair<char, int>の配列のデータ構造に、それぞれの塊の大きさ (長さ?) を格納できる。

その後、0の塊と1の塊は互いに隣接している (どちらか一方が連続することはない) ことを利用して、先頭から  K 個目の1の塊とその直前の0の塊の位置をswapする。

あとは先頭から順に出力していけばよい。

コード

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

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

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

std::vector<std::pair<char, int>> encode(const std::string &str)
{
    int n = (int)str.size();
    std::vector<std::pair<char, int>> res;
    for (int l = 0; l < n;)
    {
        int r = l + 1;
        for (; r < n && str[l] == str[r]; r++)
        {
        };
        res.push_back({str[l], r - l});
        l = r;
    }
    return res;
}

int main()
{
    int N, K;
    string S;
    cin >> N >> K >> S;

    vector<pair<char, int>> rle = encode(S);
    int cnt = 0, idx = 0;
    while (cnt != K - 1)
    {
        if (rle[idx].first == '1')
            cnt++;

        idx++;
    }

    swap(rle[idx], rle[idx + 1]);

    for (auto &&p : rle)
    {
        rep(i, 0, p.second)
        {
            cout << p.first;
        }
    }
    cout << endl;
}

atcoder.jp

実装時間: 35分