ABC146 D Coloring Edges on Treeより

ABC146 D Coloring Edges on Treeより

新ABCを制覇し、コツコツと旧ABCを埋めている。
ABC124～ABC120の水色レベルの問題全てを解説なしで解けて、今までで一番の成長を感じている。
緑以下からでも色々吸収できてニコニコだったのだが、環境の違いにかなり困惑してしまった。

問題はABC120D Lazy Faith。
ACコード
WAコード

解説PDFと少し解き方は違う。
①神社siに東西それぞれに最も近い寺tj、寺tiに東西それぞれに最も近い神社sjをあらかじめ求める。
②クエリ地点に東西それぞれに最も近い神社2箇所寺2箇所と、既に求めたそれらの神社・寺から東西に行く8通りを見る。
結局やっていることはPDFと同じく8通りを見ているだけである。
書いていて思ったが、最初の神社/寺に近い寺/神社を求める部分は、東西方向それぞれじゃなくてどちらか近い方だけでよかったな。

本題の環境の違いについて。
まず、WAコードの間違えた部分について説明しておく。
①である神社/寺より西側あるいは東側に寺/神社ない場合、INFを与えている。
その判別に使ったのが、lower_boundしたインデックスが0なら西側にはない、配列サイズと同じなら東側にはない、というものである。
この配列サイズのsとtを間違えて逆にしてしまった。
間違いなく間違えているのだが、なんとWAコードでもローカル環境では正しい答えが出ている。
間違えている部分は37,44行目。ifの中身のaとbが逆。
どうして・・・。


AtCoderのコードテストではしっかり間違えている。



色々考えてコードを追ってみると、配列外アクセスをしている可能性があることに気付いた。
そう思って少し調べてみた。

サンプル1だと、sのインデックスの判別がうまく行かず、sのサイズは2なのにs[2]にアクセスしてしまう。
そこでローカル環境とAtCoderのテストコードでs[2]の値を出力して値を確かめた。
ローカル環境: 4294967295(unsigned intの最大値)
コードテスト: 0
結果はこのようになっており、1が並んでいるか0が並んでいるかの違いがあった。
これを見るとなるほど納得が行く。
最終的にminを取っているので、ローカル環境ならINF-xの値が保存されるので、正しい答えが出る可能性は十分ある。
逆にテストコードでは0-xの値が保存されるので、minを取ると明らかに正しい答えが出ない。

正直これをデバッグするのは至難の業だと思う。
しっかり解法を立ててサンプルケースが合っている時点で、実装ミスよりは細かい条件分岐にミスを疑ってしまう。
今回はローカル環境でサンプルケースが合っているにも関わらず、提出結果を見るとサンプルケースが間違っていたので、コードテストを試すことで気づけた。
最初は全く分からず、サンプルケースは間違えているわけないし、提出をミスったのかと全く同じコードで2度提出して2度WAをもらった。
本番ならかなり痛い。

今回はサンプルケースが違っていたので分かったが、運悪くサンプルケースは正解で非公開のテストケースが間違えていたらどうしようもない。
どうしようもないが、こういう事態も起こり得るというのは肝に銘じておく必要がある。
ローカル環境だけではなく、コードテストを試すという選択肢を持っていくのも大事だ。

例えば、ABC122 B ATCoderを考える。
文字列を文字の配列とみなし、「要素が'A','C','G','T'のどれかである」という条件を満たす、連続した要素の数の最大値が答えである。
これを実現するコードを2つ乗せる。

方法1

int main(void) {
  string s;
  cin >> s;
  int cnt = 0, maxi = 0;
  // allrep(c, s) = for(auto &&c : s)
  allrep (c, s) {
    if (c == 'A' || c == 'C' || c == 'G' || c == 'T') ++cnt;
    else {
      maxi = max(maxi, cnt);
      cnt  = 0;
    }
  }
  maxi = max(maxi, cnt); // 忘れやすい
  cout << maxi << endl;
  return 0;
}

方法2

