ベスパリブ

プログラミングを主とした日記・備忘録です。ベスパ持ってないです。

std::coutが正常に動作しない現象

概要

昨日msys2でC++環境を作り直した続きです。

  • 環境
    • Windows10 64bit
    • Powershell PSVersion 7.4.6
    • g++.exe (Rev1, Built by MSYS2 project) 14.2.0

現象発生

std::coutが正常に動作しない現象（何も出力せずプログラムが強制終了）が発生しました。

#include <iostream>

int main() {
    printf("Hello World!\n"); // これは普通に出力される
    // std::ios::sync_with_stdio(false); // これを追加したらcoutできるようになる
    std::cout << "Hello World!!" << std::endl;  // 出力されない（プログラムが強制終了される）
    return 0;
}

コンパイルと実行結果

コンパイルは正常にできているが、実行で赤くなっていることから、なにかしらのランタイムエラーが発生して落ちてしまっています。

不思議なのは、std::ios::sync_with_stdio(false);を追加すると正常に出力されるというところ。

調べると同様の現象っぽい人を見つけましたが、よくわかりませんでした。C++ stringを使用するとcoutが動作しない

行き詰まったので、ChatGPTに聞いてみます。

ChatGPTさん、おねがいします

ターミナルの変更を勧められたのでGit Bashで試してみると、なんと実行結果が変わりました。

「Segmentation fault」と表示されるようになった

解決

これで検索すると、以下の記事を見つけました。

qiita.com

DLL地獄に引っかかってしまったようです。記事にあるようにコンパイルオプションに-static-libstdc++を追加すると、この現象は解消されました。

-static-libstdc++ を追加してコンパイル

久しぶりに msys2 を再インストールしたら C:\msys64\bin が消えてた

msys2 C++

タイトル通りなのですが、msys2.orgからmsys2-x86_64-20240727.exeをダウンロードし実行。WIndows10 64bit PCにインストールしました。

インストールガイドの言われるままにコマンドも実行。

$ pacman -S mingw-w64-ucrt-x86_64-gcc

インストール完了したあとにg++コマンドを打ってみてもそんなものは無いと言われるので、インストールフォルダを見に行ってみると、C:\msys64\binが消えてました。

どうやらMSYS2の構成が変わったらしく、clang64、mingw64、ucrt64などフォルダごとにbinが作られることになったらしいです。

色々調べましたが、なんかMS的にUCRTがおすすめっぽいので、とりあえずこちらを使ってみることにしました。

環境変数の設定にC:\msys64\ucrt64\binを追加し、VSCodeの設定ファイルも修正して終了。

gdb.exeも存在しなかったので、C++ Why is MSYS2 MINGW UCRT x64 gdb command not found - Stack Overflowを参考にインストールしました。

Causera: Generative AI for Software Development 感想

概要

CauseraのGenerative AI for Software Developmentという講義が無料アクセスできたのでやりました。無料期間中にさっさとやってさっさと退会したので認定証はもらっていません。

Introduction to Generative AI for Software Development 完了

AI-Powered Software and System Design 完了

Team Software Engineering with AI 完了

どんな講義

「開発者向けはじめてのChatGPTの使い方」みたいな講義でした。SNS等どこかで聞いたようなハウツー話が多かったのですが、役に立ったなと感じたところもありました。

ほとんどは動画視聴の講義で、練習問題として出されるデータ構造は基本的なものなので、まとまった時間と集中力が続く人は1日か2日ですべての講義を終えることができると思います。私は3日かかりました。

なるほどなぁと思ったのは、ChatGPTにRole（役割）を割り当てると良いという話。 「私はPython初心者で、あなたは私のメンターです。先程書いた関数について動作を説明して下さい」 「あなたはソフトウェアアーキテクトかつセキュリティスペシャリストです。次のコードの脆弱性を見つけ、可能なら改善案を書いて下さい」 「あなたはPythonのオープンソースコントリビューターです。先程の関数を批評し、改善点を提案して下さい」「あなたはソフトウェア設計パラダイムの専門家です。新しく発足する〇〇するプロジェクトにおいて、どのような開発手法を取り入れることを考えますか」 などと書くと、ChatGPTは役割に応じて説明してくれるようになり、またその役割に特化した情報を返してくれるようになります。

