自分の将棋思考アルゴリズム、間違ってないか？

将棋

はじめに

要旨

将棋、実は思考アルゴリズムや認知の方法が悪いと大損するのでは？自分の考えを書くので、皆さんどう考えているのか、気づいた点など教えてください。

エピソード

将棋を指していると、子供の指し手の速さに驚かされます。本当に考えているのか？と思えるぐらい。自分だと例えば「こう指したら、相手はこう来て…」と3手先まで読み、それぞれの局面で2通りの応手を考えるとします。計算すると、

  • 初手：2通り
  • 2手目：2×2＝4通り
  • 3手目：2×2×2＝8通り
  • 合計 14通り

1手を1秒で読むとしても14秒かかります。しかし、子供はもちろん、将棋ウォーズなどオンライン対局では、多くの人が10秒未満で指してくるのです。もちろん、定跡やパターンを知っていたり、良い手を自然に選べる感覚（評価関数的な直感）を持っていたりすることで、読む手数自体を減らしているのでしょう。それでも、この速さはやはり不思議です。

仮説

振り返ると、自分も思考方法を少し変えるだけで効率が良くなった経験があります。そこで、こんな疑問が湧きました。

  • 実は自分だけ、変な思考アルゴリズムで考えているのでは？
  • 子どもが速く指せるのは、そもそも考え方が根本的に違うのでは？
  • 人間はコンピュータより処理速度が遅いのに、コンピュータのような総当たり（brute force）的な読み方をすると損では？
  • 認知の方法次第で、上達速度も大きく変わるのでは？

しかも、自分の思考アルゴリズムが効率悪いことには、なかなか気づきにくいです。ざっくばらんと将棋に関することをどう考えているのか言語化してみるので、みなさんもどう考えているのか教えてほしいです。

将棋ネタいろいろ

  • 「２級」「初段」「現在（二段）」という表記で、その時期にどう考えていたかのかを分けて書いたもの。将棋ウォーズ基準。
  • 競プロ×将棋の方々向けに書いたので、ところどころで、プログラミング用語を使用しています。

【１】詰み判定

以下の詰みの局面を例に挙げます。

２級

下図のように王手がかかると相手の玉が⇒の方向に逃げるので、全ての逃げ方を考え逃げても捕まるから詰みということをチェックしてました。

  • アルゴリズム：相手玉の周囲９マスそれぞれについて、「自分の駒が利き範囲」にいるかを判定する。
  • 計算回数：９マス×近隣の自分の駒数×駒の利きマス数


初段

ある日、今の方法では遅いのではと気づき、以下のようになりました。

  • アルゴリズム：相手玉の周囲９マスが、「自分の駒の利き範囲」で埋まっているかを判定する
  • 計算回数： 近隣の自分の駒数×駒の利きマス数

例えば以下の図面では、馬の利きが赤色マス、銀の利きが青色マス、歩の利きが緑色のマスで、相手玉の周囲がいずれかの色で塗られています。このイメージです。
これで９倍高速化しました！（今までが他人の9倍遅かったともいえますが…）
ただ、実際テトリスのようにピースを組み合わせた図をイメージするのは、たまに１マス抜けていたりしてスルっと逃げられることはありました…。

現在（二段）

周囲９マスを埋める判定なのですが、ただ、将棋では利きに隙間がないのは良型として知られているようなので、そういう複数のピースは最初からひとかたまりだと思ってイメージするようにしました。これで雑にイメージしても、「この辺は隙間はないな」と考えられるようになり、ちょっと楽になりました。


あと、詰将棋を解いていると、隙間なく効率よく埋められる組合せはよく出てくる気がします（例：「角＋金」「飛車＋銀」「角＋角（筋違い）」「桂＋桂（筋違い）」）。

実際、詰み判定でひと固まりピース判定が有効なケースは多くはないのですが、似た判定で「自陣に打ち込まれないか判定」もあります。この場合定数倍の部分が９マスから２７マスになるのでより有効です。（自陣のすべてのマスに駒が利いているかは将棋では重要で、これにより相手の駒の打ち込みによる攻撃を一方的に遅らせることができます。）

【２】動けない合い駒

以下の場面で何も警戒せず

ポロっと金を取られたことが何度あったことか…。銀で相手の馬を取り返すことはできません…。

王が相手の飛車・角・香車で睨まれているときは、間の駒は「何も書いてない、"どこにも動けない駒"」とイメージすることで、若干見えやすくなった気がしますが、上記のような典型ケース以外では未だにミスします。皆さんどうしてるんでしょう。

【３】速度計算

将棋では、あと手番が何回きたら自玉や相手玉が詰むかを考えて、攻めか受けか適切な手法を選んだりします。どっちが速いか読むことを「速度計算」と呼びます。

２級

「詰ませるのよりも、詰めろをかけ続けることが大事だ」というのを聞いていたものの、なぜかは理解できず。

初段

何かで速度計算に関する記事をみたときに、これはターン戦闘型RPGで、

RPG 将棋
HP 3 ２手スキ
HP 2 詰めろ（１手スキ）
HP 1 詰み
HP 0 王が取られた状態

双方ともに、

  • 攻撃（相手HP-1）
  • 回復魔法（自分HP+1）

を使える。また、条件が揃うと、

  • ドレイン攻撃（＝詰めろ逃れの詰めろ）（相手HP-1 自分HP+1）
  • 死の宣告（＝必至）（相手は回復できない）

も使えます。

最初の例の「詰ませるのよりも、詰めろをかけ続けることが大事だ」は、「相手のHP2だったら、こちらは攻撃してれば、相手は次ターン回復魔法を使うしかないので、自分は安全。ずっと自分の攻撃ターン」と同じなんだと理解。

と謎の例えを書いたのですが、YouTubeをみたら全く同じ方法で理解をされている人がいたので、こちらを観た方が絶対分かりやすいです。

www.youtube.com
カードゲームでも同様の概念を表す用語があるらしい（けど忘れた）

現在（二段）（というか悩んでる点）

速度計算のフローチャートは、以下のようになっています。

  • ①相手玉が詰むか？
    • 相手のHPが「1」に相当する状態。
      • → YESなら即攻撃して勝ち。
      • → NOなら②へ。
  • ②自玉が詰むか？
    • 自分のHPが「1」に相当する状態。
      • → YESなら回復魔法＝受けの手を選ぶ。
      • → NOなら③へ。
  • ③詰めろや必至をかけられるか？
  • 相手のHPを「1」に追い込めるかを検討。

アルゴリズム的に無駄がないのは、①→②→③の順ですが、自分も①→②→③で考えていますが、これが最適か？というと、少し疑問が残ります。どっかの将棋本で②を一番先に考えるという例は見たことがあります。詰みが難しい場合は③が一番先もありそう。皆さんはどの順で考えているのでしょう？？

あと、これってうまくモデル化できれば自分にとって最適な考え方が決まりそうな気もします。

  • {読みの詰む・詰まない}x{実際詰む・詰まない}の全4パターンの確率関数
    • 読む時間をかければかけるほど精度があがる、詰みまでの手数が長いと精度が下がるので、その2変数の関数になりそう
  • それぞれの場面の価値（勝ち、すっぽぬけなど）

これらは棋譜から測定できると思うので、人によって最適な思考順が計算できれば面白いと思います。
まぁでも、長期的に上達のことを考えたら、①→②→③で考えよ！と一蹴されそう…。

【４】詰将棋

詰将棋は、詰めチャレでいまだに初段～二段で、たぶん同棋力の人に比べてだいぶ苦手です…

２級

深さ優先探索か最良優先探索をしているだけです。

ただし、自分の場合、深さは３手ぐらいで打ち切られる。

現在（二段）

思考アルゴリズムの進歩がない…。上記の探索に加えて、

  • 一旦詰まそうとして詰まなかった場合に「もし、ここに駒が利いてたら、詰んでたのに…」と分かるので、次の探索時に考慮する。
  • ぜったいに詰まない形（ゼット）の知識
  • どの本にも共通して載っている非常に基礎的な詰み型の知識

一般的には、「詰将棋は答えをすぐ見て良い。３手詰等の短い手数の詰将棋を、丸暗記して、数秒で解けるようにする」のが良いとされています（アルゴリズムでいうとメモ化 - Wikipedia？）。ただ、この暗記が全くできる気がせず、結局毎回最初から考えるので、いまだに３手詰でも２０秒程度はかかります。よほど映像記憶力が強い人でないと、答えを見て丸暗記はかえって難しいのではと思える…。
ただ将棋強い人に聞くと「詰みを読むとき、途中の手をスキップすることがある。」と聞いたこともあるので、メモ化が効いているのでしょう。

また、「詰み形から逆算することがある。」というのも聞いたことがあります。総合すると両端からの探索が最強なアルゴリズムな気がします。

  • 初手から（正方向）で見ると分岐が少ない
    • 正方向からの深さ優先探索
  • 詰み側から（逆方向）で見ると分岐が少ない
    • 逆方向からの深さ優先探索
  • 正方向でも逆方向でも、中間に分岐が多い
    • 両端からの探索

がベストな方法に思えます。ただ、人間がやるには非常にやりづらそう…。皆さんはどう考えているのでしょう？

【５】手番

手番は将棋用語としてすでに２種類ある。
手番 - 将棋用語説明｜将棋講座ドットコム

２級
手番の意味１：対局者のうち、次に手を指す方。

例えば、

初段

初段ぐらいからは以下のイメージになってます。

手番の意味２：その局面において先に攻めることができるか否か

手番の意味２は、連続する手番の集合で、相手玉が受けざるを得ない状況、飛車・角等が追い回されて逃げざるを得ない状況などでは、攻め方が自由な手を指し続けることができる。つまり「ずっと俺のターン！」が発動します。手番を握っているともいいます。詰めろ・２手スキなども意味２の手番でカウントしますね。

他のゲームでも同じ手番の概念はあるようですが、自分は知りませんでした…。知ってるのと知らないのとで+0.5級分ぐらいの価値があるので、将棋習いたての時点で知っておきたかったです。

【６】攻めるときは一気に詰ませるのが最善

将棋のゲームの特徴、持ち駒に関連した話。

２級

中途半端に攻めて相手の守りが少し崩れるものの、こちらの攻めは一旦途切れる。駒不足なので、また駒を増やして攻めようとするものも、相手に反撃をくらう。

現在（二段）

将棋の持ち駒には以下の特徴があります。防御力ダウンすると攻撃力アップする怖いゲームです！

  • 盤上の駒が持ち駒になる⇒攻撃力アップ
  • 駒交換⇒双方の攻撃力アップ
  • 敵陣でも自陣でも崩れるときは駒交換がされる⇒防御力ダウンすると攻撃力アップ

こういうルールのゲームは将棋以外でも、カードゲームや私の好きな三国志大戦でもあるのですが…。終盤で攻め開始したら一気に詰ませないと、詰ませられなかったときは相手の攻撃力が上がっているので、逆転負けのリスクが高まります。

（もちろん攻めながら駒をぽろぽろ拾えるケースはいいのですが、ここでは考えてない）

【７】王の早逃げ

将棋の格言に「王の早逃げ八手の得」というのは知っていたけど、さすがに八手の得はしない。

２級

戦うか逃げるかの判断基準がなく、囲いが崩れる前に逃げて普通に捕まる。早く逃げすぎ。

現在（二段）

たぶん、敵の駒が集中していてるときほど、早逃げが有効な気がする。ファイアーエムブレムなどのシミュレーションゲームとは違って、１ターンに動かせるのは１つだけ。ゆえに、敵の攻め駒が複数あったとして、そこから王が逃げても、相手は全部の駒が追いついてくることは不可能。ゆえに得。

