ABC135-AB

ABC135 へのリンク

A: 相異なる整数同士の和が偶数(解説では偶奇が等しい)ならば、整数それぞれからある同じ整数を引いた絶対値が等しくなる

B: std::vector は erase とかするとインデックスがずれて面倒なことになるから素直に v[i] で代入したほうがいい。あと問題文では p_i = i であることが読み取れなかったが、今回は高々 N = 50 だったので全探索で通せた。しかし N = 1E+5 あたりから 100000 C 2 = 4999950000 > 1E+9 となって全探索ではきつくなるので、解説通り p_i ≠ i の箇所を数える必要がある。

以上感想でした。

競プロ1000日チャレンジを始めてみた

徳力さんの note で1000日チャレンジというものが最近あり、1000日のあいだに何かしらなした記録を残すことでなにかの上位1/100になることを目指しましょうという内容を読んだ。

なるほどな、ということで、競プロでそれをやってみようと思います。僕はソフトウェアエンジニアリングの学習において、データ構造とアルゴリズムについては AtCoder で開催されるコンテストに出れるときに出るか程度の受け身の学習姿勢だったため、ちょうどいい機会です。

期日

今日は2019年7月28日で、1000日後というとカシオの高精度計算サイトによれば2022年04月23日です。Google カレンダーに登録しました。

目標

目標設定ですが、まず現状では茶色です。chokudai さんの記事によれば、 AtCoder では橙色になれば上位1%で、頭おかしいレベルだそうですが、とりあえず 1/100 を目指そうということで、僭越ながら橙色を目標にします。

学生時代をつぎ込んでも青色になれない人がたくさんいるとのことなので、1000日で橙色というのはかなり無理のある目標設定ですが、 1/100 を目指しましょうという流れにまずは乗ってみます。

内容

ゲームにおいてもラスボスは当初まったく歯が立たない相手であることが多いものの、スキルやパークの積み重ね、そしてプレイヤー自身の熟達によって徐々に「これはもしかするとそろそろラスボスも倒せるんじゃないか」感が得られるものです。

当面はこの感覚を少しずつ積み重ねるべく、蟻本や螺旋本、アルゴリズムイントロダクションといった本をちまちま読みすすめつつ、精進グラフを伸ばしていきます。

ところで「競プロ 橙」でググったところ、けんちょんさんの Twitter のスレッド がヒットしました。最低限の典型アルゴリズムをおさえる、700 点問題を解いて問題慣れする等が挙げられていますが、まだ全然そこまで達していないので、まずはABCを卒業すべく精進していこうと思います。


徳力さん曰く、1000日チャレンジというものの、1000日間毎日何かするというものでもないそうです。一方でまったく無関係のダ・ヴィンチ・恐山さんが月4回更新の契約の note を「なんとなく」で昔から毎日更新し続けているので、とりあえず購読することにしました。別に対抗して毎日競プロやろうというわけではありませんが…

更新する記事は基本的に自分へのメモになると思います。

上司アンチパターン

前提として、人間はある組織の一員である以前に、その組織の外に独立した生活をもつ自由な人間である。

また、個人は自身の人生における成功とか目的の達成に関して最終的な責任をもつ。決定権を持つのは君自身ってことだ。もちろんGDPが伸び悩むとかそういうことにあなたが責任をもつという意味じゃない。

このチームならミスしても大丈夫、だからリスクもとれる、というのが心理的安全性。いわゆるカルチャーマッチを構成する要素の一つ(だと勝手に思っている)。

心理的安全性があるチームでは、どんどん新しいことに挑戦できるし、隠し事をする必要もない。自律的に動けるようになる。いわゆる自走するチームになれる。

逆に、何か失敗したり些細なルールを破るたびに短気な上司に怒られるチームはどうだろうか。仮にその上司のことを個人的には好きな人でさえ、叱られまいとコソコソ仕事するようになるだろう。そういうチームで、競争相手の先を行く良い仕事ができるだろうか。僕はそうは思わない。

