脳log[2020-12-25～]

最終更新: 2020-12-26T00:15+0900

♪ [WR250R] ヘルメットホルダーが壊れたけどなんとかなったっぽい。

６年目に入った WR250R。ヘルメットホルダーがカチッと閉じなくなってただのフックと同じになった。

世の中には鍵付きのメットホルダーすら信用しない人がいるらしいが、自分はそこまでではない。だけど本屋なんかに行ったときにヘルメットを無造作にミラーに引っ掛けて、ということもできないので、その他の機会と合わせて月に数回から10回くらいの頻度で使用していると思う。酷使しているつもりはないが壊れた。壊れたメットホルダーを検索すると割と上位にこういうものが見つかった>「WR-Rのヘルメットホルダーが壊れた・・・ – Levico's BLOG」 お仲間。

メインキーと共用だというところに価値の半分があるので、新品交換で価値が半減しないかが心配。

T30 のトルクス１本で車体から外れる。バックプレートはプラスネジ２本。２本は同じだと思ったが組み直すときに一方が途中までしか入らなかったので入れ替えてみたらすんなり締まった。罠なのか？

バックプレートを外した状態。フックがあるのと反対側、車体側から見ている。表から見た形はこれとほぼ同じ>「【楽天市場】【在庫あり】DAYTONA デイトナ ヘルメットホルダー CT125：ウェビック　楽天市場店」

鍵をひねった状態。中央の銀色のパーツが逆時計回りに30度くらい回転した。色の関係で見にくいが回転軸に巻き付いて伸びた茶色の板バネがケースの上面をこすりながら力を蓄えている。

板バネにこすられて傷ついたケース上面。バネが傷に引っ掛かって位置が固定されるために蓄えた力が解放されない。結果としてフックを差し込んでもラッチが掛からない。残念なことに鍵をひねって強制的に閉じることはできない。スロットルワイヤーが開く・閉じるの２本１組であることの大事さがわかりますね。

一時しのぎだけどバネを取り付ける向きを180度回転させてケース下面をこするようにした。これでもう５年は大丈夫……かな？

最終更新: 2020-12-23T00:48+0900

♪ [AtCoder] パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）／E 問題 Throne

まだ AC をもらっていないし、それどころかひとつの提出もできていないけど、外堀が埋まってきた気がするので経過を書く。

 シミュレーションした。(未提出)

gets
puts$<.map{|ln|
	n,s,k = ln.split.map(&:to_i)
	ss = {0=>m=0}
	until ss[s]
		ss[s] = s
		m -= (s-n)/k
		s += (s-n)/k*-k
		s %= n
	end
	next s == 0 ? m : -1
}

これはサンプルの４つのケースのうち、３番目を除いて正しい答えを出す。３番目の 998244353 897581057 595591169 にもたぶん正しい答えを返すだろうけど、答えがおよそ 250 メガなので数分単位の時間がかかるはず。

N と S と K の３つの数字があるけど、N と K が近接していてしかもべらぼうに値が大きい。ループ１回のイテレーションで全周 N のうち１点だけをテストするのでは最悪 N 回繰り返す。N の上限は１ギガだ。

 たとえば K = N-1 の場合

１回のイテレーションで S-1 の地点に移動する。S 回のイテレーションで玉座に移動することが即座に理解できるが、スクリプトにそれは反映されていない。

 たとえば N と K が偶数で S が奇数の場合

K が２より大きければ(N との関係にもよるが)すべての偶数地点を網羅できるとは限らないが、K が最小の偶数２であっても、スタート地点 S から奇数席離れた玉座に移動できないことはすぐにわかる。これもスクリプトに反映されていない。

 それで？

N と K と S の関係をどういう式で表すのかなあ。LCM だか GCD だかのキーワードは目に入ってるんだけど。

K = N%K という風に再帰的に K を更新していくと最後は 0 に落ち着く。K が 0 になるまでに S をどうにかしたものが K で割り切れれば答えは N/K の倍数±α になりそうなんだけど、S をどうするのか、N-S をどうにかするのか、よくわからない。

最終更新: 2020-12-08T16:28+0900

♪ [AtCoder] 鹿島建設プログラミングコンテスト2020（AtCoder Regular Contest 110）／A,B,C

ARC 級の企業コンであることがわかりやすい表記になった。企業コンだけどいつもの ARC と同じ気構えで挑戦してもいいことがわかりやすい表記になった。