仮想局面。4枚香車が自陣を破っても、王将を追いかけるのは移動回数×4手かかるので、逃げ得。

【８】進展性・理想形・手待ち

囲いについては手数をかけるほど基本的には固くなる。ただ種類によって、短手数で囲えるものがあったり、分岐があったりするので、またその成長曲線のようなものをイメージしています。銀冠のように一瞬隙が生まれて薄くなることもあるので、相手より差が開いているタイミングで仕掛けるのが基本良い。いろんな分岐があったり、時間が経つと強くなったりする囲いもある。進展性がある囲いと言ったりもする

ただ、自分も相手も仕掛けられないと、いずれ膠着状態になる。戦闘開始前の強さの最大、ベストな配置のことを「理想形」と呼ばれています。

で、将棋はパスできないゲームなので、この最大値に到達した次の手が難しい。基本マイナスの手になってしまう。少しのマイナスで済む手がさせればいいものの、実は「手待ち」するための手段はいろいろ知ってないとまずく、手待ちの手のはずが隙ができて大きなマイナスになったり、中途半端にこちらから仕掛けざるを得ない状況になって不利になることがある。

これについては、将棋を始めた時になぜか教えていただいて、その時はよく分かっていなかったです。

【９】手番の価値

２級

例：歩の突き捨てや叩きの歩
飛車道などを通すためのは理解できても、それ以外のケースは端に相手が得するだけの手に見える
また序盤から中盤にかけたあたりで行われる理由も分からず。

初段

手番の価値が、序盤はほとんどなく、終盤は+∞になるということに気付く。

イメージですが、基本、歩の突き捨てや叩きの歩は、

  • 相手が歩を取ると 相手 +10、手番は自分のまま。
  • 相手が歩を無視すると 相手 -500になるが、手番は相手にとられる。

ぐらいなので、序盤はまぁ無難に取られてしまいます。ただ、中盤・終盤になると、無視したほうが良い場面も出てきます。
せっかく良い叩きの歩でも、終盤なのでそのまま無視されて負けるということが理解。また、突き捨てなどは、早すぎるとただの損で、遅すぎても無視されて負けることもあるというのを学ぶ。

二段

初段からかわらず。明確な判断基準もなく、なんとなく指してます…

【１０】勝利条件

２級

通常の詰み以外に、入玉でも勝てるということを知る。

初段

さらに、「相手の攻めが切れるのも、ほぼ勝利」というのも知る（競プロ将棋大会で三段の方と戦って、相手が自陣飛車で完全に切らされて覚えた）
相手の攻め駒が３枚以下になると、自陣が薄くない限り攻めが切れる可能性がでてくるので、攻めを切らす手もたまに指すようになってきます。

現在（二段）

初段のころから変わらず…。攻めが切れるか？により良い判定があるのかも。

その他ネタ

２箇所以上で駒がぶつかった場合に、どちらからとるべきか・無視するべきか？

２択に見えますが、無視もありますし、相手の手番もいろいろあるので分岐が何気に多いので、よくミスります。
結局全パターンを試すしかないのか…。ただ、取ったり取られたりの際に王手もかかるときは相手は無視できないので、そちらを優先することが多いです。

AHC (AtCoder Heuristic Contest) 攻略法をレッドコーダーにインタビュー

AtCoder マラソンマッチ TopCoder 競技プログラミング

はじめに

2025/12/13に開催されたAtCoder Conference 2025で、ゲストスピーカーとして発表を行いました。お越しくださった皆様ありがとうございます！ speakerdeck.com 発表後半で、AHCレッドコーダーにインタビューした内容を紹介したのですが、当日発表できなかった部分でも多くの素晴らしい知見があったので、公開します。

回答にご協力いただいた方々

本当にありがとうございます！（ちなみに、日本橋ハーフマラソンの懇親会で近くのテーブルにいた皆さまにお願いしました。）

saharanさん

  • AHCレーティング 3360 世界1位
  • 現在世界最強の方です。AWTF 2025 世界4位。AHC優勝4回。ハル研プロコン等で活躍されてましたが、最近は強さが極まっています。競プロ以外のCGシミュレーション分野の趣味プログラミングでも有名な方です。
  • AtCoder, X(twitter), おいもログ | shr's tech diary

montplusaさん

tomerunさん

  • AHCレーティング 2839 世界27位
  • TopCoder Open Marathonの決勝に5回出場。ベテランのヒューリスティック第一人者です。AHC以前から「日本橋ハーフマラソン」も開催しており、コミュニティへの貢献も素晴らしい方です。
  • AtCoder, X(twitter), TopCoderの学習のお時間

simanさん

  • AHCレーティング 2810 世界33位
  • TopCoder Open Marathonの決勝に2回出場、また、ゲームAIコンテストでも長年活躍しており、CodinGameでも優勝経験があります。
  • AtCoder, X(twitter), simanのブログ, scorerun

質問集

質問1.
AHCで貪欲法が重要とされていますが、攻略の定型化は難しいと考えています。貪欲法を使用する際に、意識している点や工夫している点はありますか？


saharan
「どの要素を簡略化するか」というのが難しく、いつも注意して考えるようにしていますが、しばしば失敗します。また、いきなり賢い貪欲法を書こうとせず、まずはすごく単純なものを書いてみて、ビジュアライザで挙動を観察しながら次はどこに手を付けるとよさそうかというのを考えるようにしています。あとは、「焼けそう！」と思ってももう少し我慢して貪欲を考える、というのを意識するようにしています。

montplusa
（ここでは、少なくとも何らかの評価関数が後ろで見え隠れしているタイプの貪欲法について書いています） 最適化問題を考えたとき、最小化・最大化したい指標に対してまさしく"貪欲に"採用するようなアルゴリズムが一番最初に思いつきますが、その後に将来的にツケが回ってくるような要素があればその分評価を減衰させて評価するというような構造にできないか考えます。 例として、「魔法使いがボスとの戦闘を終えるのにかかるターン数を最小化する」みたいな問題を考えると、1ターンのダメージを最大化したくなりますが、MP消費が激しい魔法では後半でMPが枯渇して失速してしまうので、制約によってはMPの効率を意識したほうがよかったりします。

tomerun
貪欲というと目先の利益だけで動いていくという印象がありますが、そうならないよう、あくまで理想的な状態を考えてそれに近付いていけるような方法を考えます。

siman
自分は貪欲法が得意とは言えませんが、takapt さんが書かれていた「確実に前進」という指針は今でも強く意識しています。

「Topcoderマラソンマッチの探索問題で重要なこと」 https://qiita.com/takapt0226/items/b2f6d1d77a034b529e21

普段はまず、その盤面から打てる合法手をすべてピックアップし、その中から「この手を打つと確実にスコアが上がる（もしくは悪化しない）」ものを探す、という考え方でやっています。ただ、これはやってみるとかなり難しいです。

貪欲法は本質的に「常に良い状態を選び続ける」手法なので「一時的には盤面が弱く見えるけれど、最終的にはそのほうが良くなる手」の評価がとても難しくなります。そういうケースでは、1 手進めたうえで、その評価関数の中でさらに「N 手ぶん簡易シミュレーションしてみる」といった工夫を入れることもあります。ただし、このやり方だと 1 手あたりの評価コストが重くなってしまうので、「もっと軽量な近似評価でうまく代用できないか？」といつも悩んでいます。

自分の中で、貪欲法における基本的な評価関数のイメージは 問題のスコア + 良い特徴量 - 悪い特徴量 という形です。そして、この「良い特徴量」と「悪い特徴量」にどれだけ気づけるかが、貪欲の強さを大きく左右すると思っています。とはいえ、何が良くて何が悪いのかを判断するのは簡単ではなく、結局はいつもビジュアライザとにらめっこしながら試行錯誤しています。

盤面状態に関するあらゆる情報を可視化しておき、「どのような状態になっていれば良いのか」を考察しやすい環境を作ることが大事だと感じています。AHC は標準のビジュアライザがよくできているので、それをそのまま使うだけでも十分に考察はできますが、生成 AI がある現在では、独自のビジュアライザを用意しつつ、問題のコアな部分を理解・抽出するための可視化の重要度が、以前にも増して高くなっているのではないかと感じています。

質問2.
焼きなまし法・ビームサーチなどの定番アルゴリズムで、他の人とは違った工夫をしている点はありますか？


saharan
ビームサーチでは、差分更新ビームサーチ (Euler tour beam search) を使うことで、今考えている問題（保持すべき状態が大きい）にビームサーチが適用できるようにならないかというのを必ず考えるようにしています。焼きなまし法では、これといった一般的な工夫は特にしていません。問題ごとのスコアの差分計算や近傍の質が全ての鍵を握っている印象です。

montplusa
ビームサーチでは、高度化する前は必ず評価値計算ののちに小さめの乱数成分を乗せるようにしています。というのも、次候補の評価値に大きな団子地帯があると、それにわずかに及ばなかった実はよい候補が淘汰されてしまい、似たような団子地帯の候補ばかりが残るという現象が起きます。実装初期はこの現象によりビームサーチの効果があまり実感できないことが多く、誤って「方針に見込みがない」と方針を捨ててしまわないようにしています。実装を詰めていくといわゆる重複盤面の除去や評価関数の改善などにより、段階的にタイブレーク+α程度に影響力を下げていっている記憶があります。

tomerun
ライブラリ化をしない（極限まで最適化をしようとすると結局全体に手を入れることになるので）（ほとんど整備をサボっていることの言い訳です…）

siman
焼きなまし法はそんなに得意ではないので他の人と異なる工夫はあまり無いかもしれません。 近傍はなるべく小さく、差分計算が可能なものを考える（イテレーションの回数を増やすため）

ビームサーチはとにかく「評価関数」と「多様性」が大事だと思っていて、重複排除のためのハッシュ関数をいい感じに設計したりとかは頑張っているかもしれません。 「評価関数」は結局、貪欲の強さみたいなところがあるので Q1の話と近いところがありますが、とにかくビジュアライザを見ながら「良い状態」とはみたいなことをずっと考えています。一応木上のビームサーチとかは手元に持っていますがここだけで差がつくみたいなことはあまり無い気がします。

質問3.
AHCで、技術的に未開拓だと感じる領域や、現状の手法では攻略しきれていない問題タイプはありますか？


saharan
参加者のレベルがとても高いので、コンテストで出された問題は概ね制約の範囲内では攻略されていると感じます。技術的には、SIMD にとどまらずマルチコアを扱うような問題や、GPU が利用可能な環境での問題が未開拓な領域だと感じています。あとは、実業務でありがちな、入出力や問題の制約が最初からは完全に決まっておらず、様々な要素や要求を考慮して最適化問題に落とし込んでいくパートなどがありますが、これはコンテストとして出題するのは非常に難しそうです。

montplusa
（質問の意図を間違えていたらすみません） AHCは競技性・楽しさの観点から極端に大きなインスタンスの問題は出ない気がしています（アルゴではよくある106サイズなど）。インスタンスが大きくなると焼きなまし相対的に少し使いにくそうだなあという印象があり、計算資源が圧倒的に足りない中での最適化みたいなところはあまり知見が集まっていない気がします。（そもそも貪欲法しかなくなってしまうのかもしれませんが）

（余談ですが、以前ABCにヒューリスティックコンテストで使っている自前の入出力テンプレートで挑んだら入力長が想定より長くREになったことがあります。完全に意識の外だったので原因特定に時間をかけつつ2ペナしました。それくらいAHCのインスタンスは小さめです）

tomerun

  • 多目的最適化：単にスコア関数が複数の要素を含むのではなく、それら複数の要素間の相対的な重要度に対応する複数の出力を提案するような形式
  • 対戦相手が存在するようなゲーム

