脳log[2021-01-03～]

最終更新: 2021-01-03T19:49+0900

♪ [AtCoder] AtCoder Beginner Contest 187／E 問題 Through Path

PAST 第４回の M 問題 筆塗りを思い出したよね>20201111p01.01。

制約が 10^5 の組み合わせだというところが同じ。だから何について繰り返すかというところが核心。繰り返しの繰り返しは許されない。N-1 本の辺を順序よく１往復か２往復すれば答えが出そうな気がするんだけど、全然ループの軸が見えなかった。まだ見えていない。テキトーにキューに突っ込んで処理できる順に処理しても間に合うかと考えてみたけど、メモするデータが定まらなくて完成しない。こういうところだよ。こういうところが緑色で燻っている理由だよ。

最終更新: 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 になった。

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