以下は Camille Fournier の『エンジニアのためのマネジメントキャリアパス』から、「すごい上司、ひどい上司」と題された複数のセクションのうち一部の内容を要約したもの。

エンジニア以外の職種でも多分みんな人間なので、適用できる範囲はそう狭くないと思う。

アルファギーク

頭の回転が速く凄腕、技術力が高い。しかしこだわりや「自分こそチームで最優秀」志向が過度に強いので他人をほめない。「議論と人格は分けるべきなんだから、正しい主張なら言葉遣いがどれだけ荒くても問題ない」という人。

Windows NT 開発の技術的指揮を執っていたころの David Cutler みたいなもんである。

メンタリングを通して人の学習を導く視点を得られればアルファギーク気質を脱する機会はあるが、それでもだめなら人の上に立つべきでない。技術だけを任せ、人のマネジメントにはかかわらせないほうが本人と周囲の両方にとって利益になる。

自分の上司がアルファギークで、チームの一員に有害な言動をしていたら?その場でただちに、「部下にそんな話し方をしないでください。失礼です」と指摘すべきだろう。上司が部下を人前で攻撃することのメリットはまったくない*1が、上司へのフィードバックは部下にとって当然の務め。

しかし尊敬できない上司がいつまでも変わろうとしないなら、自分がチーム異動か退職する。上司を変えられないのはしかたないので、一緒に働くことに利益はない以上場所を変える。

万一、優秀でもないのに有害な言動をする人が上司だったら?一目散に逃げ出すべきだろう。もうその船にねずみはいない。

プロセスツァーリ

几帳面で、手順に忠実。アジャイルの対極。「この方法でやりさえすれば失敗しない」と思い込む。失敗が怖いから。

失敗しても大丈夫ですよと語りかけよう。手順を使うにしても個々人が自分で調整できる、ゆるい環境を構築する手助けをしよう。ルールを破ったからというだけで同僚が批判されることのないようにしよう。

マイクロマネージャ

微に入り細を穿つマネジメント。新人エンジニアにとっては良いが、いつもマイクロマネジメントしてるようではよろしくない。部下を信頼していない。チームの自律性を奪ってしまう。

良い上司はどこで顔を出せばいいのかを部下とよく相談する。いざというときに力になってくれる。任せ上手が良い上司。

恐怖による支配

部下を人と思わない。効率厨。「議論と人格は分ける」のはいいのだが、上司に向かってそれができない人も普通にいるので恐れられてしまう。一見、恐怖の文化が支配していてもうまくいっているように見える会社はよくあるが、良識ある人間は転職する。何か問題があっても、恐怖に支配されたチームはそれを乗り越えられない。

このあたり、『ティール組織』に載ってたような気がする。赤い組織。

良いチームをつくるには

アルファギークを除けば上記の例は、管理者なら誰でもなりうる。特にプロセスツァーリやマイクロマネージャは、上司として失敗できないという自負から陥りがちなんじゃないかと思う。

自分が上司である場合の起点は、チームの一人ひとりと心を通わせること。

自分の上司がこのような「ひどい上司」だった場合、それを指摘するのは当然だが、上司を変えようとまでしなくていい。それは受け入れるしかない。変わらなかったらチームをただ去るのみである。

*1:例外はあって、それはブリリアントジャークがチーム全体に有害な言動をしたとき。つまりアルファギークが自分の部下であるケース

std::sort は便利

先日の ABC128_B はいい感じに入れ子のソートをしたいという問題で、自分のコードvector, multimap, set でそれぞれ別の情報をもってがんばってしまったが、解説を読んだら pair を入れ子にすればそれを sort するだけでよしなにやってくれるということを初めて知った。

具体的には

vector<pair<pair<string, int>, int>> v;
sort(v.begin(), v.end());