siman
どうしても時間制約が 2-3secになるので、長時間計算が必要となりそうな大規模な問題はあまり開拓されていないのかなと思っています。 短時間だとどうしても「焼きなまし」「ビームサーチ(貪欲)」が強くなる印象なので、もっと時間制約を緩めることで新たな手法が有効になってくるのかなと思っています。（例えば機械学習とか）

質問4.
調整・検証のために使っている環境・ツールは何がありますか？ （例：可視化／ログ／テスト／ハイパーパラメータ調整 など）


saharan
ビジュアライザ： 自作の汎用ビジュアライザを利用しています。ソースコード中に描画命令（この色でここに円を描け、など）を埋め込む形式で、結果の可視化のみならず焼きなましの過程やデバッグ作業にも役立っています。

テスト： テスト環境も自作のものを利用しています。相対スコアの表示、テストケースの特性に合わせた結果の絞り込みやグラフ表示、複数提出の詳細な比較などが特に重要な機能です。

プロファイラ： プログラムは WSL 上で開発しているのですが、プロファイラだけは Visual Studio のものを使っています。ボトルネックを絞り込むのに重宝しています。これのために、Windows 上でもコンパイルできるようなコードにしてあります。

ハイパーパラメータ調整： Optuna を使うことがあります。が、多くの場合手動による調整で済ませます。これは、「良い」パラメータを設計できた場合、スコアはそれらのパラメータに対して単峰な振る舞いをすることがほとんどで、高度なアルゴリズムを使ってパラメータを探索するよりも、座標降下法などの単純な方法で一つずつチューニングしていった方が効率が良いためです。とはいえ、設定すれば寝ている間にパラメータを見つけてくれるのは嬉しいので、終盤の立ち回りに合わせて臨機応変に戦略を考えるようにしています。

ログ・デバッグ： いろんな場所に assert を仕込みまくっています。このとき、条件が破られた場合、単に失敗したと表示するだけでなく、どの式がどの値を取ったかをログに出すようにしています。

montplusa
普段はpahcer(terry_u16さん、githubにあり)を利用しています。より詳細な時間計測・比較をしたい場合はローカルジャッジを自作して1000ケースほど回し、ahc詳細順位表(wataさん、終了した長期コンテストの解説にあり)をローカルで使用しています。

tomerun
https://topcoder-tomerun.hatenablog.jp/entry/2024/04/06/201915 これです

siman
可視化: 生成AIに作ってもらいます ログ: 各テストケースのログは自前で用意しています(スコア、各種パラメーターが TSV形式で出力される） テスト: 自前の並列テストがあります。マルチプロセスで動作するので、他のテストの影響を受けにくい構成になっていると思います。 パラメーター調整: optunaで調整はするときもありますが、上位争いしている時にしかほぼ使わないです。（なので最近使った記憶が。。。）

質問5.
AIを使用していますか？使っている場合、どのような用途で活用していますか？


saharan
GitHub Copilot による補完を多用しています。また、簡単ではあるが書くのが面倒なアルゴリズムを素早く書かせたり、SIMD を利用した高速化のために ChatGPT や Claude を利用しています。たまにアイデアを出させることがありますが、もっぱら長期では役に立ちません。

montplusa
かなり利用しています。 自分で問題から最適化したい部分問題を切り出し、部分問題を解く関数を書いてもらっています。AIが書く最適化は、「それらしいふんわりした解」を出力する印象があり、一番核となる最適化部分は自分が実装することになりがちです。 ビジュアライザや手動で何かを試せるようなツールを頼んだり、ローカルジャッジを代わりに作成してもらったりということも最近は結構あります。

tomerun
デバッグの効率化

siman
コンテスト外であれば「上位入賞者のコード解説」とかで使用しています。

コンテスト中であれば「長期」はスコア解析ツールの作成や、独自ビジュアライザの作成。方針の一部で必要な関数の実装の肩代わり。戦略の壁打ち役等々、生成AIとチームを組んでいる感覚でタスクを依頼しています。 ジャッジコードを読ませることで、問題文に対してより細かい質問とかを答えられるようになるので問題理解の役にもたったりします。

質問6.
コンテスト終了後は、どのように復習していますか？


saharan
流れてきた解法を見たり、上位の人のコードを読んで方針を理解する、などをしています。特に「それは思い付かなかった」という重要な考察が流れてきた場合は、

  • なぜ思いつかなかったのか
  • どういう思考過程を経ればその方針に辿り着けたか
  • 賢い解法だが、これは思い付けなくても仕方ないものなのか

などを分析します。

montplusa
コンテスト後にTwitterで大量の情報が飛び交うので、その時にしっかりと他の解法を見ています。近い点数の人が実は違う解法だったり、あきらめた解法ができている人がいたりするので学びは大きいと感じています。

tomerun
復習は特にしていません…（しなくて良いという意味ではないです） 復習よりかは、開催されているコンテストに出たいですからね

siman
基本的には上位入賞者の解法を見ながら復習しています。昨今は生成AIのお陰でコードを読んでもらって細かい部分の解説とかも出来るようになっているので便利です。 復習する場合は短期コンの問題をオススメします。長期コンに比べると問題もシンプルで解法も比較的シンプルになりやすいので、そこまで時間をかけずに上位のスコアを獲得することが出来ると思います。

質問7.
アルゴリズム以外で、AHC攻略に役立つと感じていることは何ですか？ （例：問題解決の進め方／思考プロセス／参加環境／体調管理 など）


saharan
ビジュアライザをよく観察する、難しいことをしようとしない、試行と改善のサイクルを短くするよう心掛ける、長い時間をかけて「最強の方針」を一度に組み立てようとしない、風呂で考える、常に 1 位を倒すことを考える、などが重要であると感じています。

montplusa
コンテスト中に気持ちを切り替える瞬間が多いと、アイデアが来やすい気がします。学業・仕事に打ち込むとか、小さなことでいえば風呂・トイレに行くなどでもかなりアイデアが来やすいです。

tomerun
重そうな実装を始める気合 情報の可視化 常に頭の中に問題のことを置いておくという点での集中力

siman
メタ戦略的な部分はありますが「逆算力」は大事だと思っていて「今1位の点数がこれぐらいか」→「つまりこの点数を取るには 1ターンにこれぐらいスコアを取る必要があって or 1ケースあたりのスコアはこれぐらいになっているはずで」→「それを達成するためには◯◯が必要で〜」みたいな感じで、上位のスコアから戦略を逆算することで割と上位者のやっていることみたいなのがわかったりすることがあります。これが嫌で上位者がたまに低いスコアをサブミットして下位の方で待機する戦略を取ることがあります。（一般的には潜伏とか呼ばれていたりします） 実際、仮にスコアボードが順位だけでスコア表示がない場合は最終的な全体スコアも低くなると思っています。（コンテスト的に全然面白くなさそうですが）

参加環境はそうですね、10日間のコンテストで 240hあると思いますが 4-50時間ぐらいの作業時間が取れる環境は上位で戦うには必要な感じがします。 体調は大事ですね、いいアイデアが思い浮かんだときについつい夜ふかししてしまうこともありますが、基本的には早寝早起きのリズムを大事にしたいです。

質問8.
AHCの4時間コンテストで意識している時間配分・進め方はどんなものですか？ また、アイディアが多すぎる場合の優先順位のつけ方・戦略があれば教えてください。


saharan
最初 1 時間くらいは貪欲による方針をじっくり考えて、2 時間時点で結果を見てその後の方針を決め、残り 2 時間で焼きなまし・ビームサーチ・貪欲を詰める、というのが理想のパターンですが、なかなか実現できていません。アイデアが多すぎるときは、あまりに自明なもの、実装に時間がかかるものを捨てて、ある程度の非自明さと実装のしやすさのトレードオフを考えて実装する方針を選択します。

montplusa
4時間でできる範囲を見積もって、それ以上に手を伸ばさないようにしています。1位を狙うのであればちょっと弱気すぎるかもしれませんが、最近の4時間コンテストは4時間では詰め切れない複雑さの問題が出てきがちなので、ある程度の割り切りが重要な気がします。 最後の1時間はチューニングに使いたいので、メイン方針自体は3時間時点で完成していたいです。

tomerun
短期コンテストだと、とりあえずの貪欲を書いて様子を見ようというのをついやってしまいますが、局所最適に陥って本質的な強い戦略に行きづらくなるように感じており、やめた方が良さそうだと最近思っています。前半2時間くらいは実験と考察に振るくらいで良いかもです。 複数のアイディアの中では、実装量と影響度のコスパが大きそうなものからやります。

siman
4時間コンテストは「問題の誤読」が一番怖いので、最初の 30分は問題理解の時間にしています。 自分の経験上早めに解き始めても終盤の数十分はパラメーター調整を行っていることが多いので、それなら前半の数十分を問題理解の時間にしようという考えです。 ここ最近は生成AIのお陰で「とりあえず思いついたアイデア」を色々試せるようになったので、特に優先度はつけていなくてとりあえず実装してみてスコアを計算する、といった戦略になっています。

質問9.
AHCの10日間コンテストで、スコアが伸びない・アイデアが停滞したとき、どのように打開していますか？


saharan
苦しみます。とにかく考えられる方針を実装しやすいものからできるだけ多く試していきます。やや hacky ですが、相対スコアを利用して、どの傾向の問題でスコアが取れていないのかを見て伸びしろを分析します。Psyho のツイート (https://x.com/FakePsyho/status/1605570944537280512) を思い出します。1 位のスコアから、解がどのような状態になっている必要があるかを分析します。風呂に入ります。

montplusa
基本的には、将来性のある解法を序盤にできるだけ慎重に考えます。実装中の心づもりとしては、「まだこの部分は詰め切っていない」という部分を常に持っておき、終盤までは完全に詰まることがないようにしています。なんとなく届かなさそうなときはほかの可能性を探ってはいますが、そこは降りてくるかの運頼みなところがあります。

tomerun
そのような状態になってから打開できたことはないような気がしますね…

siman
スコアが伸びない、アイデアが停滞したときにやることですが、地道ですがやはり各テストケースを分析して、スコアが出るケースと出ないケースのビジュアライズ結果を比較していくのが大事だと思います。 「どういう条件なら高スコアになるのか」を調べられるように、様々なパラメーター（問題特有のやつ, ex) フィールドの広さ) を可視化出来るようにして、高スコアを取るための条件を整理していく感じです。 また、制限を無視した場合にどうなるのかを実験したりもします。例えば制限時間が 2secなところを 200secにして時間をかければ高スコアが取れるのかとか、何か制約を緩くしてみてその条件なら高スコアが取れるのかとか、とにかく今上位が取っているであろうスコアはどうすれば追いつくことが出来るのかをひたすら考える感じです。

質問10.
お気に入りのヒューリスティックコンテストの問題と、その理由を教えてください。


saharan
Exploring Another Space (AHC022) とても好きな推定問題で、理論が綺麗にハマってきちんと強い、という点がお気に入りです。同じ理由で Polyomino Mining (AHC030) もお気に入りです。

montplusa
AHC033 複数クレーンを用いて荷物の移動を行う問題ですが、最上位の所要ターン数がクレーンの諸々の条件を無視して移動距離だけで見た下界にかなり近いため、下界からのロスを考えると自然と良い評価関数になる、お手本のようなビームサーチ問題でした。

tomerun
北大・日立新概念コンピューティングコンテスト2018：固い数式と思いきや非自明パズル要素が多く、ヒューリスティックな探索要素もありで面白かった

AHC022：人々のビジュアライザのバリエーションが多くて見ていて楽しい。長期にしては実装量が少なく、実行速度による差があまりないのもよい

siman
AHC008 長年やっていると「焼きなまし」とか「ビームサーチ」が食傷気味になってしまうので、それらがメインの解法になりづらい問題固有の特化した解法が有効な問題が好きです。