鹿島の名前はブルーバックスの『図解 超高層ビルのしくみ 建設から解体までの全技術』の編者としてと２冊の SD 選書『近代建築の失敗(著：ピーター ブレイク)』『建物のあいだのアクティビティ(著：ヤン ゲール)』の出版社(鹿島出版会)としてだけ目にしたことがある。ジャンルが同じだから関連があるのでは？

 A 問題 Redundant Redundancy

題意を満たすような数のうち脳死で求められるものはすべての数の積+1なんだけど、答えに制約があって N 以上 10^{13} 以下のものを出力しなさいと。

2 から N の数を素因数分解してマージする。素因数がそれぞれいくつあれば 2 から N の数を表現するのに足りるのか。16 なら 2 が 4 つ必要だし、27 なら 3 が 3 つ必要。6 や 18 など複数の素因数を持つ数はとくに考えなくていいかな。

 提出 #18579266 (AC)

ひょっとして求めたものを最小公倍数と呼ぶのだろうか。Integer#prime? なんて便利メソッドを使ってごにょごにょするくらいなら Integer#lcm を使うのが直接的だったんだろうか。

 B 問題 Many 110

入力例１の解説を注意深く読めばわかるはずですが、注意すべき点があります。110 を 100 個連結した文字列の中に、110110 という部分文字列は 99 個見つけることができます。決して 50 個ではありません。

この勘違いを正すのに多大な時間を要した。難しい問題ではないとわかるのに答えが全然合わなくて、神経衰弱になりそうだった。

 提出 #18593923 (AC)

とりあえず答えは出た。

 C 問題 Exoswap

前回より悪くて(20201202p01.04)、３問目にして 20 分しか時間が残っていなかったけど、考えるだけ考えた。

1. 同じ操作が高々１度しか許されていないので、ある数を適正な位置に移動するのに冗長な操作は許されない。
2. まずは数ごとに必要な操作の列を作った。
3. すべての数を満足させるよう操作の順番がひっくり返らないようにしながら、すべての操作列を一列にマージすれば良さそう。
4. 行きすぎて戻るということはできないから、操作が少なくて済む場合は即座に NG。
5. 同じ操作を要求する３つ目の数があれば、それも即 NG。

 提出 #18611107 (TLE×6 / AC×56)

TLE です。メモリの使用量に比例した時間がかかっているような雰囲気。testcase_10.txt は提出によっては TLE にならないことがあり、TLE といえども 22xx ms ではなく 20xx ms であるあたりちょうどボーダーライン上のケースだといえる。そのメモリ使用量が 560 MB。その他の TLE は 570 MB から 632 MB のメモリを使用している。全然ダメって感じではなくて何割か改善したら AC になりそうな期待が、ないかなあ。

特に頭の悪いことをしている部分があるとは思わないんだけど、だからこそ、根本から発想の転換が必要だと言われたら困るなあ。

大量のメモリって、前半の操作列の列挙部分で使ってるのかなあ。見え見えのダメケースを前半部分で拒絶するべきなのかなあ。さっき書いた「同じ操作を要求する３つ目の数があれば、それも即 NG。」とか、今考えたけど「i,i+1 という操作と i+1,i という操作を要求する２数があれば、操作列のマージが不可能なので NG。」とか。

前半部分の列挙について考えていると、後半部分のキューが不要にできそうな気がしてくるなあ。問題の制約って想像よりかなり厳しくて、可能なケースが限られるし、可能な操作列もいくつか考えられる中から一番簡単なものを出力するのに手間はかからなそう。

つまり、数列に対応した(※)配列に右向き左向きをメモして、山と谷があって、高いところ(流れの発するところ)から低いところ(流れの集まるところ)へ向かってテキトーな順番で列挙するだけなのではないかという……。

※数に対応させるのか数と数の間に対応させるのかで迷ってコードにならない。今は「間」かなという気がしている。

 提出 #18639675 (AC / 424 ms)

とりとめなくいろいろ書いたけど、結局、前半部で見え見えのダメケースを拒絶して AC になった。

もっと鮮やかに解けるはずなんだけど、当面のモチベーションは消えてしまった。

最終更新: 2020-12-03T19:37+0900

♪ [AtCoder] AtCoder Regular Contest 109／A,B,C,D

先月28日土曜日の振り返り。ARC なので A 問題が 300 点からスタートする。２問解けたらまあまあという感じ。配点が同じ 300 点、400 点でも、ABC のと比べるとちょっと手強い印象を持っている。