このようなRole割り当てをうまくやるためには、センスや慣れ、専門知識が必要になるでしょう。そして繰り返しChatGPTとやり取りを行い、「まあいいでしょう」となるまでコードをブラッシュアップしていく。

残念ながらありがたいことにAIは万能ではなく強力な同僚であり、人の仕事はまだ残っているということでした。

このへんのChatGPTに対するセンスは形式知にしておいてもらえると普通にありがたいので、「Effective ChatGPT ～ChatGPTと共にコードを書くときにに聞くべき100のこと～」みたいな本があったら読んでみたいなと思いました。

あとは便利だなと思ったのは、プロジェクトの依存関係解消などにもChatGPTは使えるということ。古いコードベースは変更したくなくて、それに合った古いpandasとnumpyを使うような面倒な依存関係解消も「バージョン〇〇のnumpyに対してはどのpandasのバージョンを使えば良いの」とChatGPTに聞くと答えてくれました。

このような話はYouTubeでも腐る程ありそうでCauseraに認定証料金7000円払う価値があるのかわからない――と思いましたが、腐る程ある動画を自発的に見る気は起きないので、その見る気を7000円で買えると考えればいいのではないでしょうか。あるいは、Laurenceにスーパーチャットを送ったという感覚で納得できるかもしれません。Laurenceの懐に入るかは知らないけれど。

感想

ChatGPTと共にコードを書くというのをあまりやってきてなかったので、結構新鮮な体験でした。今回ChatGPT-4oを使いましたが、「Copilotのない開発は考えられない」みたいなことを言う人の気持ちがすこしわかった気がしました。なるほど、これは良いものですね。

AHC026 参加記録

トヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）に参加した記録です。

方針1：貪欲法

4時間の短期間コンテストなので、まずは正の得点を得られる簡単な貪欲ができないかを優先した。

とりあえずビジュアライザを動かしてみて、どういう貪欲法がいいかを考える。

ターゲットの箱より上のすべての箱を、最も使わなそうな山を選んで、そこに積んでいく貪欲法をした。

「最も使わなそうな山」は、ターゲットの箱となるものが時間的に最も遠い山を選んだ。

seed0のビジュアライザ

提出コード：https://atcoder.jp/contests/ahc026/submissions/47302082

得点：1,356,657

この得点の人が多かったので、似たような解法をやってる人多そう。

方針2：ソートする？

箱を動かす時、なるべく上から昇順になるようにしたほうが、同じ体力で効率よく動かせるのでは？

イメージ図

結果的に言えば、重さ+1の体力を消費するのでそんなことなかった。

提出コード：https://atcoder.jp/contests/ahc026/submissions/47305951

得点：1,324,254

得点下がっちゃった。

方針3：ビームサーチ

多様性が確保できそうなのでビームサーチいけるかなと思って実装。永遠にバグらせて終了。

最終結果

方針1のコードが最終提出になった。

得点：1,356,657

順位：426位

強い人の方針

「片方に集める」「寄せる」みたいなのはAHCの典型なので最初そうしようかなと思ったのだけど、後半すっかり忘れていた。

山が10個あるからうまくソート状態を作ればいいのか？（ハノイの塔のイメージ？）

感想

  • 最初の貪欲の方針は悪くなかったと思う。
  • ビームサーチバグらせたのは残念。実装方法のテンプレートをNotionにまとめておこう。
  • でもビームサーチあんまりよいスコアでないらしい
  • AHC楽しいので毎週開催してほしい。
  • レートが単調増加は嬉しい。

AHC025 参加記録

AHC AtCoder

概要

AtCoder Heuristic Contest 025に参加した記録です。

珍しいインタラクション問題。