おわりに

「自分はこうやって攻略しているよ！」といった情報がありましたら、ぜひtwitterの返信かリツイートでお願いします！また、もしアンケートを答えて知見を共有したい素晴らしい方がいらっしゃいましたら、ぜひDMください！

「AWS上にマラソンマッチ用のジャッジ環境を作った」をChatGPTに投げて、Lambdaを使ったAHC用のジャッジ環境を作る。

マラソンマッチ AtCoder AWS Lambda

概要

Webやサーバー関係に詳しくなくても、良い記事をChatGPTに投げればなんとかなる。

ChatGPTのいいなりになればOK

AtCoder Heuristics Contest（AHC）用にAWS Lambdaを使った自作ジャッジを作りたいなと思っていたので重い腰を上げましたがその辺の知識はありません。そこでyunixさんの素晴らしい記事を発見します。
yunix-kyopro.hatenablog.com

AWSを触ったことがない人向けには書いていないです。すいません...

と書いてありますが、気にせず上記の記事をコピペしてChatGPTに丸投げします。

以下のようにコマンドつきで基本的な部分から手取り足取り教えてくれます。

Ubuntuでも出来ますか？レベルの質問でもChatGPTは丁寧に回答してくれます。

あとは、「エラーが出たら、エラーログを添付して質問」「ハマったら原因を適当に推測してもらう」を繰り返すと、自分用のジャッジが作れます。詳しく勉強したい部分があったらそれも質問するといいです。

以下が実行結果です。できました。yunixさんありがとうございます。

はまったところ

typescriptを使った設定にする必要があった。

CDK（AWS Cloud Development Kit ）はpythonやtypescriptで設定できますが、記事に載っていたのはtypescriptだったので質問しなおしました。

リージョン間違いでログが何も見れなかった…

エラーログやLambdaの各種情報は何も設定しなくても表示されます。出てなければ何かおかしいです。この手の問題があると何が起こっているかさっぱり分からないので最初に直しましょう。ChatGPTはひどい勘違い系も割とヒントをくれるのが良いです。

ログを見る場合はhttps://console.aws.amazon.comにCloudWatchを追加すると見れます。python内でprintで標準出力したものもここで見れます。特別な設定はいりませんがリージョンを間違えていると何も見れません。


ジャッジ環境のディレクトリ構成が分からなかった。



記事に載っている1つ目のtypescriptはlib以下に置きます。

記事に載っている2つ目のDockerfile, 3つ目のhandlers.pyはlambda以下に置きます。また、requirements.txt（空ファイルで良い）も置く必要があります。

なお、main.cppやAHCのテスターを置くコンテスト毎のディレクトリとは別のものです。記事に載っている4つ目のpythonスクリプトは、コンテスト毎のディレクトリからmain.cppをS3に送ったりするのに使います。

別なバケット名を設定していた。

元の記事のpython実行スクリプトが以下のようになっているので、"バケット名"を書く必要があります。

バケットは２つ出来ているかもしれませんが、marathonjudge～のほうを設定します。もう一方のcdk-～はAWS CDKが、AWS CDK自体が管理するためのバケットの名前です

各種パスの更新をわすれていた

handlers.pyを実行したら、cdk deployコマンドでデプロイしなおすのも忘れないでください。

# handlers.py
import os
import json

import boto3


def entry_handler(event, context):
    timestamp = event["timestamp"]
    contest_name = event["contest_name"]
    N = 50
    result = [
       {
            "test_path": f"{contest_name}/in/{i:04}.txt",  # 要変更。テスト用入力ファイルのパス
            "timestamp": timestamp, 
            "contest": contest_name, 
            "id": f"{i:04}"
       } 
       for i in range(0, N, 1)
    ]
    return {"tasks": result}


def exec_handler(event, context):
    print(event, os.environ["s3Bucket"])
    # 前の段からテストファイルのパス・コンテスト名を取得
    test_path = event["test_path"]
    contest_name = event["contest"]
    test_id = event["id"]
    timestamp = event["timestamp"]

    # ソースコードを取得してビルドする
    bucket = boto3.resource("s3").Bucket(os.environ["s3Bucket"])
    bucket.download_file(f"{contest_name}/main.cpp", "/tmp/main.cpp") # {contest_name}/main.cpp。ここは記事に載っている4つめのスクリプトを使えばこのままで良い。
    os.system("g++ -O2 /tmp/main.cpp -o /tmp/a.out")

    # スコア計算のスクリプトを取得
    bucket.download_file(f"{contest_name}/vis", "/tmp/vis") # 要変更。テスター。{contest_name}/visは、S3で自分で設置した場所を指定。visは"cargo run --release --bin vis"でRustコンパイルしておく。
    os.system("chmod 777 /tmp/vis")

同時実行数が最大で10になっていた。

TooManyRequestsExceptionというエラーがよくかえってきたのですが、50個のテストケースを回していたのに最大10だったからでした。デフォルトで1000らしいですがなぜか10になっていました。

最後にChatGPTによるブログ

タイトル： AWS LambdaとAmazon S3を使用した高負荷タスクの並列化

AWS LambdaとAmazon S3を組み合わせることで、高負荷タスクを並列化し、処理効率を向上させることができます。今回は、プログラミングコンテストのジャッジシステムを構築する例として、AWS CDKとAWS Step Functionsを使って、この組み合わせを実装する方法を解説します。

1. AWS CDKとLambda関数の作成

まず、AWS CDKを使用して、タスクの各ステージを処理するLambda関数を作成します。今回は、各問題を別々に評価するためのLambda関数（evaluation-lambda）、評価結果をまとめるためのLambda関数（summary-lambda）、それらを制御するエントリポイントとなるLambda関数（entry-lambda）の3つを作成します。Lambda関数は、AWS CDKのlambda.DockerImageFunctionを使用してDockerイメージから作成します。

各Lambda関数はS3バケットに対する読み書き権限を持ち、バケット名は環境変数から取得します。

2. Step Functionsの構築

次に、AWS Step Functionsを使用してこれらのLambda関数を連携させます。Step Functionsのステートマシンは、エントリポイントのLambda関数を最初に実行し、次にマップステートを使用して評価Lambda関数を並列実行し、最後に結果をまとめるLambda関数を実行します。

3. ログの確認

Lambda関数がエラーを返す場合や、デバッグが必要な場合は、AWS CloudWatch Logsを使用してログを確認できます。CDKで作成したLambda関数は、関数名が自動生成されるため、AWS Management ConsoleのLambdaのダッシュボードから関数を見つけることができます。

4. バケットとファイルパスの確認

Lambda関数がS3からファイルをダウンロードできない場合、バケット名やファイルパスが正しいか確認が必要です。S3バケットの名称はCDKスタック名とリソース名から自動生成されるため、AWS Management Consoleから確認することができます。

5. 同時実行数の調整

Lambda関数の同時実行数が多すぎる場合、TooManyRequestsExceptionが発生する可能性があります。これは、Lambda関数のデフォルトの同時実行数（1000）を超えた場合や、Lambda関数の設定で制限された場合に発生します。

解決方法としては、AWS Management ConsoleのLambdaの設定から特定のLambda関数の同時実行数の上限を増やす方法があります。さらに、Lambda関数の上限がアカウントレベルで設定された上限（"予約されていない同時実行数"）を超えている場合は、AWSサポートに問い合わせてアカウントレベルの同時実行数の上限を増やすことも必要です。

今回の実装を通して、AWS LambdaとAmazon S3を組み合わせて、高負荷タスクを効率的に並列化する方法を学びました。この方法は、プログラミングコンテストのジャッジシステムだけでなく、データ処理やマイクロサービスの構築など、さまざまなシナリオで応用できます。

「競技プログラミングの鉄則」のレビュー

競技プログラミング マラソンマッチ AtCoder C++

米田 優峻さん（E869120@ICPC2022 (@e869120) / Twitter）の著書「競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~」をご恵贈いただきました。その感想です。

競技プログラミングの鉄則 (Compass Booksシリーズ)

競技プログラミングの鉄則 (Compass Booksシリーズ)

Amazon

素晴らしい内容で競技プログラミング初心者への最初の１冊として最もお勧めできる本です。特に、数学も得意というわけではなくプログラミング自体も初めてという方には、ダントツで一番お勧めできる本です。

本書の良い点

１．図が分かりやすい。

最初の48ページが無料公開されているので、百聞は一見にしかずということで見ていただけると良いと思います。i
www.dropbox.com
図自体分かりやすいですし全編カラーで書かれているのも良いです。段階的に説明すべきものについて無理に１枚に納めず多くの小さい図に分けて説明しているのもとても分かりやすいです。先ほどのpdfにある図の１つです。

また、既に理解しているアルゴリズムでも、勘違いしたりケアレスミスしたり書くのに妙に時間かかったりすることは誰にでもあると思います。本書の分かりやすい図は、自分の中での理解をアップデートするのにとても役立ちました。簡単な問題でも「あー、たしかにこういうふうにイメージできれば、すっきり理解できるなぁ」と感じることが多かったです。

２．つまづきにくい。

頭が良いが説明が苦手な人が記事を書くと、説明の段差が大きくなりがち（例： 「自明である」、「定義そのもの」、式の省略等）ですが、この本についてはそういうことはありません。特に、各節最初の例題は「無駄な部分を省き、学んでほしい部分に絞った問題」となっており、その例題まですら図で多く説明しているので、とにかく最初の１歩では絶対につまづかせないという意図を感じます。続く応用問題もほとんどの場合は例題に沿っています（でもコピペではうまくいかないちょうど良い問題）。必要に応じてヒントも書かれています。つまづきにくいです。

３．ヒューリスティックスについて取り上げてある。

できるだけ良い答えを出す系のコンテストAHC（AtCoder Heuristics Contest）についてはネットの記事はあるのですがまとまっているわけではないので、体系的に学びたい初めての人にこの本はとても良いと思います。貪欲法→局所探索法（単純山登り）→焼きなまし法のように、実際のコンテストで徐々にコードを改善していく過程に沿って書かれているので、コード量が増えがちでも分かりやすいと思います。

４．考察テクニックの章

問題のパターンは無数にあり全解法覚えるわけにもいかず自力で考察するほうが本質だと思うのですが、その考察について１章分設ける（６章）*1はとても良いと思いました。考察テクニックはもっとあると思うので、もしこの本の続編がでる場合は、さらにこの部分の分量をふやしてもらえると嬉しいです。

５．コンテンツが充実

まず問題集151問がすべてAtCoder上で利用できます。
atcoder.jp

本に載っていない分についてはgithubが用意されており、C++, Java, Pythonの3言語での解答コードも読むことができます。親切です。
github.com

解説pdfについても、本書程ではないにせよ図を駆使して分かりやすく書かれており、全216ページ（！）もあります。付録コンテンツは誰でも無料で利用できるのですが、正直ここだけでも商品になる気がします…。

本書の賛否両論ありそうな点

コードの書き方

分かりやすさのために一般プログラミングの作法については目をつむる、他の本で勉強してね、という方針は構わないと思いますが、以下の２つは気になりました。

  • 変数の定義がmainの関数内で行われている場合と関数外で行われている場合があり、その理由が特に書かれていない。
    • スタックオーバーフローを避けるために全部外に書きグローバル変数とするというのであればある意味分かりますが、そうでない例もあります。
  • STLに関して、説明無しで登場しているところがある（3.5章 vector）
    • ここまで引っ張るより早めにどこかでSTLについて説明したほうが、生配列よりもvectorのほうが良い部分で素直にvectorを使えたので良かったかもしれません。

親切すぎる

裏を返すと、この本に慣れると

  • コンテストにでる、あまり素直でない問題
  • 一足飛びの解説