時間は長めの２時間。ABC と違って C、D、E、F 問題にはだいたい取り付く島さえないので、時間が足りなくなるということはまずない。簡単すぎるテストと難しすぎるテストは時間が余るという点で共通する。

 A 問題 Hands

上の階に上がるのに階段と廊下の２種類の手段があるというのが不思議な設定だが、床の高さが半階分ずれた２棟が上りと下りのスロープで結ばれていると解釈するツイートを読んだ。なるほど。ところですべてのフロアが渡り廊下で連結されているなら、それも水平１本ではなく三角形で繋がっているなら、２棟は一体の構造物として設計されているのでは？ そのとき「廊下」はどのような形態になりますか？

 提出 #18452990 (AC)

11分ちょっとで提出している。こうだったらこうだな、こうだったらああだなと考えながらとりあえず書き出してみてそれをそのまま提出した。

 B 問題 log

考えたこと。

• 長さによらずコストが同じであるし、切れ端を捨ててもいいのだから、とりあえず長い方から買えば良い。
• そしてもちろん、長い丸太から切り出して買うのを節約する丸太は、短い方から順に揃える。
• n がいくつのとき、何本分の節約ができるかが問題。
  • 順番に書き出してみれば、長さ１を１本分節約するのに１本の購入が必要。(n=2)
  • そこからもう１本節約するには長さ２を１本用意しなければいけないので、追加で２本の購入が必要。(n=2+3=5)

節約する本数 k から n (の下限)を求める式が n ≧ Σ(k+1) = k+k*(k+1)/2 だということはすぐにわかったけど、n が与えられたときに k の最大がいくつになるのかを求めるのに、sqrt を使ってずっと考えていた。B 問題に取りかかってから最初の提出まで 46 分。

 提出 #18463725 (AC)

n の制約上限は 10^{18} であり、(10**18).bit_length は 60。なんだ探索すればいいじゃないと気がついたらもう問題は残っていなかった。

 C 問題 Large RPS Tournament

RPS って Rock, Paper, Scissors なんだな、たぶん。本番中はよく考えなかったけど。

k の上限は高々 100 ではあるけれど、2^k 通りの勝敗を考えるには大きすぎる数だ。まあ頭の中で考える分にはあまり関係がないので、トーナメントをシミュレーションして、その際に文字列 s のどの部分を参照するのかを確かめていた。優勝者の手、準優勝者の手、準々優勝者の手……がどこからやってくるのか、逆方向のシミュレーションもした。

 提出 #18467915 (AC)

最初の提出まで 30 分。C 問題という段階で解けなくてもともとなので、あせる理由はどこにもない。

 D 問題 く

残り時間は 30 分だったけど考えるだけ考えた。

• 移動方法は３通り。軸となる２つの石を選べば決まる。
• 石の配置は単位正方形を基準にして分類できる。すなわち、ある一角(たとえば左上)の座標と、くの字の折れ曲がり部分の位置(左上、右上、左下、右下)の組み合わせで決まる。
• さて最小の移動回数は？

四角形の座標移動をまず考えた。

• 水平方向、垂直方向に１移動するには２手かかって、くの字の向きが変わる。
• 水平垂直同時に１ずつ移動するには３手かかって、くの字の向きはそのまま。

ここまで考えたが、この安定した移動に入る前と出るときに何手かかるのか数え切れなかった。B 問題のことを思い出して探索すればいいじゃない、ということには気がついたが、その探索がどういう形になるのかおぼろにも想像ができなかった。

というわけで D 問題はひとつの提出も用意できないまま放置している。

あ、３通りじゃないや、５通りある。じゃあいろいろ変わってきちゃうね。

え？ ７通りある？ だから最初から最後まで機械に数えさせるべきなんだな。

最終更新: 2021-01-05T18:27+0900

♪ [COSMOS] システムドライブを SSD に移した。(SSD 初体験)

やっとである。2012年と2015年と2017年に SSD 化の思惑を書いてるけど(20121112、20150812p01)、今や2020年の末である。500GBで6500円である。