方針1：ナイーブ実装

とりあえずシンプルな解法を考えて実装するところから着手した。以下のような解法になる。

  1. 最初、各グループは1つずつアイテムを持つ。残ったアイテムはすべてグループ0が持つ。
  2. s=0とする。
  3. グループsが他のグループに順番に1個ずつアイテムをランダムに渡していく。
  4. グループsがグループiにアイテムを渡したとき、グループiがグループsより重さが大きくなったら、s = iになって、再度3を繰り返す。

実装上の注意点として、

  • アイテムが0個のグループを作ってはいけない
    • 他のどのアイテムを足し合わせても敵わないような激重アイテムが1個ある場合、そのアイテム1個を唯一持つグループが出来上がる。このグループからその激重アイテムを取るとアイテムが0個になってしまうので取ってはいけない。

シード1の結果

提出コード：https://atcoder.jp/contests/ahc025/submissions/46658987

得点：1,163,992,256

方針2：クイックソート実装

方針1の問題点は、「アイテムを1個ランダムに選んで渡す」とき、重いアイテムを渡す可能性があることにある。できれば軽いアイテムをやりとりして各グループの重さがならされるようにしたい。

ここで、クエリに2つのアイテムの大小関係を尋ねまくると、（アイテムの重さは不明のままだが）いずれアイテムをソートできることに気づく。アイテムがソートできた状態になると、各グループの一番軽いアイテムがわかるので、軽いアイテムを選択してやりとりすることで微調整できるようになる。

ソートアルゴリズムはクイックソートを実装した。

実装上の注意点として、

  • クイックソートは最悪クエリ回数が(N-1)N/2 回かかる
    • クイックソートでクエリ回数を使い果たさないようにしなければならない。今回は実装が簡単のため N*10 <= Q のときクイックソートするのに十分なクエリ回数があると判断するプログラムとした。十分なクエリ回数がない場合、ナイーブ実装に切り替えた。

シード1の結果

提出コード：https://atcoder.jp/contests/ahc025/submissions/46693668

得点：811,781,427

今回の問題は得点が小さいほど良いスコアとなるので、改善されたと言える。

方針3：クイックソート打ち切り

方針2の改良。クイックソートに使えるクエリ回数上限を設定できるようにして、上限に達したら途中でソートを打ち切る。打ち切ると順番が中途半端にわからないアイテムがあるが気にしない。

アイテムの交換に使える最低クエリ回数を D*3 くらい（各グループ3回くらいアイテムのやりとりをするくらい）は確実に残すようにして、あとはクイックソートに使えるように設定した。もちろんクイックソートが早く終わればアイテムの交換に使えるクエリ回数は増える。

これにより方針1のナイーブ実装の実行を完全に排除できた。（運次第だと思うが、ナイーブ実装のほうが良いスコアのサンプルがちらほらあったが……）

提出コード：https://atcoder.jp/contests/ahc025/submissions/46697190

得点：586,051,759

このあと、アイテムの交換に使える最低クエリ回数の値をいろいろ試したところ、D*5 が最もスコアが良かったので最終的にそうした。

方針4：グループの重さのクイックソート実装

Seed 29を考察した。

方針3のシード29の結果

シード29は完全にソートされているにも関わらず、あまり良くないスコアになっている。

たとえば、左から5番目のグループは軽いアイテムをたくさん持っているにも関わらず、それらを貯め込んで一番重いグループになっている。こいつのグループが他のグループに軽いアイテムを配ってくれればもっと良いスコアになるはず。

分析の結果、全1423ターンのうち、509ターン目でソートが完了し、残り約900 ターンでアイテム交換をしていた。アイテム交換に十分のターン数があるにも関わらず、スコアは良くない結果になっている。

もっと深く考察するために、途中結果を出力して確認してみる。

ソート完了直後の状態

ソート完了直後は上の状態となった。

1回目のアイテム交換

一番左と、左から3番目のアイテムの交換が行われた。

2回目のアイテム交換

