脳log[2023-02]

2023年02月03日 (金) こういうの好き。やってみた。「簡易版職業適性テスト（Gテスト） | job tag（職業情報提供サイト（日本版O-NET））」■もっともプリミティブな、脳みその形とでもいうようなものを知るためのテストかな。Result.png / plot.png / plot2.png / plot3.png■展開図から立体を選ぶ検査 A (空間判断) の成績が一番悪い。半分も解けていない。この成績が上がるだけで赤丸(自分の位置)が EG (エンジニア) の水色球に近づいていく。最も近いのが MS (マルチスキル) の桃色球。検査 C (数理)がちょっと浮いてる以外はほぼ桃色中心と一致している。■検査 A では１、２問を除いていいペースで進めていたつもりだったので、適性がある人とは基本となるペースが全然異なってるんだろうなと思う。検査 B (言語) は拙速気味にだいぶ飛ばして進めていたけどそれでも４分の３しか到達できなかった。こうなると何も読まずにクリックしていくだけでも完答は難しいんじゃないかと思うけど、きっかけとなったツイート(「厚労省のIQテストっぽい奴で職業診断できるやつ、やってみたが、うーん… どうなんだろうこれ？ https://t.co/32xsKAkZIa https://t.co/NvEWICJZN6」)の下に満点の人が現れている。無理ゲーではないのか……(困惑)。

ツッコミを入れる

2023年02月05日 (日) [BOOX Max2] １月のアップデートで 3.3.1 になったのだけどこのバージョンには注意が必要なように思う。自分は自炊したスキャン画像を束ねた PDF をプリインストールの Neo Reader で閲覧している。アップデートで 35044 になったバージョンでは全体の反応がきびきびしていることに気付く。ハードウェアが同じならからくりはどこにあるのか。レンダリング品質が劣化している。システム上で４種類から選べるリフレッシュモードでは最も高品質なモードを選んでいるにも関わらずだ。正直ひどい。文字の線に穴が空いたり棘が生えたり、全体につぶつぶしている。コントラスト設定にある画像のディザリングという項目を ON にしたり OFF にしたりするとそのときだけは以前のなめらかな線で描画されるけど、その状態は維持されない。Neo Reader の画像のレンダリングに問題があって、関係しそうな設定も無視されて役に立っていないように見える。■Neo Reader を起動した状態でシステムステータスバーを表示するとリフレッシュモードがスピードモードに変更されていることがわかる。しかし設定変更のための場所には「アプリの更新設定をご利用ください」と表示されるのみで変更ができない。■Neo Reader の画面リフレッシュというメニューでより細かくリフレッシュモードが設定できるみたい。おおまかにノーマル/リーガル/スピードから選べるように見えるけど、ここで選ぶノーマルモードがスピードモード品質なところが問題になっている。高品質なモードを捨てる意図はないだろうから、設定が反映されない不具合だと思いたい。はよ戻せ。■Neo Reader のメニューで画面リフレッシュの１つ下にある設定という項目を選んで設定の一覧を表示して特に何もせずに閉じるだけで描画がなめらかになった。ちなみにシステムステータスバーの表示は一時的に変更されたスピードモードのまま。■まとめるとこう。Neo Reader はシステムの設定とは別に独自の画面リフレッシュ設定(ノーマル/リーガル/スピード)を持っている。Neo Reader を使用しているときはシステムのリフレッシュモードがスピードモードに固定されて変更できなくなる。Neo Reader のリフレッシュ設定はアプリを開き直すたびに無視され、(Neo Reader が定義する)スピードモードで描画がされる。しかしアプリの「設定」画面(「画面リフレッシュ」の１つ下の項目)を一度でも開くことで画面リフレッシュの設定を反映させることができる。なお、リーガルモードとノーマルモードの違いは確認できなかったので、実質的に Neo Reader の画面リフレッシュの大枠はノーマル/スピードの２択になる。操作を繰り返してるとリフレッシュに失敗して画面が重なる現象が何度も起こってるので、諸々質の低いバージョンなのだろう。とりあえず面倒でも手順を踏むことでまともな表示にできたのは助かった。

ツッコミを入れる

2023年02月06日 (月) [AtCoder] 精進。先週末あった Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）-F「Integer Division」(ぎりぎり黄 diff)。当日は D と E をひとしきり考えて諦めた後は F に狙いを定めていた。狙いはまちがっていなくて、３問のうちまず F が解けた。■提出 #38678223 (AC / 143 Byte / 91 ms)。前からの DP で解ける。何を覚えておいて何が計算したいか。１桁目が A、２桁目が B だったとして、(AB+AB) に当たるものを覚えているとする。３桁目が C だとして求めたいものは問題の定義から (ABC+ABC+ABC+ABC) なんだけど、ABC+ABC は覚えておいた (AB+AB) に C を掛けて求まるとして ABC+ABC はどう求まるか。覚えておいたものを 10 倍すると (AB0+AB0) となって惜しい。不足は (1+A)C であるが 1+A とは何か。２つ前までに覚えていた値の和だということがサンプルを丁寧にデバッグしていてやっとわかった。わかったというか見つかった。がちゃがちゃデバッグ、良くないね。■D 問題「Range Add Query」はまず操作の累積和を記録して、区間の末尾 K 要素が０になるかどうかを見たいと思った。しかし数列全体を通した累積和から区間の前 K-1(？)要素の影響を引き算する方法がわからなかった。■E 問題「Wish List」は前から順番に何個の商品を選んだ場合に最小コストがいくらかを記録していく DP をやりたいと思った。前に最初何個の商品があって最後何個まで減るかが決まっていれば最適な順序コスト(C)の選び方がわかる。そしてその選び方は前にある商品の選び方に影響を与えない。M 個の商品については必ず選ぶこととし、それ以外の商品は選ぶ場合と選ばない場合を両方考える。時間に追われてふわふわしてる頭で書ける DP ではないのだ。■E 問題。F の AC から２時間弱、ここまでの日記を書いてからじっくり集中して AC です。提出 #38679476 (AC / 465 Byte / 2166 ms)。■残った D 問題は「あ、一応。典型の考え方も含めて。「この問題そのものが有名」という話ではない。・区間に足し引きする問題は、imos法の逆の考え方で、始点・終点に足し引きする問題に変換できる・足す区間が一定（長さK）の場合は、modKが同じ場所しか互いに影響を与えないので独立で考えられるの2つが典型」とか「X_i, X_{i+1}, \cdots , X_{i+K-1}にcを加算するとはどういうことでしょう。Aを多項式、すなわち A_1 + A_2x + \cdots + A_Nx^{N-1}と考えると、 c(x^{i-1}+ \cdots x^{i+K-2})を足すことです。つまり、この問題は、 1 + x+ \cdots + x^{K-1}の倍数を足して0になるか、言い換えると多項式を 1 + x + \cdots + x^{K-1}で割って余りが0か否かということです」とかのネタバレをすでに読んでしまったのだけど、だからといって自分で書ける目途は立たないんだな。咀嚼が足りない。

ツッコミを入れる

2023年02月07日 (火) [AtCoder] 精進。ABC008-D「金塊ゲーム」(黄 diff)。以前順番に埋めていっていたときに埋めきれなかった古い ABC の問題。今となっては何がわからなかったのかわからない。だって今日は以前に立てた方針をそのまま実装しただけなのだから。■提出 #38698822 (AC / 469 Byte / 155 ms)。最初四角の枠があって、機械を動かすごとに枠が４分割される。枠の中にあるどの機械を一番に動かすかのがいいかは総当たりで決める。枠を定める４つの値のバリエーションは N+1 個から２個と N+1 個から２個を選ぶ組み合わせの掛け合わせだから高々 N の４乗程度。N≦30 だから N^4≦81万。枠の中にある機械の数は N 以下だから全体で N^5≦約2400万を見込んでおけば足りる。定数倍が軽ければ Ruby でも通る。

最終更新: 2023-02-08T02:07+0900

♪ [Ruby] Ruby クイズ (複合代入編)

a = b = 0 # 初期化
a += b += a += 1 # 本題
p a #=> 1? 2?

右から順番に a に 1 を足して(a=1)、b に a を足して(b=1)、a に b を足して(a=2)、と考えると間違える。「自己代入」を読むと「この形式の代入は 式1 = 式1 op 式2 と評価されます。ただし、op が &&, || の場合には(略)」と書かれている。一番右の a += 1 が評価される前に一番左の a += が a = a + と分解されていて古い a の値が評価中の式の値として一時的に記憶されているのだと考えられる。a の値は 1 になる。ちなみに C++ では 2 になった。

この前の ABC288-D が解けなかった理由のひとつにはこの罠に気がつかなくて合わせるべき数字がそもそも間違っていたということがある。それがなくても解けなかったのもたしかだけど。

ツッコミを入れる

2023年02月08日 (水) [AtCoder] 精進。埋めきれずに穴が空いていた ABC035-D「トレジャーハント」(水 diff)。ちょっと考えて気が付いてほしいんだけど、滞在する町は１つに決めていい。複数の町に滞在する理由はない。あとは往路と復路に分けて町１からの最短距離がわかればいいのでダイクストラ法を２回やる。えっと、なんで埋められなかったの？>過去の自分■提出 #38710483 (AC / 1026 Byte / 480 ms)。■もちろん経験からつまずきポイントを３つまで挙げることができる。１つ目は「なんで滞在する町を１つに決めていいの？」たとえば町１を出て町１に返るパスが与えられたとして、滞在する町はパスにある町のうち１分あたりの報酬が最高の町一択になるでしょう。２つ目の疑問は「そうはいってもどのパスが答えになるかはわからないじゃない？」視点を変えて、ある町に滞在すると決めてからその町での滞在時間を最大化するパスを考える。それはグラフでおなじみ最短経路問題になる。３つ目の疑問は「町 A に滞在すると決めて最短経路を求めたら経路にある町 B の滞在報酬の方が大きかったりしそうなんだけど？」それは町 B に滞在すると決めたときに考える範囲なので無視して大丈夫。４つ目の疑問は「すべての町について町１に返る最短距離を求めると時間がかかりすぎるんだけど？」辺の向きを逆にしたもうひとつのグラフで町１を始点にした最短距離を１回だけ求める。■たぶん１年半前の自分は３番目の疑問に答えられなくて分割した問題が解けなかったのだと思う。別の問題に対する感想だけど「難しいなこれ。ある時点のループにおいてベストを求めなくていいし不正確でもいいということを見極めて受け入れるのは」「自分はこの手の見極めが苦手みたいだ」と書いたように、問題を分割したにもかかわらず分割した枠の外にあるより良い解に目移りしてしまって問題が解けなくなってしまうところが８か月前までの自分にはあった。

ツッコミを入れる

2023年02月19日 (日) [AtCoder] 精進。今日あった Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290）-E「Make it Palindrome」(水 diff)。時間中は、各数字がすべての連続部分文字列の中で左側に何回出現するかと右側に何回出現するかを数えようとしていた。それはうまくない。ヒントを読みました。「E: バケットソートしてから端から貪欲」。すべてのペアについて個別に考えるのが許されない制約だけど、端から貪欲が可能ならペアを考えても良い。ただし何らかの属性でひとまとめに取り扱う必要はある。■提出 #39053926 (AC / 210 Byte / 342 ms)。グループ化してソートして積算しました。ある要素について左右にある要素数のうち少ない方を考える。少ない方の要素数が M1,M2 である２つの要素がペアになったらそのペアを回文の中の比較対象として含む部分文字列は min(M1,M2) 個ある。■Ruby によるすべての提出を見てると自分の 342 ms は目に見えて遅い。最遅である。左右にある要素数の規則的な増え方減り方に注目すればソートする手順が余分で、そのせいで遅くなっている。提出 #39117164 (AC / 162 Byte / 157 ms)。遜色ない速さになった。実はこの書き換えは全然すんなりいかなくてバグに苦しんだ。理解の浅さが露呈したわね。■■■D 問題「Marking」の設定が灘校文化祭コンテスト 2022 Day2-A「ACPN」と同じだということに遅まきながら気が付いた。それを解いたときの日記に「実験したら M 個の剰余が出現する周期は K と M の最大公約数で分割されるようだった。たとえば M が 10 なら剰余は 10 種類あるが、K が 5 のとき最大公約数は 5 で、M 個の値は周期 2 の組が 5 組となって出現する。あとはこの周期で N が割り切れるかどうか」と書いてあるんだけど、えっと、なんで「割り切れるかどうか」なのかよくわかりません。去年は今より頭が働いていたのだなあ。

ツッコミを入れる

2023年02月28日 (火) [AtCoder] 日曜にあった AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS）のふりかえり。■A 問題「camel Case」。ASCII コードで大文字小文字は特定の１ビットを見ればわかる(それ以外のビットは共通)。■B 問題「Trimmed Mean」。フィギュアスケートとか芸術競技の採点方法っぽい？ソートして真ん中を取り出す。■C 問題「LRUD Instructions 2」。賢い判定方法があるかなとちょっと気にしてみたけど、普通にメモを取ってシミュレートした。■D 問題「Flip Cards」。D は DP の D！直前のカードが A のときの場合の数と B のときの場合の数から今回のカードが A のときの場合の数と B のときの場合の数を出す。初期値をどうするか迷った。A のときの場合の数を 1、B のときを 0 にして、答えは (A のとき+B のとき)%998244353 にしたら合っていた。■E 問題「Find Permutation」。ABC285-D「Change Usernames」を思い出す問題。自分より小さい要素がない要素を順位確定要素としてキューに追加して他の要素の前から取り除いてはキューを伸ばしていった。ただし、どの時点でもキューの長さは１でなければいけない。２つ以上の要素がキューにあるとどちらが小さいかわからない。キューの長さが１ずつしか増えないとわかったときにちょっとせこいことを考えて、キューをそのまま答えの配列にしようとした。残念ながらそのまま答えにはならなくて、順番と添字を入れ替える処理が必要だった。自分の提出にはバグがあるような気がしていて、キューが途中で途切れたときに対応できていないと思う。運良くそういうケースがなかったのかな。E 問題に関連してトポロジカルソートの語が頻出している。トポロジカルソートがわかるなら ABC041-D「徒競走」(青 diff) が埋められないなんてことはないはずなんだよなあ(まだ埋められていない⇒わかりません)。■F 問題「Teleporter and Closed off」。都市 k を通らないケースというのは、都市 k-M+1,k-M+1,...,k-1 から都市 k+1,k+2,...,k+M-1 へ飛ぶ 1+2+3+...+(M-1) 通りが上限であり、M は 10 以下なので、各 k について１つ１つ調べて良い。あとは k の手前の都市へ移動する最小回数と k の奧から移動する最小回数が１ステップでわかればいいので、前からと後ろからの２回 DP をやっておく。考察にはそれほど悩まなかったけどバグ取りをしたりしてるうちに気が付いたら 45 分経っていて驚いたよね。しかも TLE だった。2115 ms であり 22xx ms ではないから 115 ms を削る小手先の変更を２つ入れて AC。ペナルティと合わせて 9 分のロスだった。それ以前に時間をかけ過ぎていて E までを 30 分で片付けた貯金がパーなんですよ。■G 問題「OR Sum」は制限時間８秒がやばいよね。考察であっさりスマートに答えを出す系の問題ではない。あきらめちゃうよ。■自分のすべての提出。コンテスト成績証。■E 問題への提出の潜在的バグについてお風呂で考えてきた。キューが途中で途切れるのはどういう場合だろうか。たとえばグラフが複数の連結成分に分かれているとき。これは始点が複数あると検出されるならバグには当たらない。しかし始点がなかったら。１つまたはそれ以上の連結成分が環状部分を持っているなら、キューは途切れる。バグか？おそらくそういうケースは「入力に矛盾しない A が存在する」という制約により除外されている。潜在的バグはバグではなかったしテストケースにも不備はなかった。そこまで見切った上での割り切った実装(９行目の `if (1..N).all?{|n|`)だったらかっこよかったんだけどな。ABC285-D「Change Usernames」のときも「入力制約のきれいさに助けられた」って書いてるんだよなあ。

ツッコミを入れる