int main(void) {
  string s;
  cin >> s;
  int maxi = 0;
  rep (i, s.size()) {
    int start = i;
    while (i < s.size() && (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T')) ++i;
    maxi = max(maxi, i - start);
  }
  cout << maxi << endl;
  return 0;
}

最初、方法1で書いていたのだが、これはミスしやすい。
最後にmaxを更新するという操作をあまりに忘れる。
仮に配列内の全ての要素が条件に合っていた場合、maxiは0のままである。
この問題では忘れたまま提出し、久々にB問題でWAを出してしまった。
実はこの間違いは、覚えているだけでもこの問題と合わせて少なくとも3回している。
1つは初コンテスト参加のABC139 C Lower、このミスに気づくのに少し時間を取られてしまった。
もう1つは、まさかのこの問題と同日に解いたABC124 D Handstand、実装中のデバッグ段階で気付いたのでこのミスによるWAはなかったが、そういや初参加のコンテストでミスったなぁと思い出した後のBでのミスである。ひどい。

他人のコードを見て、これは良さそう！となったのが方法2。
for文の中で最後のmaxiの更新も済ませられるため、忘れるということがない！
カウント用の変数や、条件に前の要素が絡んでくる場合に前の要素を保存するための変数等、必要な変数のスコープが抑えられるのもGood。
これを機に間違えづらくてスマートな方法2を使っていくように習慣づけたいと思う。

しかしrange-based forの使い所がどんどんなくなっていく。
添字を使わないループなんて、文字列のループの一部か答えの配列の出力くらいしかなかったのだが、数少ない文字列ループの一部がさらに減ってしまった。
好きなんだけどなぁ、range-based for。

現在エディタはVSCodeを使っている。
以前はAtomを使っていたのだが、数ヶ月前にVSCodeを使ってみるとかなり軽くて動作も安定していてすぐに乗り換えた。
ターミナル環境はなしで、C++コンパイラにはMinGW-w64を使い、BOOSTは自前でビルドしていた。
特にBOOSTのビルドが面倒くさかった・・・。

ところがこの数ヶ月でVSCodeとコンパイラ周りに色々問題が発生してしまい、1から環境構築を行うことになった。
1からVSCodeのターミナル内でビルド実行できるまで環境構築を行ったので、今度困らないようにメモしておく。
自分用メモではあるが、他人が見ても使えるように説明も入れておく。

といっても、コンパイラ環境構築はMSYS2を使ったら一瞬だった。
Linuxかよ。
ターミナル環境しゅごい・・・。
試しにClangも入れてみたが、Clangの方がエラーメッセージが見やすい気がするので乗り換えた。
gccに依存しているようなので、#include <bits/stdc++.h>も自分で作ることなく使える。
もちろんAtCoder等に提出の際はgccを選ぼう。

2019/11/11追記
VScode 3.task.json
"presentation": "panel"とコンパイルオプションと説明等を一部編集 
コンパイル&実行を高速にする書き方の追加

コンパイラ関連

1. MSYS2(64bit)をインストール。

2. pacman(パッケージ管理システム)をアップデート

   pacman -Syuu

3. Clangをインストール

   pacman -S mingw-w64-x86_64-clang
   (pacman -Ss clangで名前が変わっていないか等パッケージ検索できる)

4. BOOSTをインストール

   pacman -S mingw-w64-x86_64-boost
   (これだけ！ビルドいらない！)

5. gdbをインストール(オプション デバッグするなら)

   pacman -S mingw-w64-x86_64-gdb

VSCode

1. 公式拡張機能C/C++をインストール

2. setting.jsonに以下を追加(GUIでも可)

   "C_Cpp.default.compilerPath": "C:\\msys64\\mingw64\\bin\\clang++.exe",
   "C_Cpp.default.cppStandard": "c++14",
   "C_Cpp.default.cStandard": "c11",
   "C_Cpp.default.intelliSenseMode": "clang-x64",
   

3. tasks.json

   {
     // See https://go.microsoft.com/fwlink/?LinkId=733558
     // for the documentation about the tasks.json format
     "version": "2.0.0",
     "tasks": [
       {
         "label": "build c++",
         "type": "shell",
         "command": "clang++",
         "args": [
           "${relativeFileDirname}\\${fileBasename}",
           "-std=gnu++14",
           "-DLOCAL",
           "-g",
           "-O2",
           "-o",
           "${relativeFileDirname}\\${fileBasenameNoExtension}.exe",
         ]
       },
       {
         "label": "build & run C++",
         "type": "shell",
         "command": "chcp.com 65001; ${relativeFileDirname}\\${fileBasenameNoExtension}.exe",
         "dependsOn": [
           "build c++",
         ],
         "group": {
           "kind": "build",
           "isDefault": true
         },
         "presentation": {
           "panel": "shared"
         }
       },
       {
         "label": "run C++",
         "type": "shell",
         "command": "chcp.com 65001; ${relativeFileDirname}\\${fileBasenameNoExtension}.exe",
         "group": {
           "kind": "test",
           "isDefault": true
         },
         "presentation": {
           "panel": "shared"
         }
       }
     ]
   }
   

   
   文字コードがUTF-8を前提とすると、ターミナルで実行すると文字化けする(と思う)。
   これを解決するには"chcp.com 65001"等でターミナルの文字コードを変更する必要があるが、最初に一度実行しただけではダメ。
   パネルは一緒でも内部的にはおそらく新しいターミナルで実行されているので、毎回実行の前に毎回文字コードを変更する必要がある。
   現状他の手段は知らないが、こう書くと"Active code page: 65001"がプログラムの切れ目の判別にも使えて良いかも。
   VSCodeのターミナルで実行するかどうかは個人差があると思うが、この方が楽だと思う。
   特にWindowsは自動でサンプルケースを実行してくれるツール等の導入が面倒なので、手動でやるならせめて少しでも楽したい。
   なお、コンパイルオプションの-DLOCALは、LOCALを定義することでローカル環境のみで機能するマクロを実現するために入れている。
   
   2019/11/11追記
   この書き方だとコンパイル&実行がかなり遅い。
   まずdependsOnでタスクを呼び出すのが遅いのと、文字コードの変更を途中に挟むと一度クリアが挟むからなのか遅くなる。
   ということで頭悪そうだが以下のようにベタ書きするとかなり早くなる。
   ターミナルから直接コンパイル&実行した時と比べて明らかに遅いのは、VSCode内部で処理が入っているからだと思っていたが、このように書けば遜色ない速度になる。
   プログラムもタスクの設定もベタ書きが最速だぜ！
   

       {
         "label": "debug build c++",
         "type": "shell",
         "command": "clang++",
         "args": [
           "${relativeFileDirname}\\${fileBasename}",
           "-std=gnu++14",
           "-W",
           "-DLOCAL",
           "-o",
           "${relativeFileDirname}\\${fileBasenameNoExtension}.exe",
         ]
       },
   

4. ビルド用のショートカットキーを編集

   デフォルトでは"Shift+Ctrl+B"でビルドタスクの実行になっており、上記の設定ではコンパイルと実行がこれで行える。
   2回目以降の実行でもコンパイルをするのは無駄なので、テストタスクの実行をショートカットキーにすると時間の節約になる。
   自分は"Ctrl+Alt+B"に設定している。
   おそらくmakefileを使えば1つのコマンドで無駄なコンパイルも無くせるが、フォルダごとにmakefileを作るのは面倒なのでこの形式にしている。
   ファイル名を取得してmakefile1つだけでうまくやる方法もありそうだが、makefileはあまり詳しくないので知っている人がいたら教えて欲しい。

VSCode オプション

• コードフォーマッタ

  Atomを使っていた頃はAtom-beautifyでUncrustifyを使っていたが、VSCodeではデフォルトでclang-formatが入っているためこれを使っていた。
  Uncrustifyより設定が楽で、なおかつプロファイル毎に結構良い感じにフォーマットしてくれるのだが、どうしても納得いかない部分がいくつか出てきてしまった。
  VSCodeにも拡張機能としてUncrustifyが提供されているので乗り換えた。
  C++ではフォーマッタとしてUncrustifyが優先して使用する設定と、毎回フォルダに設定ファイルをコピーしなくてもデフォルトとして読み込む設定ファイルのパスを決める設定をしておく。
  せっかくコードフォーマッタを活用するなら保存(Ctrl+S)の度に整形するようにしておこう。
  ある程度書いて保存すればエディタが強制終了しても大丈夫だし、見やすくするために入れるスペースなんかも自動で入れてくれて結果的に早くなるかもならないかも。
  

  "[cpp]": { "editor.defaultFormatter": "LaurentTreguier.uncrustify", },
  "uncrustify.configPath.windows": "uncrustify.cfgのパス",
  

• デバッグ

  VSCodeのデバッグ機能は結構高機能らしいので、デバッグも設定すると良いかもしれない。
  自分は昨日始めて設定したが、競技プログラミングに限ればあまりいらないかなぁという印象。
  task.jsonと同じディレクトリにlaunch.jsonを作成する。
  

  {
    // IntelliSense を使用して利用可能な属性を学べます。
    // 既存の属性の説明をホバーして表示します。
    // 詳細情報は次を確認してください: https://go.microsoft.com/fwlink/?linkid=830387
    "version": "0.2.0",
    "configurations": [
      {
        "name": "clang++.exe build and debug active file",
        "type": "cppdbg",
        "request": "launch",
        "program": "${fileDirname}\\${fileBasenameNoExtension}.exe",
        "args": [],
        "stopAtEntry": false,
        "cwd": "${workspaceFolder}",
        "environment": [],
        "externalConsole": false,
        "MIMode": "gdb",
        "miDebuggerPath": "C:\\msys64\\mingw64\\bin\\gdb.exe",
        "setupCommands": [
          {
            "description": "Enable pretty-printing for gdb",
            "text": "-enable-pretty-printing",
            "ignoreFailures": true
          }
        ],
        "preLaunchTask": "build c++"
      }
    ]
  }
  

終わり。
競技プログラミングの環境構築とは書いたものの、普通のC++コーディングも同じ環境で行っている。
そちらではC++17を使用している等、主にtask.jsonは変更しているが。
競技プログラミングでも早く構造化束縛使わせて。

これだけ書いておけば新しいパソコンを買っても大丈夫だ！
自分で好き勝手設定したあの膨大なUncrustifyの設定ファイルだけは無くすととても嫌な気持ちになるから気をつけよう・・・。

後この忍者ブログとかいうサイトわざわざ<br>入れても自動で消してくるのさすがに頭おかしい。