脳log[2021-01-22～]

最終更新: 2021-03-02T17:55+0900

♪ [AtCoder] 緑diff精進４問

AtCoder Regular Contest 100／C 問題 Linear Approximation

提出 #19496296 (AC / 124 Byte / 173 ms / 36900 KB)

ソートすることに気付けたらあとは基準線をどう上下させるかだけ。

最初は平均をとって考えていたが中央値だった。ひとつだけへっこんだ極端な要素に下駄をはかせようとして、他のすべてがそろってでっぱったら意味がない。+1 するか -1 するか、改善する要素が多い方を選び続ける、その均衡点。

AtCoder Beginner Contest 115／D 問題 Christmas

提出 #19497044 (AC / 480 Byte / 63 ms / 14280 KB)

2020年12月にあった PAST の J 問題 長い長い文字列を思い出した。提出 #19035422

ということはこの問題も、クラスも入れ子にしたインスタンスも(つまりは再帰関数が？)不要で解けるということなんだけど、それは解らないので答えはプログラムに聞いた。

天下一プログラマーコンテスト2012 予選C／B 問題 ロイヤルストレートフラッシュ

提出 #19497447 (AC / 169 Byte / 65 ms / 14320 KB)

これは簡単。最大でも50枚ちょっとしかないカードなんていかようにも処理できる。

Tenka1 Programmer Beginner Contest／C 問題 Align

提出 #19498159 (AC / 215 Byte / 182 ms / 16952 KB)

よくわからない。雰囲気で答えらしきものを求めた。

これを提出するときに１年以上前に D 問題 Crossing に挑戦していたことを知った。提出 #8100494。え？ さっぱりわからないんだけど。当時と同じように１時間ちょっと考えてどうにかなる気もしない。

最終更新: 2021-01-16T18:37+0900

♪ [AtCoder] 緑diff精進３問

Coprime はまた解けなかった。WA ではなくなったけど TLE が解消しない。

AtCoder Grand Contest 023／A 問題 Zero-Sum Ranges

提出 #19447872 (AC / 107 Byte / 176 ms / 43452 KB)

以前に一度挑戦して TLE になっている。今となってはどうやって TLE を出すのかわからない。

半年前(20200615)まで累積和という概念・単語を知らなかったから、それが理由だろうな。

AtCoder Beginner Contest 160／E 問題 Red and Green Apples

提出 #19448291 (AC / 114 Byte / 192 ms / 42816 KB)

リアルタイムで参加した ABC だけど D 問題で詰まったからこの問題は初見。こんなに簡単でいいのだろうか。X≦A、Y≦B という制約がまた親切で、面倒な場合分けを取り除いている。

提出 #19457324 (AC / 94 Byte / 242 ms / 41108 KB)

引数付きの max メソッドを使うチャンスだと気がついて再提出してみたら 25 % くらい遅くなった。用意された罠なの？

diverta 2019 Programming Contest 2／B 問題 Picking Up

提出 #19449145 (AC / 184 Byte / 65 ms / 14404 KB)

2019年と2020年に一度ずつ提出して同じように１つの RE と３つ４つの WA をもらっていた。RE は N=1 のケース。WA はたぶん軸に平行な傾きをうまく扱えなかったんだろう。今回は読めていた。

最終更新: 2021-05-04T21:04+0900

♪ [AtCoder] 緑diff精進５問(+α)

AtCoder Problems がお勧めする Moderate な問題(緑difficulty)を上から順に解いた。半年前に解けなかった問題も１年前に解けなかった問題も解けた。だから０完だったこの前の ARC 111 は忘れよう。

AtCoder Beginner Contest 178／E 問題 Dist Max

提出 #19414840 (AC / 137 Byte / 319 ms / 28476 KB)

わかるようなわからないような感じが今でもするんだけど、y=x に沿って対極にある２点と、y=-x に沿って対極にある２点を抽出して比較すればいいらしい。コンテスト後に解いた人の感想が目に入っていたのでチートといえばチート。

AtCoder Beginner Contest 152／D 問題 Handstand 2

提出 #19421375 (AC / 312 Byte / 63 ms/ 14260 KB)

面倒くさく計算で解いたんだけど、N 個の数を列挙して先頭の桁の数字と末尾の桁の数字でクラス分けして数えて掛け合わせるので解けたらしい。たぶんそちらの方が間違えない。

AtCoder Beginner Contest 114／C 問題 755

提出 #19420198 (AC / 210 Byte / 81 ms / 17972 KB)

さっきのと似た問題。これは計算と列挙のハイブリッドで解いたんだけど、そうすると速くもなくシンプルでもなくどっちつかずになった。

そうすると？ これを見よ>提出 #15048046 (jajapop さん)。シンプルに列挙して速い。

AtCoder Regular Contest 006／C 問題 積み重ね

提出 #19420356 (AC / 95 Byte / 69 ms / 14280 KB)

謎の段ボール。重さと丈夫さが１つの数字で同時に表されている。１の上に２は乗せられないけれど、１と１と１を３つ乗せることはできる。謎の段ボール。

あ、大きさだと考えればいいのかも。小が大を支える不安定な重ね方が NG だと。でも重さって問題文に書いてあるなあ。←どうでもいいから解け。

最適な置き場所は１つなので貪欲法で。

AtCoder Beginner Contest 039／D 問題 画像処理高橋君

提出 #19421120 (AC / 242 Byte / 86 ms / 29364 KB)

最近の ABC-D はこういう素直に実装するだけの問題ってなくない？ 数学でいじめられたり制約でいじめられたりばっかりじゃない？ この問題が今の ABC で出たら difficulty が緑ってことはまずなくて、灰茶がいいところだと思う。世知辛いなあ。

 アナクロニズム

過去問はテストケースが利用できる。DropBox からダウンロードするとコンテストの各問題ごとに in フォルダと out フォルダが解凍される。

ARC111_A フォルダの中がこうなっているとする。

• in/
• out/
• my_answer.rb

そこで次のように実行する。(ARC111_A> はプロンプト)

ARC111_A> attc my_answer.rb

attc.bat の中身がこう。

@echo off
for %%F in ("in\*") do (
	call :run "%~1" "%%~F"
)
exit /b 0

:run
	echo %~1 ^< in\%~nx2
	call ruby27 "%~1" < "in\%~nx2" > "out\%~n1.out.txt"
	fc /A "out\%~n1.out.txt" "out\%~nx2"
	del "out\%~n1.out.txt"
	echo.
exit /b 0

カレントディレクトリの in フォルダの中身を入力として引数のスクリプトを ruby27 コマンドで実行する。出力を out フォルダの同名のファイルと fc コマンドで比較する。

call ruby27 という風に call が付いてるのは ruby27 が exe の名前ではなくて、C:\Program Files\Ruby27\bin に PATH を通してから ruby.exe を呼び出すバッチファイルの名前だという固有の事情から。

別に call でなくて当たり障りのないコマンドならたぶん何でもいいんだけど、call|ruby27 という風にパイプを通すと新しいコマンドインタープリタが起動するので、呼び出したバッチが setlocal してなかったとしても現在の環境(PATH 変数とかカレントディレクトリとか)が汚染されなくなるというハックがある。cmd /C "ruby27 ..." と同じことなんだろうけど、そっちは引数が引数になって二重の引用符が面倒の種だよね。

tc は Test Case の略だけど、 AtCoder の略が at か ac かで定まらないから、attc と actc の両方の名前でバッチを用意してる。ハードリンクにしたら中身の同期に手間もかからないし。

アナクロだけどそれなりに便利。

最終更新: 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 をどうにかするのか、よくわからない。