/(.)\1*/ みたいな正規表現パターンでうまくできないかとあれこれ考えて、できなかった。同じ文字の繰り返しを意味するパターンって難しくない？ キャプチャを使うとできるけどそうすると String#scan メソッドが役立たずになるので困ってしまった。■D 問題「Election Quick Report」。D 問題で BIT とかプライオリティキューとか使いたくないよね。考えました。最高得票者が入れ替わる瞬間がつかまえられさえすればいいので、誰が最高得票者で得票がいくつかがわかればそれでいい。■E 問題は解けなかったのでひとまずとばして F 問題「Colored Ball」。ただのマージテク。考える時間も書く時間もいらない。E 問題を考えていたせいで F 問題の AC が 30 分近く遅れたのを挽回するためには、最終的に E 問題も通すほかなかったんだけど、結果はあのとおり。残念無念。■■■E 問題「Stamp」。難しかったよね。時間内のこの提出 #47726211 (WA×5) だけど、19 行目が嘘貪欲なのはわかっていて、でも残り数分で新しい方針をでっちあげることもそれを実装することもできない。昨日はもうお手上げだった(あ、この日記は翌日に書いています)。■提出 #47752502 (AC / 515 Byte / 393 ms)。これは翌日の今日なんとなく転がしていたアイディアを実装したもの。貪欲なのは同じ。違うのは起点が複数あること。昨日は左右端を起点にしてスタンプを上から押したり下に差し込んだりする操作を考えていた。今日は T と完全一致するすべての場所を起点にして、そこから(端でなければ)左右にスタンプを繰り返し差し込む操作を考えた。操作の起点を複数考えることでスタンプを上から押す操作を考えなくて済んだのが昨日との違い。複数の可能性を考えなくてよくなり貪欲法がはまるようになった。最終行の判定がやや複雑で条件が３つある。両端の条件に２つで、貪欲法と貪欲法の狭間に残る部分の判定に１つ。■たしかに D 問題とのあいだで配点はひらいているけども、これを E 問題に配置しようって判断が、それもあの F 問題の前に配置しようって判断が謎すぎる。でも考えるのが楽しい問題だった。知識問題というよりのーみそこねこね(コンパイル)な問題だったのでは。=SUM( (A1 > {0,10,20,40,100,200}) * (A1 - {0,10,20,40,100,200}) * ({10,1,2,4,5,8}) )(※記憶を頼りに書いてるし Excel も持ってないので不正確な部分があるかも)。まず自分は波括弧記法を知らないんだけど、たぶん６行１列か１行６列の行列を表してるんだろうなと思う。そして行列にスカラー値が掛けられるのはわかるけど、比較演算を分配する発想がなかった。1,0 に変換されているらしい真偽値の仕様も知らない。そして単価表を反映した３番目の行列の中身、特に２番目以降の値が注目に値すると思う。発想の転換ですよ。それで全体としてこんなに簡潔になった。値上げをこの式に反映させることはできるとしても、イチからは書けないよね。コンピュータの動きを変えるには、コンピュータの中のデータを少し書き換えればよいのです。すなわち、社会が環境の変化に対して、記録されているデータを書き換えるだけで対応できるのです。」 社会が～がどこに繋がるのかわからない。たぶんがを抜いて社会環境の変化だと思う。■71-72 ページ。「
サービス利用や書類において利用者ごとに割り振られる符号で、パスポート番号、基礎年金番号、運転免許証番号、住民票コード、マイナンバー、保険者番号などがあります。」 個人情報の例として保険者番号が挙がっている。元になった政府のページ(「「個人情報保護法」をわかりやすく解説 個人情報の取扱いルールとは？ | 暮らしに役立つ情報 | 政府広報オンライン」)からが保険者番号なので間違いではないのかもしれないけど、保険者って組合などのことなのでは？ 保険の文脈で個人に対応するのは被保険者という用語なのでは？ 保険者番号って「サービス利用や書類において利用者ごとに割り振られる符号」(本と Web より)とは違うのでは？ 保険者番号について検索したら保険者番号の中にも保険者別番号みたいな紛らわしい番号が入れ子になってるみたいだけど、だからといって変わることはなさそうだし。■74 ページ。「
さまざまなサービスのログインの際に、ID とパスワードのみならず、30 秒ごとに更新される６桁の数字を打ち込んでいます。これにより IT とパスワードが盗まれたとしても、スマートフォンも同時に盗まないと IT サービスにログインできないのです。」 盗まれるのは IT とパスワードではなく ID とパスワードだと思う。直近で IT というワードを使っているせいもあるだろうし、アイティとアイディという音の近接性に引っぱられたタイポということもあると思う。実際濁点の有無によるタイポってよくやるんだ。キーボード上での近接ではなく音の近接に引っぱられて間違える。■93 ページ。「
見れません」 学校で習ったら抜き判定法。まず未然形(～ない)を作ります。語幹が「～aない」というようにあ段に変化するなら五段活用動詞なので可能動詞が作れます(作るの未然形は作らないであり tsukura-nai なので。一方で見ないは mi-nai であり上一段活用なので作れない)。今になって面白いと思うのは、これって完全にネイティブ向けの説明だなというところ。まず未然形がどうかという答えがあって、そこから活用のルールを得ているところ。ルールに従って活用させているのではないんだ。判定法を役立てるためにはまずら抜きを疑うことができないといけないんだけど、今では「見れる」より「見られる」の方に違和感を覚える人の方が多いだろうなと思う。だって年齢を問わずそんな風に話す人まわりにいないでしょ？ 「俺は例外だ」って言いたいけど、自分は話をしない人だった。■■■122 ページ。「
社会人として知っておかなくてはならいのは」 脱字。■154 ページ。「
生産性を改善させるためは」 脱字。■159 ページ。「
Society 5.0 といった日本政府しか使っていないバズワード」 バズワードのバズはブザーと同根らしい。うるさく鳴るもの。多くの人が口にする言葉というのは、専門用語とは対極の扱いを受けて意味や本質を失ったり逸れたりしていくことが容易に想像できるけど、そういうものを同一視した結果が「転じて～の意」と辞書で紹介されるのかもしれないけど、今のところここでのバズワードの使い方には「一人で爆笑」と同じ矛盾を感じる。
2 1 4 3 という順列は前半後半の２グループに分かれていて、１回のスワップで達成できる辞書順最小は 2 3 4 1 なので、1 と 3 をスワップする必要がある。何をどう判断して 1 と 3 をスワップすることができるのか。さっきのルールでは 4 を見ているときに 1 を引っぱってくることになって良くない。グループの末尾の位置にあっては多少の妥協をして現在の要素より大きい値を引っぱってくることになっても他所のグループとスワップをしなければいけない。それで 1 を見ているときに 3 を引っぱってくることができる。そうした結果が本当に辞書順最小かというのは実はよくわからないところだけど……。■提出 #46663066 (TLE×18) のち 提出 #46665195 (AC / 772 ms)。アルゴリズム的な違いはない。スワップ候補というのは１度に２つだけ準備できていればいい。最小の要素を持つグループと、２番目に小さい要素を持つグループ。現在見ている要素と異なるグループが実際のスワップ対象になる。この２つの要素を配列の外に出して変数で参照するようにしたりして配列参照を減らしたら TLE が AC になった。■グループの管理とスワップ候補の管理を同時に行うために、UnionFind のルートの決め方をいつものようにサイズの大きい方を新しい代表にするのではなく、値が小さい方を新しい代表にしている。そうすると Find 関数での書き換え回数が増えてまずい場合があるのだけど、代表と最小要素を別々に管理するのは煩雑でミスが避けられない雰囲気だったのでそうしている。スワップ候補の列について。最初にソートして用意するんだけど、スワップ１回につき１つの候補が列から消えることになる。現在見ている要素の代表が消える場合もあり必ずしも先頭２要素のどちらかが消えるとは言えないし、Ruby には SortedSet がない。今から BIT を持ち出すのは大仰で気が進まないし、消す操作を配列に対して素直に行うと実行時間が足りないので、スワップ候補の先頭２要素についてだけ今もまだスワップ候補(グループの代表)のままであるかチェックをするようにして、結果的に削除操作を遅延させている。こういう部分であるとか、数列を先頭からひとなめするだけで辞書順最小を達成するだとかいう部分があるから、効率良くやるのがたいへんな問題だったと思う。スワップするためには最小の要素がどこにあるかを知る必要があって、それを追跡する逆引き配列を予め作成してスワップの際には同時に更新しもしている。たいへんだなあ。そのときそのときで全体を見て最適な選択ができたならもうちょっと簡単だった。■昨日のコンテスト成績証。解くべき問題を解いて -5。まあ順当。B 問題が解けたのえらかったと思う。約分なんて高等数学テクニックとか式をにらんでの２の素因数探しとか、そんなんもう何十年も前に忘れてんねん。■■■「そうした結果が本当に辞書順最小かというのは実はよくわからないところだけど……」。この問題の設定においては位置と値が等価だということをよく考えれば納得できるのではないかな。「グループの末尾の位置にあっては多少の妥協をして現在の要素より大きい値を引っぱってくることになっても他所のグループとスワップをしなければいけない」と書いたけど、この「グループの末尾の位置」というのは必ず１を含むグループの末尾のことだし、「他所のグループ」というのは必ず全メンバーが後方を占めているグループのことなので、そういう関係を踏まえればスワップの位置づけがわかる。いや……、考えれば考えるほど「必ず１を含むグループ」であるということが俄には承服しがたいな。やっぱりそうだと思うんだけど。