2007年に買ったHDDが丸13年間もった。いや、実はもっていない。最近になって不良セクタが見つかって名前も知らないファイルがいくつかロストしたのだけど、ケーブルを抜き差しして問題はなかったことにしていた。それから、ちょくちょくプログラムが一時的に停止するような状況が続いていて、IO 待ちなのかなと。ディスクがお隠れになってるのかなと。ファイルバックアップが正常に終了することが珍しくなったし、３回ほど INTERNAL_POWER_ERROR を理由とする BSoD を見たりもした。検索するとグラフィックスドライバが悪いとか、HDDが壊れてるとかで生じると書いてあるが、ドライバの再インストールとチェックディスクは不良セクタが見つかったときにもう済ませてある。処置無しである。完全な破局が訪れる前の今を限られた猶予として動かねばならぬ。

以前書いたとおり、まずは Complete PC バックアップをシステムドライブが入っているのとは別の HDD にとった。バックアップは毎月やっていることなのだけど、直前にまたとろうとしたら罠があった。少し前にとあるボリュームの容量を拡張しようとして、それは HDD の末尾に配置されていて後ろに空き領域がなかったものだから、拡張するにはベーシックディスクからダイナミックディスクへの変換が必要だという。誘われるままに変換したのが罠だった。ベーシックディスク上のボリュームである C ドライブのバックアップをダイナミックディスク上のボリュームに保存することはできないらしい。ダイナミックディスクをベーシックディスクに戻すにはボリュームをすべて削除する必要があるらしい。罠である。よりによってこのタイミングで。

ともあれバックアップを保存した HDD とフォーマットもしていない新しい SSD だけを接続した状態で Windows のインストール DVD から起動した。インストールは選ばずにその他のオプションから Complete PC バックアップからの復元を選んだのだけど、警告された。復元するとディスクはフォーマットされすべてのデータが失われると。それでも実行するかと。困ったのは、どのディスクがフォーマットされるのか全く示されなかったこと。画面上にはどのバックアップから復元するかを選ばせるリストがあり、T ドライブを選択したのだけど、それをどこに復元するのか、どのディスクがフォーマットされるのか、選ばなかったし提示されなかった。考えてみれば10年以上前にプレスされた DVD が昨日買ってきた SSD のメーカーや型番を知っているはずがないし、フォーマットしていないからドライブレターの割り当てもないし、どういう識別情報が提示できたかわからなくはある、……ような気がしたが、EFI でブートドライブの優先順位を決めるときに型番が利用できるのだから、デバイスに刻まれた文字列が利用できるはずでは？ なんにせよ、いちかばちかで実行したらちゃんと SSD に C ドライブ(と Y ドライブも含めていた)が復元されていた。

さっきから C とか Y とか T とか、その他にもドライブレターの割り当てはないけど特定のパスに接合されたボリュームがいくつか存在しているように、細かくパーティションを分けている。NTFS ではそういうことは一度もないんだけど、ファイルシステムが FAT32 だったときはファイルの全ロストが何度もあった。BSoD もしょっちゅうだったし、そこからのコンボが現実の恐怖だった。失われるのはパーティション単位だから、巻き添えを少なくするために分けている。マウスを使ったファイル移動の既定がボリュームをまたぐ場合に(名前の変更だけで済まないからか)コピーになったりするけど、それだけ。Shift キーを押すか後で削除するだけの手間。

アイコンや文字のサイズなどデスクトップの設定がリセットされていたり、復元された Y ドライブ(まさしく自分の設定(レジストリ)が保存されている場所)が壊れているからチェックディスクを実行しろとファイルシステムからの鬼のような催促がイベントビューアに記録されていたりしたけど他は何も変わらず。もちろんレスポンスは速い。M.2 スロットなんてしゃれたものは 2011 年発売の MSI 990FXA-GD80 には付いていないし NVMe にも対応しないので転送速度は SATA3(実効転送速度 600MB/s)に律速される。500 MB/s 台が出ていたので大変満足です。HDD だとシーケンシャルでも 80 MB/s いけばいいところ。

SSD を知らない OS (Windows Vista) を SSD にインストールしてどうなるかはよくわからない。買った SSD のメーカーであるサムスンのユーティリティに期待していたのだけど、Samsung Magician 6 は Windows 7 以降でないとインストールできないらしい。Magician 4 はインストールできたけど当然ながら最近の自社製 SSD を認識しないので役に立たない。デフラグのスケジュールからは外したけど、他は何も。Trim はどうする？ TxBENCH のインストールはした。総容量の４分の１しか埋まっていないしデータディスクは別にあるからここから大きく増えることもない。空き容量に任せてどうとでもなるんじゃないかな(なったらいいな)。