などの耐性があまり付かず今後つまづくかもしれません。ただ、終章で次の教材として勧めている「競プロ典型90問」については「解説は原則１ページで簡潔にまとめられているため、分かりづらい部分もあるかもしれません。しかし、解説の行間を読むのも練習です。」と述べられており、この鉄則本については割り切って超親切にしているのかなと思いました。

同じジャンルでまとまっていて、必ずしも難度順にはなっていない。

同じジャンルのものをまとめる方式になっており、他の本では最初の方に来る「深さ優先探索」「幅優先探索」はグラフなので本書では最後のほうの9.2章・9.3章に主に取り上げています。ただ、この本は十分にわかりやすく、勉強の際には飛ばして必要な章から読むことも可能なので、必要なら飛ばし読みして良いと思います。

難度と勉強時間の目安

YouTubeで生放送しながら、本書を全部読み演習問題集の全151問を解いたのですが、33時間46分43秒かかりました。そのときの生放送は全てYouTubeのプレイリストにまとめてあります。
www.youtube.com
喋りながら問題を解くとだいぶ遅くなるのも踏まえると、おそらくAtCoder水色レベルの人なら20～25時間で全部読んで全問解けるのではないでしょうか？勉強する際の時間の目安として参考にしていただければと思います。

また著書の最終章にも書かれているのですが、米田優峻さんが本書の次にお勧めしている「競プロ典型90問」について現在解いていっています。こちらも良問が多くこれらも全て解説スライドがあり、とても親切です。
atcoder.jp

おわりに

そういうわけで自信を持ってお勧めできる本なので、みなさん購入しましょう！また、個人的な話ですが、この本がきっかけで毎朝7:00からの競プロ学習習慣がついた気がするので、このまま続けていきたいと思っています。

*1:10章の最初にも考察テクニックが書かれてあります

Visual Studio 2022でC++範囲外アクセスに気づきやすくする方法

C++

目次

はじめに
先日、Visual Studio 2022で、配列の範囲外アクセスのデバッグでハマってしまった。

constexpr int S = 20;
struct Maze
{
	Maze()
	{
		for (int y = 0; y < S; ++y)
		{
			h[y][0] = true;
			h[y][S] = true;
		}

		for (int x = 0; x < S; ++x)
		{
			v[0][x] = true;
			v[0][S] = true;	// 配列外アクセス。 v[S][x] = true が正しかった
		}
	}

	bool h[S][S+1];	// 横移動を阻む縦の壁
	bool v[S+1][S]; // 縦移動を阻む横の壁
};

定数で範囲外アクセスしているとても単純なケースなのに、なぜ警告も気づかなかったんだろう？となったので、いろいろ調べた。

配列外アクセスをしたときの比較表

  • コンパイルエラー・コンパイル時 警告・エディタで警告
    • 最高。実行前に気づける。
  • 実行時エラー・例外中断
    • まぁまぁ。実行時に気づける。実行時のabort、グローバル バッファー オーバーフロー、ヒープオーバーフロー等でとまる。
  • なし（オプションで実行時エラーに）
    • 設定によっては、実行時に気づける。
  • なし
    • 最悪で、範囲外のメモリを壊し動作が不定になる。未処理例外で止まる可能性もあるし、誤動作する場合もあるし、正常に動くこともある。
Visual Studio gcc clang
変数の種類 Intellisense Debug Release Sanitizer
オプション		 デバッグ寄り*1 デバッグ寄り*2
ローカル
生配列		 エディタで警告 1次元配列→コンパイルエラー
2次元配列→なし		 なし なし（終了時に不明の例外） コンパイル時 警告（部分的） コンパイル時 警告
グローバル
生配列		 エディタで警告 なし なし 例外中断 コンパイル時 警告（部分的） コンパイル時 警告
ローカル
std::array 		エディタで警告 実行時エラー なし（オプションで実行時エラーに） なし（終了時に不明の例外） 実行時エラー 実行時エラー
グローバル
std::array		 エディタで警告 実行時エラー なし（オプションで実行時エラーに） 例外中断 実行時エラー 実行時エラー
ヒープ
std::vector		 なし 実行時エラー なし（オプションで実行時エラーに） 例外中断 実行時エラー 実行時エラー


範囲外アクセスの参考コードはこちら

Visual Studio 2022で範囲外アクセスを気づきやすくする方法５つ

エラー一覧を「ビルド＋Intellisense」にする

f:id:shindannin:20220328054022p:plain
f:id:shindannin:20220328054310p:plain

  • インテリセンスで範囲外アクセスの警告が表示されて、基本的には強力である。
    • 逆にビルドの出力ログには警告すら表示されないので、それしか見ていないと気づかずに大失敗するので、要注意。今回気づかなった一番の原因はこれ。
    • インテリセンスなので、すぐに表示されなかったり、なにかのきっかけでリフレッシュされず古い情報が残ったりする（おそらくMicrosoftのバグ）。ターゲットの切り替えや、コード編集後にリビルドをすると直ったりするが不確定で緩慢なこともある。

sanitizerを積極的に使う

f:id:shindannin:20220328054555p:plain
（訂正）さらに調べてみたところ、ローカル変数を使用していないコードでも終了時に常に例外（0xE0736171）が出ることが分かりました。おそらくVisual Studioの問題？
- ローカル変数の例外（0xE0736171）は例外設定に入っておらず、ログには情報が流れるもの中断はしないので気づきにくい。

    • 中断するなら、以下のように例外設定ウィンドウで追加すればよい。ただしデバッグ情報は他のオーバーフローのように表示されない。
  • 今回のような配列範囲外のミスだけではなく、ダングリングポインタ・メモリリークなども見つけることができる。

生配列よりstd::arrayがよい

  • ローカル1次元配列だけなぜか親切にコンパイルエラーを出してくれるが、それ以外はチェック目的ならstd::arrayが常に良い。
  • 特にstd::arrayの2次元以上の書き方が順番が逆で、慣れないと間違えやすいが、テンプレートを使うことで緩和できる。以下のページがおすすめ。

koturn.hatenablog.com

Release版でSTLの範囲チェックしたいときは、 _CONTAINER_DEBUG_LEVEL=1 にする

f:id:shindannin:20220328055135p:plain

  • 実行時に、Debug版だと遅すぎて問題箇所までたどり着かないとき、Release版でSTLの範囲チェックしたいときに使える。
  • Debug, Releaseターゲット以外に、最適化するけど範囲外チェックするデバッグ用のターゲットを用意してもよい。

devblogs.microsoft.com

インテリセンスが安定せず嫌な場合、clangを代わりに使うのがよい

  • clangでもgccでも、警告の種類は"-Warray-bounds"だが、結果は微妙に違う。
    • Clangは、ほぼコンパイルオプションなし"clang++ -std=gnu++17"でも、コンパイル時に生配列への不正アクセスの警告をしてくれる。
    • gccは、 "g++ -O2 -std=gnu++17 -Wall -g -fsanitize=undefined,address -D_GLIBCXX_DEBUG" の設定をすればコンパイル時に生配列への不正アクセスを警告してくれるが、最初の１箇所だけの警告のみで、全ての箇所の警告してくれない。


おわりに
ちなみに、今回はコンパイラオプションでの対応を取り上げたが、より複雑な問題に対応するために以下のようなツールもあります。

  • 静的解析ツールを使う
  • メモリリークの検証ツールを使う（Valgrind、WindowsならAppVerifier