このように書けば first.first, first.second, second の順に比較して昇順にしてくれる。(参考: pair で書き直したコード

これができるなら tuple でもいいじゃんと思ったらやはり通る。(参考: tuple で書き直したコード

そもそもなぜこういうことができるかというと、 std::sort() はソート対象のオブジェクトに operator< が定義されていればなんでもソートでき、 pairtupleoperator<入れ子になっていてもちゃんとソートできる頭のいい定義になっているため。(リファレンス: std::sort, std::pair の operator<, std::tuple の operator<

pairoperator< の返り値は

x.first < y.first || (!(y.first < x.first) && x.second < y.second)

なので、まず first で比較して、x.first = y.first なら second を比較した結果が返る。 first や second に pair が入れ子になって入っていても再帰的に比較されるのでちゃんとソートができるし、 first に等しい値が入っていたらその集合の中では second でソートされる。tupleoperator< も同様。

さらに、std::sort は比較条件を自分で指定できる。今回の例で言えば、たとえばレストラン番号、レストラン所在地、レストラン点数の順で tuple に格納したとしても、所在地、点数の順で比較するように指定できる。

typedef tuple<int, string, int> T;
bool comp(const T &a, const T &b){
  return get<1>(a) < get<1>(b) || !(get<1>(b) < get<1>(a)) && get<2>(b) < get<2>(a);
}

今回の問題では点数に関しては降順だったので、最後の比較だけ a, b の大小を逆にした。こうすることで、レストランの点数を負にして格納しておく必要がなくなる。(参考: 上記比較関数を std::sort に指定した場合のコード

全然関係ないが、最近 Rust をやりはじめた。このへん を読むと、どうやら Rust でも今回のような感覚は近そうに感じられる。とかくこういった言語知識は息をするように出し入れできるようになりたいもので、昔は高度な知識は language lawyer に聞けばよかったのかもしれないが、リファレンスが気軽に読めてコンパイラインタプリタが親切になった現在では個々人に相応の言語知識が求められるようになっているんじゃないかと思う。(この記事は全然高度ではないが…)

ABC117 C問題 反省会

Streamline

これです。簡単なはずなんだけど解けなかったので反省がてら図解します。

問題設定

数直線上にM個の白いターゲット座標がある
数直線上にM個のターゲット座標がある

上図のように、数直線上に M 個の座標があって、それらを N 個のコマですべて訪れたい。はじめにコマを置くのは手数に入れず、コマの移動(前後 ±1 に限る)を 1 手と数えた場合、最短何手ですべてのターゲットを訪れられるか。

実験

具体的な場合から考えてみます。まずコマを移動させる方向は左から右、または右から左のどちらか一方向に限ってよいでしょう。行ったり来たりしても移動が増えるだけだからです。

今回は左から右へのみ移動することにします。

N = M の場合

すべてのターゲットにコマを置き、黒く塗りつぶした
すべてのターゲットにコマを置いた

特殊かつ考えやすい場合から考えてみます。コマの数 M がターゲット座標数 N に等しい場合、0 回の移動で目的は達成されました。上の図ではコマを置いた座標を黒く塗りつぶしました。

N = M - 1 の場合

右端のターゲットだけ空いていて、そこへ左隣のコマを移動する
コマが 1 つ足りない場合、 1 区間ぶんの移動が必要

さきほどのケースから、コマを 1 つ減らしました。上図ではとりあえず右端のターゲット座標が最初に空いていることにしました。するとその左隣のターゲット座標に置いたコマを右端のターゲット座標に移動させればよいですね。

このとき必要な移動回数は、いま注目している 2 つのターゲット座標の間隔に等しいですね。

最適な区間を選ぶ

移動回数をできるだけ少なくしたいので、最も短い区間を 1 つだけ選びます。

左端の区間が最短の図
ターゲット座標間の間隔が最短の区間を選ぶ

上図では、左端の区間が最短なので、それを選びます。

コマをもっと減らす

短い 2 区間を選んだ図
コマが 2 個不足したら、最短の 2 区間を選ぶ

さきほどはコマがターゲット座標に対して 1 個足りませんでしたが、さらにもう 1 個、合計 2 個足りない場合はどうすればよいでしょうか。

最短の区間はもう選んであるので、次に短い区間を 2 個めとして選べば、最小の移動回数ですべてのターゲットを訪れることができます。

一般化

ここまで来たら、もうコマをどんどん減らしても問題ありませんね。結局、コマの不足数である M - N 個だけ、ターゲット座標で区切られた区間を短い順に選ぶことで、最小の移動回数ですべてのターゲットを訪れることができます。

本当に?

選ぶ区間が連続していなくていいのだろうかとか、コマを 1 個ずつ減らしていったら選ぼうとした区間の右端や左端のコマがすでになくなっていたりするんじゃないかとか思うかもしれませんが、そのような心配は不要です。

ここでは、左から右に移動すると決めていました。すると

区間を選ぶ」ことは「その区間の右端には初めにコマを置かないと決める」こと

になります。この時点で「選んだ区間の右端のコマがもうなかった」という事態がありえないことがわかります。また選んだ区間が連続していなくても、その区間の左端にコマがあれば選んだ区間の右端を訪れることができます。そこにコマがない場合は、左に隣接する区間も既に選ばれたということであり、ここで数直線の最も左端にあるターゲット座標には必ずコマが置かれているので、左側からいずれコマがやってくることがわかります。

解答

  1. ターゲットとなる座標の隣同士の区間長を計算してソート
  2. ソートした区間の短いほうからコマの不足数 M - N 個だけ選ぶ
  3. 選んだ区間の長さの総和が最短移動回数

お粗末さまでした。

Geant4 で新しい物理過程をつくる

Geant4 で新しい物理過程を入れたくて、OSSだしドキュメントも充実しているし論文も講習会資料もあるけど、どこを読めばいいのかわからない、または読んだけどわからないという人向け。

実装済みの物理過程はたくさんあるのですが、それでも未実装な物理過程もあります。そんなニッチな物理過程をシミュレーションしたいときは、自分で実装します。

僕が実装したのが離散過程でしたので、以下は離散過程を中心に述べます。

Geant4 の初歩的な知識と C++多態性の理解を前提とします。

ステップを理解する

ステップという概念があります。ステップの切り方と、切れ目で何が起こるか分かれば実装の大きな助けになります。

まず2017年初心者講習会のレクチャー資料「放射線シミュレーションの概要」の p.12 を見てください。

run --> event --> step --> track

括りの大きさでいうと、こんな階層構造ができています。

プログラム1回の実行 (run) が、粒子の生成から停止までの流れ (event) を任意の回数だけ計算します。Event 中では物理過程*1が何回か起こります。物理過程で区切られた区間をステップ (step) といいます。現在粒子がどういう状態にあるかはトラック (track) が保持しています。

物理過程で区切られた区間をステップとしたので、ステップの終点では必ず何かしら物理過程が起こります。これこそ実装したかった新しい物理過程です。このとき起こる現象を、仮想関数 G4VDiscreteProcess::PostStepDoIt() のオーバーライドとして実装します。

ステップの終点でおめあての物理過程が起こることはわかりましたが、ではステップの終点が起こる場所を決めるのは誰でしょうか。

ステップの長さを決める

ステップの終点、つまり物理過程の発生点までの距離を決めるのは、サイコロです。サイコロの出目の決まり方は「放射線シミュレーションの概要」の p.17 や Appendix を見てください。累積確率がサイコロの出目にまで高まる距離がステップの終点です。ここで重要なのは、これで決まるのは Number of Mean Free Path (NMFP) という無次元量であって、物理的な距離ではないということです。定義として、 NMFP は発生点までの物理的な距離を平均自由行程で割ったものです。平均自由行程数とでもいいましょうか。 *2

NMFP は平均自由行程の何倍かという無次元量なので、物質によりません。仮に粒子がサイコロをふって、 NMFP = 2 だけ飛ぶと決めたとします。この粒子の飛跡が 2 つの異なる物質をまたいだとし、片方の物質で NMFP = 1 だけ、もう一方で NMFP = 1 だけ飛んだとしたら、それぞれの物質中で、その物質における平均自由行程ぶんだけ飛んだことになります。

NMFP で次に起こる相互作用を決める

NMFP を導入するのは計算量の抑制が目的だろうと思います。NMFP なしだと複数の相互作用から次に起こるものを決めるのが大変です。

まず、ある 1 種類だけの相互作用だけが起きると仮定します。 NMFP は一旦忘れます。現実で粒子が飛ぶときには、物質の性質から散乱断面積が決まり、平均自由行程が決まります。粒子が飛んでいく方向に物質が複数あっても、累積確率が十分に高くなるまで逐一平均自由行程を取得していけばステップの長さはいずれわかります。

ここで、 1 種類だけ相互作用が起こるという仮定を外し、任意の種類の相互作用が起こるとします。すると、次に起こる相互作用がどれであるかを決める必要が出てきます。そのために想定しうるすべての相互作用に対してステップの長さを計算し比較する必要があります。

しかし実際に起こる相互作用はステップが最短の 1 つだけで、しかもその相互作用が起こると粒子が飛んでいく方向が変わります。そうなるといま起きたもの以外の相互作用に関するステップ長の計算が無駄です。この無駄は各相互作用について物質とは無関係に NMFP をサイコロで決め、 NMFP が最小であるものを選択することでなくすことができます。

NMFP の比較で次のステップの物理過程が決まることはわかりました。ところで、1 ステップが複数の物質をまたぎそうなときはどうしたらよいでしょうか?この問題に対処するために、物質境界の通過もステップの終了点としましょう。すなわち、候補となる物理過程の NMFP に平均自由行程をかけた実際の空間における距離と、物質の境界までの距離を比較して、境界までの距離のほうが短かったらそこで 1 ステップを終えます。境界をまたいだあとは、また同様の比較を行います。これを繰り返すことで粒子の生成から停止までを追うことができます。

なお、NMFP に平均自由行程をかけて実際の空間における距離に換算する際、物理過程ごとに物質の情報から平均自由行程を計算しますが、この計算は G4VDiscreteProcess::GetMeanFreePath() をオーバーライドしたメソッドとして実装します。

ステップ開始から終了までの流れ

まとめましょう。いま粒子が新たにステップを始めようとしています。

  1. 想定される物理過程すべてについて、 NMFP がサンプリングされます。
  2. NMFP に平均自由行程をかけた実際の空間での距離と、次の物質までの距離のうち最短の過程が次のステップを決めます。
  3. 粒子が輸送されます。このときの輸送距離はすべての候補の残りの距離から差し引かれます。
  4. ステップの輸送が終わると、そのステップを決定した物理過程が起こります。
  5. 次のステップを決めるために、いま起こった過程だけ NMFP が再サンプルされます。すべての過程について、2 に戻って次のステップに行きます。

メソッドが呼び出されるタイミング

ステップが繰り返される流れは以上ですが、各メソッドがいつ呼び出されるかをまとめましょう。

  • PostStepDoIt(): ステップ終了点で物理過程を起こす。
  • GetMeanFreePath(): 次のステップを決めるとき。物質境界をまたいだ直後もこれに含まれる。

これら 2 つは自分で実装する必要があるものです。ついでに次のメソッドを知っておくと理解の助けになると思います。

具体的実装

具体的にどう実装するかについては、既存のプロセスの実装を真似るのが計算量的に安全かと思います。ツールキット開発者向けガイドのハドロンの物理過程のセクションなどが参考になるでしょう。ソースコードを読む際は doxygen は参照箇所がわかって便利ですし、 GitLab の Geant4 リポジトリは検索ができて便利です。(例: 可視光光子のレイリー散乱の実装*3

新しい物理過程をプログラムに組み込む

新しく作った物理過程をプログラムに組み込む方法は2017年初心者講習会の資料や各種ユーザーガイドを参照してください。通常どおり Physics List に追加するだけです。

*1:一般的な言い方では相互作用

*2:平均自由行程を相互作用長 interaction length という分野もあるようです。実際、Geant4 コードでも使われています。 cf. G4VDiscreteProcess.cc

*3:Geant4 は多くの研究者の貢献によって成り立っており、ドキュメントのメンテナンスも研究者らの好意によって成り立っています。それを鑑みると最良のリファレンスはソースコードだろうと思います。