一番左と、左から4番目のアイテムの交換が行われた。

これを見ると、重いグループ同士で無駄な交換が起きているように見える。なので、クエリ回数が十分に残っている場合（最悪交換回数の(D-1)*D/2以上の場合）、各グループの重さでソートし、「重いグループと軽いグループで交換を行う」ということをすれば良さそうである。

すなわち今回の方針では、グループの重さのクイックソートを実装した。

提出コード：https://atcoder.jp/contests/ahc025/submissions/46748553

得点：602,827,302

スコアが悪くなってしまった。

方針5：方針4の改良（残りクエリ回数を十分取るときだけグループのソートをする）

方針4では、残りクエリ回数が十分にあるときだけグループのクイックソートをして、そうでないときは方針3に切り替えるように調整した。それでもスコアが悪かったので、何がいけないのか出力ファイルを比較して原因を探った。

悪くなったサンプルを比較してみる。

以下の分数は、(アイテムのソートで使ったクエリ回数)/(全クエリ回数)。

シード7の比較。

278/294

左が方針3、右が方針4

シード8の比較。

175/197

左が方針3、右が方針4

シード16の比較。

206/221

左が方針3、右が方針4

良くなったサンプルを比較してみる。

シード1の比較。

306/1120

左が方針3、右が方針4

シード18の比較。

368/1028

左が方針3、右が方針4

他にも比較したが割愛。

比較してわかったのが、 (アイテムのソートで使ったクエリ回数)/(全クエリ回数)の値が大きい （＝アイテムのソート後に残ったクエリ回数が少ない）と、グループのソートに使えるクエリ回数が少なすぎて方針3より悪いスコアになってしまうらしいということ。

つまり残りクエリ回数が十分にあるときだけグループのクイックソートをしていたつもりが、まだまだ全然足りなかったということらしい。

残りクエリ回数がQ/2以上のときだけグループのクイックソートをするように変更した。

提出コード：https://atcoder.jp/contests/ahc025/submissions/46748977

得点：543,035,466

方針3よりスコアが良くなった。

上記の方針5では、方針3よりサンプル100個中、

  • 5個スコアが悪くなった
  • 31個スコアが改善された
  • 64個はスコアが変わらなかった

方針6：残りクエリ回数に応じて確率的にグループの重さが切り替わるようなアイテム交換を許す

方針5では、64個はスコアが変わらないのであった。これは、アイテムのソート後に残りクエリ回数が少ないので方針3に切り替わった個数が64個ということであった。

方針3の問題点はなんだろうかと、いくつか悪いスコアのものをピックアップしてみた。

seed62: 157/185

シード62の結果

seed66: 438/482

シード66の結果

ビジュアライザを動かしてみると、残りクエリ回数が少ないときにもグループ間の重さが入れ替わるような重いアイテムの交換を許してしまっていた。

残りクエリ回数がまだ残ってるときはグループの重さが入れ替わってもいいが、残りクエリ回数が少ないときはグループの重さが入れ替わるようなことはせず、軽いアイテムのやりとりだけで済ましてほしい。イメージ的には『安定』したやりとりをしてほしいという欲求がある。

なので、残りクエリ回数に応じて確率的にグループの重さが切り替わるようなアイテム交換を許す実装をした。気持ち的には焼き鈍し法である。

方針7のシード62の結果

方針7のシード66の結果

かなり良くなった感じがしたので、提出した。

提出コード：https://atcoder.jp/contests/ahc025/submissions/46841307

得点：492,973,943

最終結果

方針6を最終結果として提出した。

A：58,654,377,877

A-Final：300,672,027,666

順位：458

ここまでの感想

  • 方針5を実装した時点での相対スコアが62Gで、順位は380位くらいだった。この得点帯は激戦区で、寝て起きたら順位が結構下がっている。
  • 方針5を実装した時点で頭打ちしてると思ったのだが、上位陣が90Gで途方もなかった
  • 「山登り、焼きなまし、ビームサーチは絶対にできないよな」「いやしかし…」とぐるぐる考えてた
  • 方針6は発想としてはかなり焼き鈍し法なのだが、これに至るまでかなり時間を要した。