*1:オプション g++ -O2 -std=gnu++17 -Wall -g -fsanitize=undefined,address -D_GLIBCXX_DEBUG
バージョン g++ (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

*2:オプション clang++ -O2 -std=gnu++17 -Wall -g -fsanitize=undefined,address -D_GLIBCXX_DEBUG
バージョン clang version 10.0.0-4ubuntu1

本帰国後に、海外に置きっぱなしのお金のせいで面倒になることリスト

海外 よもやま

はじめに

自分は、投資等には興味なくお金に関する面倒なことはしたくない考えなので、最低限のこと（年金・非課税投資等）しかしてなかったのですが、意図に反して5か国（米国・カナダ・フランス・香港・シンガポール）8箇所に口座や金融商品が散らばってしまいました。散らばっていることは、ある意味リスク管理には有利とも言えるのですが、以前と比べて、

  • 節税効果はない（後述）
  • 日本の口座に外貨のまま持つことも可能
  • 香港にお金を置いておくのは…（実際、香港の人が口座凍結されたケースもあったし、世界情勢的には…）
  • もし自分に何かあったとき、全部連絡が英語だし、家族が何もできなさそう。

ということで、日本に帰国した区切りで口座等の整理を試みたのですが、いろいろと面倒があることが分かりました…。

この記事は、ほぼ自分の愚痴で人生で１回しか使わないことばかりですが、将来日本に帰国する予定がある人のチェック用にも役立つかもしれません。

お金に関することについて

クレジットカード

  • 自動更新できない
    • 居住してないとクレジットカードの更新ができない場合があります。
  • 自動更新されてしまって損する
    • 海外のクレジットカードは、日本では使えない場合が多々あります。
    • 海外のクレジットカードを使うことで不正な取引との疑いで、一時停止になることは普通にあります。
    • 最低使用額が指定されているケースもあります。使用額は月7000円以下のときでも7000円取られるといった状況です。クレジットカードが使用できなくなったからと言ってそのままにしておいて、思わぬ高額の使用料を毎月とられるのには注意しましょう。

Wise（旧 TransferWise）

送金手数料が安い*1ということで有名な送金サービスWiseがあります。以下の点には注意してください。

  • 初期画面に表示されないその他の手数料もいろいろある。

以下はWiseのメッセージより

100万円を超える日本円への送金は、SWIFTにて送金されます。SWIFT送金では、TransferWiseで発生する手数料以外に受取銀行や中継銀行から課金される手数料が発生する場合がございます。この手数料はTransferWiseが課金しているものではないため、最終的な受取額を当社でも把握することができかねます。恐れ入りますが、ご理解いただければ幸いでございます

この辺は普通の銀行間の送金と一緒です。　

  • 同一通貨の海外送金はできない。
    • 違う通貨に換えることの為替手数料は大きいので、国外の銀行から日本の銀行へ同一通貨のまま送りたいことがありますがそれはできません。
    • Wiseではなく普通の送金なら送れることもありますが、同一通貨のリフレクションフィーと言われる手数料がかかります。でも為替手数料よりは全然やすいです。
  • 2000万円～3000万円以上の送金はできなくなった。
    • 記事の通りです https://wise.com/gb/blog/lower-limits-for-large-transfers
    • また多額の送金は、そもそもwiseで指定される口座にその金額をインターネットバンキングで送れず失敗するというケースもあります。これもwiseのメッセージで警告がでます。

租税条約や税務上の居住地に関する届け出

  • ちゃんと所得税等を納めて出国しても、出国後に収入を得るようなケースもあります。例えば出国後に、海外保険会社（年金用）から「租税条約に関する届出 （https://www.nta.go.jp/taxes/shiraberu/taxanswer/gensen/2888.htm）」 を求められたことがありました。これをやらないと海外と日本で二重課税されてしまう恐れがあります。こういう重要な連絡は普通Eメールではなく手紙でくるので、ちゃんとお金を置いているうちは住所の更新等を常にしておくべきです。
  • 住所変更先を日本にする時や送金を行う際に、税務上の居住地に関する届け出、"Jurisdiction of tax residence"と"TIN(Tax Identification Number)"を問われます。前者は日本、後者は日本の場合はマイナンバーになります。2016年以前から海外在住の人は、マイナンバーが一度も付与されていない状態だと思うので、手続きは日本に住民票を移しマイナンバーを付与されてからになります。

外国払い小切手は、日本のほとんどの銀行では換金できない

欧米では小切手は安心できるお金の受け渡し方法としてまだ使われています。年金の掛け金の払い戻しに海外小切手が日本に送付されたのですが、これは問題がありました。日本の銀行は、ほぼ海外小切手の取り扱いを終了しています。こちらの記事（ https://yatsuyaku.com/clean_bill/ ）の通りです。唯一使えるSMBC信託銀行プレスティアにも直接伺ったのですが、手数料等を考えると海外小切手のためだけに口座を作るのはお勧めしないようでした。ちなみに、インターネットバンキングで小切手を換金する方法は考えたのですが、少なくともHSBC香港ではインターネットバンキングに対応した小切手でないと不可能でした。小切手は現地で換金しましょう。

マネーロンダリングに対して厳しくなっている

昔たまに見かけた「海外にお金を置いといて税金回避！」みたいなのは、ただの脱税になるだけです。以前よりもとても厳しくなっています。

  • 海外の利息や株式の利益も、日本の税金の対象となります。
  • 国外に5,000万円を超える財産を持つと、国外財産調書制度で把握されます。（https://www.smbcnikko.co.jp/terms/japan/ko/J0689.html ）国外財産調書制度とは、適正な課税の確保のため、国外に5,000万円を超える財産（預金、有価証券や不動産など）を持つ日本国内の居住者に、その内容を記した国外財産調書の提出を義務づける制度です。2014年度から始まり、現金預金、不動産、有価証券、骨董品や貴金属類まで、その年の年末時点で国外にあるすべての財産が対象となります。翌年3月15日までに税務署に提出しなければなりません。
  • 相続税についても、国外資産についてもかかります。相続人も被相続人も10年以上住んでいる場合のみ（https://www.nta.go.jp/taxes/shiraberu/taxanswer/sozoku/4138.htm）

少し前までは、香港へHSBC香港の口座を作るためツアーがありわんさか日本人がきていたそうです（話を聞く限りそういうツアー自体かなり怪しかったようですが）が、今だに残る利点といえば「海外銀行にしかない魅力的な金融商品」がほしいときぐらいでしょうか。でも、それこそ素人では判断では難しいと思うので、あくまで自分の意見ですが、海外に投資する興味があっても普通に日本の口座を使えばよいのではないかなと思います。

口座閉鎖する意思があり、日本に戻ってくる前に口座が閉鎖できる状態であれば、現地にいる間に閉鎖してしまった方が良い

  • 実際には、最終給与受け取り・税金支払い等で、その国を去ったあとでも一定期間口座を残しておく必要がある場合が多いですが、もし閉鎖できるなら現地にいる間に閉鎖したほうが良いと思います。インターネットバンキングでも口座閉鎖だけはできないケースがほとんどだと思います。
  • 代替案として、「口座閉鎖はせずに、後で日本の口座にほぼ全額送金して、空っぽにしておく」という考えもあると思います。ただ、現地採用で海外から本帰国するというケースは、送金額も大きくなると思うので、やはり現地にいる間にやってしまったほうが楽だと思います。送金方法に寄らず税金に関する手続きは全て済ませておく必要があり、多額の送金では審査もあります（ https://moneykit.net/visitor/fx/fx07.html ）。日本のサポートのほうが親切なので、海外にいる間に海外の面倒は解決したほうが良いと思います。

連絡方法について

インターネットバンキング

ほとんどの手続きはインターネットバンキングでできるので、他の国に引っ越ししたときは頼みの綱です。絶対途切れさせてしまってはいけません！途切れた時に面倒にならないために、連絡先更新はすぐにやっておくのが大事です。

  • パスワードとIDさえ覚えておけば大丈夫に思えますが、出国後に思わぬところでアクセスが途絶えたケースを挙げておきます。
    • 2段階認証が新たに追加されたが、2段階認証の登録が現地電話番号へのSMS経由のみ。
    • ストックオプション用の口座で、会社連絡先しか登録されておらず、転職後にアクセス不可能。
    • デジタルトークン（ちっちゃい計算機みたいなやつでパスワードがでる）の電池切れ。
  • 一定期間インターネットバンキングでの操作がないと、限度額が減ったり口座が一時凍結になる銀行もあります。
    • 最悪の場合、口座凍結解除するには、銀行に直接いかないといけない場合もあります。それはコロナ禍では無理なので、予めどういう条件で自動凍結になるかを確認しておいて、定期的にお金を動かしたりログインしておいた方がよいです。
  • そして一旦アクセスが途絶えてしまうと復帰は、予想外に面倒なことがあります。
    • ヘルプや問い合わせ機能で、パスワード自体はリセットできても、そのあとで結局現地電話番号SMSによる認証が必要で、結局ログインできない。
    • ログインの方法を問い合わせしたいのに、ログインしないと問い合わせできない。すでに仕組みとしておかしいですが、そういうのはよくあります。

出国後、連絡手段別の問題点

インターネットバンキングが途切れても、その国にいるときは簡単に復帰できますが、出国後はいろいろと難しいです。手紙・Eメール・電話・オンラインコールとなると思います。

  • 電話（SMS）
    • 現地の電話番号はすでにないので初回登録やSMSによるワンタイムパスワードを受け取れないという場合もあります。
    • 現地の電話番号しかそもそも受け付けていない（ネットだと電話番号フォームに入力できない）といったこともあります。
    • 問い合わせ先の電話番号が特殊な番号で、日本からは絶対かけられないケースもあります。
    • 電話の問い合わせで解決できることもたまにありますが、日本のコールセンターみたいな親切はないと言ってよいですし、たらいまわしも多いです。
  • Eメール
    • 海外-日本間のEメールはスパム扱いされて本当に届いてないこともあるので、要注意です。
    • Eメール届いてない場合に、念のために確認メールだしてくるといったレベルの親切はほぼないです。せっつきましょう。
  • 住所
    • 引っ越し後に住所更新するときに、住所証明が必要な場合があります。このとき日本の住所の証明はやっかいです。
      • 住所更新時の住所の証明として、最近の公共機関の領収書等を要求されることがありますが、日本の領収書は日本語で書かれており、また「令和3年」のように西暦で書いてないこともあるので、証明にならない場合があります。説明すれば大丈夫な場合もあるので説明しましょう。
    • 住所の更新をしないと最重要な連絡が届かないケースがあるので忘れずにしましょう。前述の「租税条約に関する届出」 もそうですが、前に住んでた国の税金の申告書類が届くケースもあります。
  • 手紙
    • 一番遅いですが、手紙なら電話・Eメール・インターネットバンキングではできないことも、できることが多いです。
    • しかし手紙の遅延もあります。届いたかどうかの確認を担当者に連絡できるようにコネクションを用意しておいたほうがいいです。
  • 担当者（銀行の担当者・ファイナンシャルアドバイザーなど）
    • 海外を去る前に担当者の連絡先を増やしておきましょう。メールもCCを複数人に増やすのが重要です。
    • 海外へ送受信するメールは届いていないことが普通にあるので、1人しか担当者がいないとそれで気づかずに途切れることがあります。
    • 単純に退社やご不幸等で連絡が続かなくなることもあります。
    • 銀行によっては、ある程度の預金額を越えているとちゃんとした担当者がつくプレミアムサービスがあるケースもあるので、利用できるなら利用したほうがよいと思います。

日本にいる間にやっておいた方がよいこと

  • 海外通貨が扱えてインターネットバンキングができる銀行口座
    • インターネットで申し込み手続きができる銀行ありますが、結局、確認通知を日本の住所で郵便で受け取る必要があるので、日本にいる間に作っておいた方が便利でしょう。帰国の際に、海外にいる間に済ませられることが増えると思います。
    • 海外通貨が扱えると、円に戻して為替手数料が取られることがないので、便利です。

おわりに

アドバイス・間違いの指摘等があったら随時更新しますのでお知らせください。

*1:以前は銀行との送金との比較表示で数%の差がでてたときもあったのですが、最近は最安の手段と比較するようになったので、送金手数料は実はあまり変わらないような気もしてきました。

競技プログラミングを終わらせる人々への指摘、頑張っている人々へのアドバイス

競技プログラミング

はじめに

競技プログラミングに関連する、以下の記事が話題にあがりました。

nuc氏1つ目の記事
nuc.hatenadiary.org

chokudai氏の記事
chokudai.hatenablog.com

nuc氏2つ目の記事
nuc.hatenadiary.org

nuc氏は、元Googleのエンジニアで面接も担当されていました。現在は某医大の特別特命准教授の方で、2007年頃に東大で競技プログラミングをされていた方のようです（氏名も役職も上記の記事のリンク先で公表されています）。nuc氏の記事は、競技プログラミングに対して「我々の目的の一つは、我々が始めてしまった競技プログラミングを我々が終わらせることです。」といった強い主張が多く、これらの記事の反応をみたのですが、

  • 競技プログラミングをしている方々が、nuc氏の主張で不安になり、特に若い世代で、競技プログラミングをやめようとしているケース
  • 競技プログラミングを知らない方々で、nuc氏の主張を鵜呑みにして、 競技プログラミングを誤解しているケース

等を見かけました。そういうわけで、なんらかのフォローをしたほうが良いと思い、この記事を書きました。

フォローの内容は以下のようになっています。

  • 第１章　競技プログラミングは変質したのか？
  • 第２章　競技プログラミングは変質して、悪影響を与えたのか？
  • 第３章　競技プログラミングをがんばっている皆さんへのアドバイス

付録以下の内容は今回のフォローとは関係ないのですが、一連の記事の読者の中で混乱していた方も見受けられたので、その辺を整理したものです。ほとんどの方は興味ない内容だと思うので、飛ばされても結構です。

  • 付録１章　nuc氏の議論方法の問題点
  • 付録２章　nuc氏のグループは、競技プログラミングを生み出したのか？
  • 付録３章　残る疑問

ちなみにnuc氏の記事の内容に全て反対しているというわけではありません。

  • 「競技プログラミングだけやっていても、Googleの入社面接の対策は不十分」という主張。これは、chokudai氏・nuc氏、元記事のリンク先で登場したLillian氏、全員同じです。
  • おすすめの本

のあたりは正しいと思っております。

第１章　競技プログラミングは変質したのか？

nuc氏は記事の中でこのように述べています。

我々の目的の一つは、我々が始めてしまった競技プログラミングを我々が終わらせることです。

競技プログラミングは変質し、その悪影響は看過できない所まで来てしまったと思います。競技プログラミングを始めた人たちができていたことが、その少し下の世代ではみるみるできなくなっていったと思われます。少なくとも、競技プログラミングの関係者がここまで Google に通らないことはありませんでした。

そして、2007年に競技プログラミングの名前が付きます。つまり「競技プログラミング」が広まり変質したというのは AtCoder ができる2012年より前の話をしています。

「悪影響は看過できない」は断定まではしていませんが結構強めの主張だと思います。でも、そもそも悪影響を与えるような変質があったのでしょうか。これを見ていきたいと思います。

短期コンテスト

まず、昔の競技プログラミングのほうが必要な能力が鍛えられていた例がいろいろあげられていましたが、トピックごとに検討してみました。

1・打ち込むのが大変なアルゴリズムも出題されていてた。（減った）

実装量が多いがアルゴリズムがほぼ不要な問題、通称「実装やるだけ問題」については、これは確かに現代のほうが減ったと思います。

2・バックスラッシュ（変化なし）

これは昔も今も短期コンテストでほぼ出題されていないと思います。例外的に、TopCoder・Codeforces等で、2次元のフィールドの左斜め方向を表すために使わていることありました。念のため2000年以降のICPC World Finalの問題をチェックしましたがバックスラッシュを入出力に使うケースはありませんでした。

3・言語の選択（重要になった）

昔は短期コンテストで使用できる言語は数個でしたが、現在では使用できる言語が圧倒的に増えていますし、むしろ現在の競技プログラミングのほうで重要です。文字列処理が簡単にできる言語、多倍長処理が簡単にできる言語などを適切に選べば有利になります。

4・定数倍高速化（とんとん）

昔のほうがオーダーがきっちりしておらず定数倍高速化が有効だったケースが多かったというのは同意です。しかし、逆に現在は言語が増えたことで、スクリプト言語のように実行時間が遅い言語で定数倍高速化が有効なケースもでてきたので、一長一短です。また、言語が増えたことで、すべての言語でオーダーがきっちりした問題が作るのは不可能なゆえに速い言語での定数倍高速化が有効なケースもあります。ちなみに、nuc氏は「プログラミング言語の選択は影響がないように作られています。このために、1000倍くらいの定数倍は無視します」と述べていますが、そのような問題はほとんどありません。

5・クイックソートのようなライブラリーが提供するアルゴリズムについての詳細（変化なし）

ライブラリの内容が分かっていることを要求されるアルゴリズム問題はでたまに問われますが今も昔も多くはありません。例えば、クイックソートでいえば、アンチクイックソート（クイックソートキラー）の問題については、今も特にCodeforcesで含まれています。

6・出題者の気持ちを読む能力（変化なし）

必要でしょうか？これが「制約などから逆算して、適応可能なアルゴリズムを考える」という意味なのであれば、むしろ実用的な能力です。私はこちらとこちらに同意見です。出題量の意味でも変化はありません。

nuc氏は述べていないのですが、変化があるとすれば枝刈りです。

7. 枝刈り（減った）

計算量が不定な場合が多く、ICPC以外ではほとんど出題されなくなったかもしれません。

以上は問題そのものの変化についてです。

またnuc氏は、

面白くするために作られたルールだと分かっている人たちがいなくなり、そのルールとそれによる序列が絶対的なものになってしまったということです

と述べていますが、これは違います。レーティングがつかない自由な形式の短期コンテストは、現在のほうが明らかに増えてます。代表的なものとしてyukicoderががあります。
yukicoder.me
「競技プログラミングは、出題することもとてもアルゴリズムの勉強になります。完璧に出題できなくても、気軽にお互い指摘しあって向上していこうという方針で行っております。」という思想により、出題形式がかなり自由で、また「ゆるふわポイント」のように競技力以外の貢献度の指標もあります。これは明らかに「ルールとそれによる序列が絶対的なもの」と真逆です。参加者数も7000人以上います。

また、出題形式がとても自由な各種有志コンテスト（Xmas Contest 2020 - AtCoder 、お誕生日コンテスト - AtCoder）も増えました。これらは、競争用としては微妙ですが、プログラミングとしてはいろいろと勉強になります。例えば、入力が「１＋２＝？」となぜか画像で渡される問題がありましたが、短時間で画像解析をどうやるかを考えることができ、明らかにプログラミングの勉強にはなります。

ちなみに、短期コンテストそのもので良くなった点については元記事で触れられてはいないわけですが、AtCoderを初めてとした参加しやすいコンテストが増え参加への敷居が下がったため全体のレベルは上がり、さらにいろいろなアルゴリズムについて問われるようになりました。深みは増しています。

長期コンテスト・最適化コンテスト

長期コンテストや最適化のコンテストは、短期コンテストの例で述べた1～7の全てのスキルはもちろん、使用言語や計算資源も自由なことが多く、プログラミングのより幅広い知識スキルが必要になっています。そもそも実務の問題をアウトソーシングしている形のものすらあります。

各競技プログラミングサイトによって何を重視するかは違いますが、そういうコンテストは増え続けています。

SuperComputing Contest 1995～ スーパーコンピューターを使った高校生向けコンテスト
ICFPC 1998～ 自由な形式の3日間チーム戦コンテスト
TopCoder Marathon Match 2006～ 最適化・高速化・1人ゲームAI・機械学習など。NASA主催など、実務と直結するものも多い
CodinGame 2012～ ゲームっぽさ抜群の対戦型ゲームAIコンテスト
Google Hash Code 2014～ データが非常に大きい最適化コンテスト
Halite AI Programming Challenge 2017～ 15000人以上が参加したこともある対戦型ゲームAIコンテスト
AtCoder 2017～ 最適化・1人ゲームAI・ウェザーニュース社のデータ圧縮、日立・北大と量子コンピューター設計

nuc氏が記事内で、昔は良かった例として、問題が途中で変わった最適化コンテストの話を上げていますが

昔は、面白くないコンテストというのがたくさんあったのです。たとえば、線形時間アルゴリズムの最適化のコンテストで、締め切り後にフロッピーディスク内のファイルで計算が行われることが発表され、フロッピーディスクから大きなファイルを読み込むため、非同期処理をして読込み中に計算をした人が2位にダブルスコアで勝つというコンテストがありました。騙された感じはあります。ただ、本当に勉強になりました。

これについてはICFPCが代表格で、良くも悪くも現在までこういった出題傾向は続いています。

また、似たようなタイプの（面白くないコンテストかどうかは人によりますが）よりさまざまなスキルが要求されるコンテストは増え続けいています。

Google Hash Codeに至っては、30000人以上の参加者がおり、世界最大級の競技プログラミングコンテストとなっています。また、いまだに、大学や学会が独自主催の小さめのコンペティションというのも結構あります（例：http://www.jpnsec.org/files/competition2019/EC-Symposium-2019-Competition-English.html ）

まとめると、競技プログラミングは短期コンテストで傾向が少し変わったものの、全体としては大きく幅が広がったいえます。

第２章　競技プログラミングは変質して、悪影響を与えたのか？

最初に、「競技プログラミングは、面接のために作られたわけではないので、どう変質しようが競技プログラミング側には一切責任はない。」という部分は最初にはっきりさせておきます。

同じような仮説は各所で述べられていますが紹介します。（念のため、悪影響を与えたかどうかの立証責任は私にないです。）
f:id:shindannin:20210408125022p:plain

昔は競技プログラミングは、情報系の強い人や極めて頭の良い層しか知らなかった、そういう人達しか競技プログラミングをやれないほど敷居が高かった。アルゴリズムの勉強をちょっとすれば面接合格レベルに到達できた。
（以下の例だと、競プロをしていてアルゴリズムの能力だけであればGoogle面接合格レベルの人で、最終的に面接合格したのは、4人中3人で75%です）
f:id:shindannin:20210408125254p:plain

今は競技プログラミングが幅広い層に普及した。アルゴリズムの能力だけであればGoogle面接に通るレベルに到達できる人も増えたが、全体として面接合格レベルに到達できる割合が少なくなった。
（以下の例だと、競プロをしていてアルゴリズムの能力だけであればGoogle面接合格レベルの人で、最終的に面接合格したのは、9人中4人で44%です。割合は減っています。）
f:id:shindannin:20210408125309p:plain

といった現象が起きているだけだと予想します。アルゴリズム能力が上がること自体に悪影響はないでしょう。

第３章　競技プログラミングをがんばっている皆さんへのアドバイス

自分にとって、競技プログラミングは人生に欠かせぬものです。

  • 本職はゲームプログラマーなのですが、競技プログラミングで得た能力は仕事に大きく役立っています。むしろ、仕事で役立たない分野が見当たらないくらいです。
  • 競技プログラミングそのものが楽しいので、人生の豊かさアップにもなっています。
  • 競技プログラミングを通じて、世代や業界を越えて、いろんな人と知り合うことができました。これも素晴らしいことです。

ただ、自分の例を挙げても、世代も環境も違いますしピンとこないと思うので、いろいろなテーマについて考えてみました。ここで書いていることの多くは、競技プログラミングに限らず成り立つことだと思っています。

なにかに熱中しているってこと自体が、素晴らしい。

  • 何かが好きで熱中してがんばっているってことは、ベストな行動だと思います。一般的には高校生以下なら制約も少ないと思うので、迷わず熱中しましょう。
  • 仮に、他の方に「あまり好きでない他の事のほうが役に立つよ！」と言われたとしてそれをやるとして、同じように頑張れるでしょうか？結局ダラダラやってしまうことになると思うので、好きなことに熱中したほうがいいです。
  • 将来、自分の好きな事が他の事に変わったとしても、１つのことに熱中でき頑張れることが素晴らしいスキルなので、その経験自体が応用できます。
  • ちなみに、競技プログラミングの強さは全く関係ないです。自己ベストを出すために、ベストな行動をすること自体が大事です

競技プログラミングは役に立つ論

  • こういうのは価値判断の論題と言われていて、それぞれの人がどの価値に重きを置くかによって違ってくるので、決着がつかない論題と言われています（他の例：「男と女ではどちらが幸せか？」だったら、何をもって幸せとするかはなんとでも定義できるので議論に決着がつかない）
  • 「競技プログラミングは役に立つ」をシェアするのは、他の方の参考になるので良いことですが、他の方に押し付ける必要はないと思います。
  • もし、わざわざ山を越えて、他の方が「競技プログラミングなんて役に立たないよ。むしろ悪影響だよ。」と言って来たら、それは「お前の中ではな…」と思って相手にしないほうがいいと思います。

競技プログラミングを仕事に役立たせたい人が仕事に役立たせるためのコツ

  • 応用できないかを日ごろから考えようとすることは大事だと思います。普段の問題を解いているときでも、仕事をしているときでもいいので、応用できないか考えてみましょう。
  • 競技プログラミングで学べるスキル「最適化（＝最小値を求める・最大値を求める）」は、平たくいうと、短期コンテストなら「一番良いのを探す」、長期コンテストなら「できるだけ良くする」という意味で、とても応用がききます。
  • 長期コンテストであれば、仕事を外注しただけの問題がたくさんあります。どういう風に世の中で使われているのかはヒントになると思います。

競技プログラミングがおもしろすぎて、仕事を含む他の事に興味が持てない。

  • 気持ちはとても分かりますが、上と下が参考になれば。

人生の目標が決まっていると、競技プログラミングをやる上でも迷わない。

人生の目標が決まってると優先度も決めやすいので、例えば社会人になっても優先度から時間を割り当てて競プロをするといったことができます。他の人の価値観押しつけにも惑わずに済みます。ただ人生の目標を立てるのは簡単ではありません。人によっては小中学生のころから崇高な目標を持ってる人もいるので焦りますが、ヒントを書いてみたいと思います。

  • 崇高な目標を立てる必要はありません。まずは初期解をつくりましょう「毎日5時間競プロして、5時間ゲームして、お風呂とご飯が2時間ぐらいで、12時間ぐらい寝たい。あとはモテモテの生活で一生を終える。」ぐらいの目標でいいと思います。欲望のままに立てるのがいいと思います。
  • 現実には、お金の制約・能力の制約・時間の制約・家族の制約・身体的制約などで、現状から目標達成までに大きなギャップができると思います。この例だとお金が1億円ぐらい必要な気がします。
  • そのギャップを埋めるに当たって妥協するのも途中の目標としては悪くないと思いますが、組み合わせを考えてみると妥協量を減らせるケースがあります。例えば、「5時間競プロして、5時間ゲーム」を組みあわせて、「ゲームAIを作る仕事を8時間する。残り2時間を競プロとゲーム」という風にすると、競プロ欲とゲーム欲もある程度も満たせる上にお金も入ってくるので、より現実的になり、最終目標にも近づけます。
  • また、目標を改善したい場合は、「仮に目標が全部達成できたとして、それで人生本当に満足か？」を考えると良いと思います。「毎日5時間ゲームするのも楽しいけど、せっかくならもっと時間を増やしてプロゲーマー目指すか！」みたいに考えられるといいです。
  • 子供の頃に好きだったは、その人の本能的な欲求だと思うので、人生の目標ヒントはあるかもしれません。

Googleに入社したい方へ

なんでも１次情報が大事です。競技プログラミング勢で現役でGoogleで働いている方はかなりいるので、相談するのであればそういう方々に相談する方が良いと思います。また、YouTube上にGoogle自身が就職のためのいろいろな情報を載せています。
www.youtube.com
www.youtube.com

nuc氏の記事によると性格はあまり関係ないとのことでしたが、現役Googleのエンジニアの方の情報によると、最近は技術以外なものも求められるとのことでした。
careersonair.withgoogle.com （要登録）Googleyness & Leadership で検索してもいろいろと出てきます。謙虚さやリスペクトも大事みたいです。


以上、ここまでが競プロに関していいたいことでした。ここから先は読み飛ばしても構いません。

付録１章　nuc氏の議論方法の問題点

[1] 自分の主張を読み取れないのは相手の責任にする。

nuc氏の1つ目の記事での主張です。

[A] 競技プログラミングは、東京大学競技プログラミング同好会2007年春台湾合宿から始まります。それまで、プログラミングコンテストは開催されてきましたが、競技プログラミングの名前が使われたのはこの合宿がはじめてで、このとき一つのジャンルが生み出されたのです。

[B] 我々の目的の一つは、我々が始めてしまった競技プログラミングを我々が終わらせることです。

どちらも断定しています。[A][B]を信用して正しいものとし解釈すると、nuc氏の主張は

「競技プログラミングという一つのジャンルを生み出したのは我々（＝nuc氏を含めた合宿参加者）であり、我々の目的の一つは、競技プログラミングを終わらせること。」

となります。ジャンルを生み出した人がそれを終わらせると言ったら、ジャンルを丸ごと終わらせるという風に解釈するのが自然です。しかし、nuc氏の2つ目の記事によると、実際の意味は、

で、この「競技プログラミングを終わらせなければ」における「競技プログラミング」というのは、もともとは、今回の模擬面接をした3人の周りの人たちの間では、競技プログラミング同好会・クラブやその周辺の活動を指すわけです。そりゃそうじゃないですか、「競技プログラミングをする」という表現は当時はなくて、「プログラミングコンテストに出る」と言っていたわけです。だから、競技プログラミングといえば、自分たちが大学生の頃の集まりを指すわけです。「学生時代のバンドを終わらせなければ」と置き換えたら意味が通じるでしょうか。つまり、自分たちの大学生・大学院生の頃を反省して、とても大事なことをやり忘れてきたのでやり終わらなければいけない、ということです。

「そりゃそうじゃないですか」と理解できるのが当然のごとく言っていますが、2012年以前に活動は終わっているわけですし、終わらせる対象が「当時の競技プログラミング同好会・クラブやその周辺の活動」と限定的だというのは、思いこみをなしにそう確定することはできません。

[2] 相手の主張は自分の思いこみでより悪く解釈する。

chokudai氏は記事で、[C]と[D]を主張しています。

[C] 「競技プログラミングをしている」と言ったら、非常にありがたいことに、殆どの人がAtCoderに取り組んでいると思います。日本における「競技プログラミング」は、「AtCoder」と言い換えても、さほど問題がないかと思います。

[D] 昔の競技プログラミングがどんなものだったか知りませんが（とはいえ、記事で書かれていた2007年に僕は競技プログラミングにすでに行っていましたが）、今の日本の競技プログラミングの主流であるAtCoderは、このようなものになっています。

[C]についても断定まではしてません。[D]では今の日本の競技プログラミングということで、昔の競技プログラミングと明確に区別しています。

AtCoderは競技プログラミングに含まれる（競技プログラミングの一部である）ことは明らかで、[C]で言い換えても問題ないというのは
「競技プログラミングが終わる」ならば「AtCoderが終わる」
のようなケースのことを指しているのかなと解釈しました。これは真です。

これに対してnuc氏は2つ目の記事で以下のように解釈しました。

別に「競技プログラミング」という単語を商標登録していたわけでもないですから、その後、誰が使うのも自由です。ただ、さすがに、個人の代名詞や会社の代名詞のようになっていると思っている人がいることには私は気が付かなかったわけです。

「ちょくだい」は、東京大学「ちょくだい」同好会2007年春台湾合宿から始まります。
「ちょくだい」は変質し、その悪影響は看過できない所まで来てしまったと思います。
我々の目的の一つは、我々が始めてしまった「ちょくだい」を我々が終わらせることです。
「AtCoder」は、東京大学「AtCoder」同好会2007年春台湾合宿から始まります。
「AtCoder」は変質し、その悪影響は看過できない所まで来てしまったと思います。
我々の目的の一つは、我々が始めてしまった「AtCoder」を我々が終わらせることです。

これはchokudaiさんの主張に全く沿っていません。まず[D]で昔の競技プログラミングと明確に区別はしているのに、nuc氏は昔の競技プログラミングをAtCoderと置き換えてしまっています。これらの文は一目みたら意味がわからず、読者でこう解釈した人はほぼいないと思われます。特に、昔の「競技プログラミング」を「ちょくだい」と置き換えるのについては、そのような主張はなく、全く意味が分かりません。

そりゃそういう風にいわれたら怒ります。ごめんなさい。だけど、破産させる気も抹殺する気もありませんでした。というよりも、こう読まれるのにあらかじめ気がつけというのは、正直無理です。

正直無理とは言っていますが、それはnuc氏が勝手に「昔の競技プログラミング」を「ちょくだい」に置き換えたために起こった自作自演なのに、相手の責任にしています。さすがにこれはnuc氏に悪意があると思われて致し方ありません。

また[1][2]からダブルスタンダードであり、公平性がなく、説得力がないと思います。

[3] 分かりやすく書く気がない

chun さんに、このようなことをお伝えするのは本当にお耳汚しなのですが、散逸は意図的です。私の経験則で「誰にとっても新しい情報」のメッセージを広く伝えたいときには、「詳しい人は同意するが、そうでない人は違和感を感じる内容」を加えるんです。そうすると、人は、「新しい情報の真贋を、周囲の情報から判断しようとする」ので、一部の人に認知負荷がかけられます。こうすることで、根拠と結論が噛み合わない支離滅裂な発言も出てきて広まると認識しています。

バズるのには確かに成功しましたが、真摯でないと思います。自分だったら、一意に解釈できない記事を書いて誤解されたら、自分の責任だと思っていますが…。

またマウントを取るタイプの人が、このような手法をとると、書いた側が常勝してしまうので、基本相手にしないほうが良いと思います。

  • 違和感がある主張に対して、書いていないことを読みとらないようにしてると、「普通に考えてそんなわけない」
  • 違和感がある主張に対して、辻褄があるように書いていないこと仮定すると、「思いこみ。文章を読む訓練をしていない人にありがち」

[4] 不遜

[1][2]については、単に議論についてのスキル不足な場合でも起こりえます。人間は誰でも間違いがあると思うので、記事の主張に間違いがあったとしても、それは冷静に問題点を修正していけばよいだけだと思います。
しかしnuc氏の記事は謝っている内容にはなっていないし、相手を悪く解釈して、嫌味っぽい言い方が多くあり、この記事を読んでnuc氏が心から謝っていると解釈する人はほぼいないと思います。（chokudai氏はもう関わりたくないので大人の対応をしているだけかと思います）

ちょくだいさん、ごめんなさい。(ちょくだいさんが中高の後輩で、中学校一年生や中学校二年生の頃の印象からアップデートされていないことも行き違いの原因かと思いますので、この書き方にいたします。)

本文が謝っている態度にもみえないですし、大人に対して、中学校一年生や中学校二年生かのように話かけている時点で相手を馬鹿にしていると思いますが…。とても失礼だと私は思いました。

さらに、

ここで残念なお知らせがあります。とある医学部教授から「読んだよー。文章はいいけど、お前が卒業生をひょいひょい適当にエンジニアにすると教授会で問題になることがあるから、するんだったら出来の悪いのにしてよね。いいね。ほんと頼むよ。特にそこにいる生徒会長みたいなのはだめだから。」ということなので、今後は、あらかじめ「出来が悪いかを問い合わせる」約束をしてきました。

「出来が悪いかを問い合わせる」、自分はこういうのに同意するような人には教わりたくはないです。この医学部教授も問題だと思いますが…。

こういうのを見ると、最初の記事のタイトル「Twitter で医師を拾ってきて Google のソフトウェアエンジニアにするだけの簡単なお仕事」の「拾ってくる」という表現ネタではなく、上から目線で本当に失礼なだけな人にも見えてきます。

その他

もし、どなたかがnuc氏は議論することになった場合は、最初に議論のマナーを守っていただけるように約束してからのほうがいいと思います。特に4. 注意点の部分
http://www.ritsumei.ac.jp/ir/ir-navi/common/pdf/technic/technic_text_09_2019.pdf

付録２章 nuc氏のグループは、競技プログラミングを生み出したのか？

nuc氏は競技プログラミングに対して責任感や使命感を感じているようなので、今回のような行動を起こしたともいえます。しかし、そもそも競技プログラミングを始めたのでしょうか？始めたのでなければ終わらせる必要もないので、なにもせず平和に終わっていたと思います。

  • まず本題の前に、nuc氏の指す「我々」が、競技プログラミング*1というージャンルを生み出したというのは、competitive programmingはすでに存在していたので間違いです。"competitive programming"の日本語訳を考えたということであれば合っています。「ージャンルを生み出した」は間違いというのは自明ではありますが、嘘を言っていることには違いないので反省はしてください。

自分の意見ですが、「nuc氏の指す『我々』が2007年に競技プログラミングという一つのジャンルが生み出した」のが、「nuc氏の指す『我々』が2007年以降の競技プログラミングに大きく影響を与えた」という比喩であったとしても疑問が残ります。それは以下の理由からです。

ただ、nuc氏の指す競技プログラミングを生み出し終わらせようとしているメンバーが曖昧なので、確定はできません。

付録３章　残る疑問

nuc氏の指す「競技プログラミングという一ジャンルを生み出した我々」「競技プログラミングを終わらせる我々」が、台湾合宿メンバー全員なのか、nuc氏＋面接の講師役2人の計3名だけなのか、今だに分かりません。もし違うのであれば、当時の状況などを知る人を教えていただけると助かります。

また、

  • Q1. 競技プログラミングを始めたメンバーはだれか？
  • Q2. 競技プログラミングを終わらせようとしているメンバーはだれか？始めたメンバーと同じか？
  • Q3. 競技プログラミングを終わらせる活動に、競技プログラミングを始めたメンバーはどれぐらい賛同しているのか？
  • Q4. 競技プログラミングを終わらせる活動は、結局何をやることなのか？（「自分たちの大学生・大学院生の頃を反省して、とても大事なことをやり忘れてきたのでやり終わらなければいけない」とありますが…）

このあたりをはっきりさせないと、これ以上議論が進まなそうです。

2007年の東大の状況は分からないのですが、2008年からはUTPCというコンテストがあり、参加者や作問者が見れます。

私自身、このメンバーの半分ぐらいは知っていると思うのですが、終わらせようとしているのに賛同している人がどれぐらいいるのか疑問が残ります。

*1:ちなみに、「競技プログラミング」という訳語自体も、実はすぐには広まりませんでした。当時、ほとんど「プログラミングコンテスト」という呼び方をしていたと思います。Googleトレンドの検索結果。プログラミングコンテストだと主語が大きく、それこそ他のプログラミングの存在を無視している感がある、そのかわりに「競技プログラミング」という呼び名が使われるケースが増えたと予想しています。→追記:情報をいただきました競技プログラミングという言葉の誕生 - MAYAH