脳log[2020-12-31～]

最終更新: 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 問題はひとつの提出も用意できないまま放置している。

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

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