公式解説

公式解説動画のリンク

X（Twitter）で調べると強い人はソートして一番重いものと一番軽いものを交換している人が多いイメージ。似たようなことは自分もしているのだが、自分の解法では一番重いやつと軽いやつを交換、2番目に重いやつと軽いやつを交換、…としていたのが良くなかったのか？

公式解説の動画を見てみる。

  • 解法1：クエリを使ってがんばって重さを推測する。その後クエリを使わずに最適化問題を解く
  • 解法2：焼きなまし法（近傍解を求めて、その近傍解が良くなったら採用。悪くなったら悪くなった度合いに応じて確率的に採用）は、今回の天秤を使ったクエリでは「どれだけ悪くなった」かがわからないので難しい（「悪くなった」はわかるが「どれだけ悪くなったか」はわからない）。が、「良くなった」のは判定できるので、山登り法が可能
    • 初期解を適当に作って、山登り法をする
  • 解法3：初期解を貪欲法で作る

公式解説では解法2の山登りを解説してくれた。

山登り法

2つのグループ間でアイテム交換をするの図（公式解説動画から引用）

2つのグループの大小関係がわかっている状態で、アイテム交換をする。アイテム交換後、2つのグループの大小関係が変わっていなかったら、「スコアが良くなった」といえる（2つのグループ間の分散が小さくなっているので）。

基本的にはこれをひたすら山登っていけばいい。

この解法のシンプルな手法ではソートすら必要なくて、アイテムをランダムに1個選び、それをどこのグループに入れるかもランダムに選ぶ。アイテム交換してスコアが良くなるなら交換し、スコアが良くならないなら交換しない。

初期解は各グループ同じアイテムの個数になるように適当に割り振る。

これをすると321位がとれるらしい。

うーーーーーーーーーん。シンプルな解法に見えるが、これでも十分自分より良い点数が取れるところを見ると、考察力が足りないと感じる。やってることは「言われてみれば当然といえば当然」のことなのだが、思いついてないんだよなぁ。

アイテム交換方法2

もうひとつのアイテム交換方法として、グループAとグループBからそれぞれアイテムを1個ずつ取り出して、取り出したアイテムをアイテムa、アイテムbとする。

このとき、「グループA < グループB」「アイテムa < アイテムb」ならば、アイテムaはグループBに入れ、アイテムbはグループAに入れるとスコアが良くなる。

アイテムaはグループBに、アイテムbはグループAに入れるのが良い

このようなアイテム交換はクエリ2回の発行で行える。

「この交換法も50%の確率でする」みたいに組み合わせると218位に入れるらしい。

キャッシュする + 推移律のグラフを作る

一度した交換方法はキャッシュして覚えて、2回もしないようにすると地味に良くなる。

アイテム交換方法2をすると、アイテムの大小関係のデータが蓄積していく。

a < b のような大小関係のグラフを作っておくと、a < b と b < c => a < c のように、クエリを発行しなくても推移律で新たに大小関係が判明する。

推移律からa < cを導く

もっとやろうと思えば以下のように導くこともできる。

a<b と b+c<d から、a+c < d も判明する

こういう不等式系がたくさんあったときにすべて満たす解を求める方法にLP（線形計画法）があるらしい。

それをしなくても「アイテムa+cとアイテムdの交換」といった複数個の交換が可能になる。

これを実装すると200位になる。

グループのソートを実装する

これまでの方法の問題点は、交換するグループをランダムに選んでいたのが問題であった。

そこでグループのソートを実装すると、どのグループがアイテムを交換すべきなのかがわかる。

一番重いグループと一番軽いグループがアイテム交換するのが良い

アイテム交換後のグループのソートは単純にやればO(DlogD)。けどこれは以下のようにして改善できる。

一番重いグループをグループA、一番軽いグループをグループBとする。アイテム交換後、グループAとグループB以外の他のグループはソート済みなので、「グループA（B）は、ソート済みのグループのどこに入るか」を2分探索すればO(logD)で済む。確かに……。

これをすると49位になる。

公式解説の感想

  • 公式解説を見ると、「なぜこれが思いつかなかったのか……」といった感想になった。ソートなどそれっぽいことは思いついて実装できているのだが、初期の解法の土台が良くないのでスコアが伸びなかった印象。論理的な道筋が見えていないのというか。練度が足りない。

AHC024 参加記録

概要

丸紅プログラミングコンテスト2023（AtCoder Heuristic Contest 024）に参加しました。4時間の短期間コンテストでした。

ほぼ何もできなかったといってもいい。

最初の方針

連結成分をノード、「隣接する」というのを辺と考えるとグラフができるので、そのグラフからグリッドを作ろうと思いましたが、実装が大変で2時間経過。スジが悪いと思い直してビジュアライザをいじっていると、与えられたグリッドを白に塗っていくのほうが実装が簡単なことに気づきました。

かなりバグ散らかしつつ終了10分前くらいにかなりナイーブな貪欲ができたのでそれを提出。終了です。

atcoder.jp

seed0のビジュアライザ

白に塗れるところは貪欲に白に塗っていく。

真ん中あたりのエリアが大きいですね。これらを隣接条件等を崩さないように圧縮していければなあと思いつつ終了しました。あと4時間ほしい。

上手い人の解法

中心に寄せる貪欲らしいです。貪欲でもここまでいけるらしい。

https://twitter.com/Jiro_tech15/status/1705889677910348053

左上に寄せていき、最後にぎゅっと圧縮する手法。おお、と思いました。AHC系は「はしっこに寄せる」という発想はよく見る気がします。

消せる行や列を消すという発想。「隣接条件を崩さずにどう圧縮するか」というのを考えたとき、たしかに「1行ごっそり消せるなら消す」というのは実装ラクそう。天才や……

反省

AHCやることメモに「まずビジュアライザをいじる」って書いてあるだろ。なぜそれをしないんだ。

短時間コンテストは実装のしやすさ・速さがかなり重要だと感じました。

あと最近、C++でクラスを書くときはメンバ変数にm_のプレフィックスをつけているのだがいい感じ。メンバにアクセスするときは通常this->を使うと思うのだが、長いのがやだ。

Chromeでデベロッパーツールを開くとwasmが遅くなる現象

WebAssembly

概要

wasm生成の練習のため、実践Rustプログラミング入門を参考にしてマンデルブロ集合の計算のwasmとjsで速度比較するWebページを作成しました。

taketakeyyy.github.io

しかし開発中、wasmの速度が遅くなったり速くなったりする挙動に悩まされました。色々調べた結果、Chromeでデベロッパーツールを開いているか否かが原因だったようです。

比較

デベロッパーツールを開いてない状態

デベロッパーツールを開いている状態

なんでこうなるのか全くわかっていません🤷後述追記した。

この現象はlocalhostや本番環境関係なく発生しています。

デベロッパツールを開いてconsole.logで時間計測する際には注意が必要になりそうです。

「wasm　遅い」で検索すると色々出てきますが、こういうのも原因のひとつになっているんじゃないかと思いました。

2023/09/21 0:56 追記

Twitter(X)でご指摘いただきました。ありがとうございます。

nmi.jp

Chrome において、DevTools をただ開くと wasm の実行が極めて遅くなる現象が確認されております。これはバグではなくて仕様なのですが、結構複雑な仕様で、

DevTools を開くと TurboFan の最適化がキャンセルされて遅くなる しかし Profile タブで Profile を取るときには再度 TurboFan の最適化が適用される という挙動になっております。Chrome では、ただ DevTools を開いているだけで wasm の実行がかなり遅くなります。大変気づきにくいトリガーなので、wasm 系の開発をされる時にはお気をつけください。

そういう仕様らしいです。

その他