2021年01月23日 (土) [AtCoder] NoSub に関して @evima0 さんのこのツイートがえらいと思う。「現在の AtCoder ではコンテストで一度も提出しなかったら (できなかったら) 不参加扱いですが、問題を読み始めた瞬間に参加扱いにすることを検討しているようです。」■ NoSub 即不正みたいな論調ばかりで想像力の足りない連中に言いたい。NoSub したくてする奴なんざいねーんだよ。いつだって誰だって全完できるなら全完したいしそうするに決まってんだよ。A 問題のサンプルを通す解答すら用意できなかったから NoSub になるんだよ。もちろん戦術的 NoSub の選択肢は知っている。でもそれが？■パフォーマンスの良かった回だけピックアップすることでレイティングが上振れするとしても、その範囲は精々色半分程度ではないか。自分の場合、緑が水色にはなるかもしれない。でも青パフォ黄パフォなんて見たこともないから、粉飾しても青黄の目はない。■にもかかわらず NoSub を含む戦術を駆使してレイティングを良く見せようとする人間は、自分がその程度伸びる未来も描けない終わった人間だと俺は思う。何を気にかける必要がある？ そんな他人の足なんざどうでも良かろう。
最終更新: 2021-05-07T14:34+0900
♪ [AtCoder] AtCoder Beginner Contest 189／C,E
今日の ABC。
C 問題 Mandarin Orange
制約がよく見かける 10^5 ではなくて 10^4 だから雑なやり方でも通る気がしたんだけど、そんな仏心が期待できるはずがなくて、時間が厳しいからこそ制約が緩めてあるのだなあ。Ruby では D 問題よりも解かれてないみたい。
提出 #19612283 (AC / 190 Byte / 88 ms / 15720 KB)
AtCoder のことを初めて日記に書いた記念すべき日「脳log[20190907p01] AtCoder Beginner Contest 140 E問題」を思い出して書いた。
不安だからそのままにしたけど、今回は更新と更新のあいだに参照が１回だけだから、番兵も１つで足りたと思う(これに対する答え>「実のところ
」)。+ [N, N] と + [-1, -1] は完全なるコピペ。+ [N] と + [-1] ではダメだったものがどうしてこれで正しい答えにつながるのか、さっぱり理解していない。RU[N] と LU[-1] に番兵を１個置くのと２個置くのの違いとは。
提出 #19649425 (AC / 167 Byte / 68 ms / 15644 KB)
ソートで配列を比較するのが贅沢で余分な時間を使ってるみたいだったのを修正した。88 ms → 68 ms
多重代入部分を読み解く参考に>20201124p01, 20200428p01.08.01
主流の解き方ではデータを蓄えたり捨てたりしながら数列を前から一度だけスキャンするみたい。何を蓄えて何を捨てるんだろう。わからない。ピークの情報は残しておいてもしかたないな。現在の要素をピークとして左側への広がりが知りたいかな。上昇トレンドでは広がりに意味がないな。
提出 #19675442 (AC / 201 Byte / 69 ms / 15096 KB)
2 WA のち AC。数列を１回通り抜けるだけ。上昇トレンドでインデックスを記録しておいて、下降局面で幅を確定する。
あ、これ８行目の if が常に true でバグってる。
提出 #19679788 (AC / 199 Byte / 66 ms / 14984 KB)
これが(バグ修正済みの)本当の O(N) 解答。バグといっても等しい要素が多いときに無駄がある、という程度だったみたいだけど。
C 問題でこれをイチから考えるのはあまりに酷だけど、実は O(N^2) が通る制約だったらしい。Ruby で 10 メガや 100 メガが秒未満は無理だと思うけど。
「ヒストグラム中の最大長方形の面積を求める」
ここで紹介されている方法が O(N)。自分の(前２つ)はソートしてるから O(NlogN)。
提出 #19680172 (AC / 297 Byte / 69 ms / 15104 KB)
さっきリンクしたのと同じ日記だけど、「Rubyで一番速いのはこれ。345ms」として参照したのと同じ解法。愚直に検索する O(N^2) 解法の改善案として素直に理解しやすいと思う。
数列がソート済みであればあるほど改善効果がなくなるのではないかな。クイックソートみたい。
提出 #19700600 (corazon さん / AC)
#ここがよくわからない #●●●しない限り、次に来る高さと取り出した長方形の最後のインデックスをスタックの中に入れる
わからないのがよくわかる。自分が O(N) 解法を書くにあたって 2 WA した原因がここだから。
要するに、「取り出した長方形」は「次に来る高さ」よりも高い要素なわけだから、次に来る高さの上位互換であるわけ。その「最後の」(=最も左の)インデックスを、次に来る高さの左方への広がりとして記録している。
E 問題 Rotate and Flip
提出 #19644038 (TLE×6 / AC×24)
アフィン変換を検索して見よう見まねで書いた。１時間かかった。TLE だった。これ以上はもう余力も時間もなかった。無念。
対称移動のための行列は３つの積ではなく２つの積で表現できるし、それも自分で計算して１つにできる。でもそれだけでは TLE のままだろうな。行列の掛け算をただの配列同士の掛け合わせとして自分で書いてみたりもしたけど、７秒が６秒になるだけだった。
競技プログラミングをするフレンズ @kyopro_friends Jan 23
アライグマ「E問題は、(0,0),(1,0),(0,1)の3点だけシミュレーションすれば全部計算できるのだ！」
な、なんだってー。
汎用的に点を動かそうとするのでなく、具体的に基底を動かすってことなんかな。だけどそのシミュレーションをするのに行列を使ったら元も子もないので、どうするの？ 頭が働かないから行列におまかせしていたんだけど、どうしたらいいの？
軸に平行な直線で折り返すのはまあできる。90度回転は x と y を入れ替えたり符号を入れ替えたりで、たぶんできる？ 個々の点の座標を求めるのは……？
まあ、TLE 提出を見れば行列って形で式が見えてるんだから、計算できないはずがないんだよなあ。
提出 #19690206 (AC / 619 Byte / 1497 ms / 103080 KB)
いやー、厳しい。ヒントがあってもいくつも穴にはまって時間がかかる。「まあできる」とか言っていた折り返しも実はできなかった。
ここでやったことと蟻本に書かれていた(けど解らない)「実は、m 項間漸化式の n 項目は行列を用いるのではなく、各項を初項の線形結合で表して繰り返し二乗法を行うことにより、O(m^2log(n)) で計算することも可能です。興味のある人は考えてみるとよいでしょう」に関連はありますか？
@2021-02-06
移動後の点の X 座標ないし Y 座標を求めるのに、a+x*(b-a)+y*(c-a) の式を使うと遅い。どうせ同じ数の係数を蓄えておくなら、a+b*x+c*y で答えが求まるような係数を用意したい。
- 提出 #19625610 (hmmnrst さん / 881 ms) 速い。提出時刻も早い！
- 提出 #19947952 (ds14050 / 950 ms) 遅い
でも何を考えて係数を変換していけばいいのかわからない。
- 提出 #19948980 (ds14050 / 858 ms) 答えは合った
a,b, c,d, e,f の初期値を 0,0, 1,0, 0,1 として、操作１～４でどのようにマッピングしていくか。
| 遅い方 | 速い方 | 備考 | |
|---|---|---|---|
| 操作１ | b,-a, d,-c, f,-e | b,-a, d,-c, f,-e | 同じ |
| 操作２ | -b,a, -d,c, -f,e | -b,a, -d,c, -f,e | 同じ |
| 操作３ | p2-a,b, p2-c,d, p2-e,f | p2-a,b, -c,d, -e,f | 一部 p2 の省略 |
| 操作４ | a,p2-b, c,p2-d, e,p2-f | a,p2-b, c,-d, e,-f | 一部 p2 の省略 |
| 移動後の座標 | (a+(c-a)*x+(e-a)*y, b+(d-b)*x+(f-b)*y) | (a+c*x+e*y, b+d*x+f*y) | 引き算が不要 |
遅い方は各操作で余計なことをしていて、移動後の座標を求めるときにも余分なことをさせられている。そりゃあ遅くなるはずだけど、何を念頭に置けば速い方の式が書けるのかわからない。
遅い方を書くときは、基底となる２つのベクトルを定める３点を移動していくつもりで書いていた。
速い方でも (a,b) の意味はただの点なのでわかる。でも (c,d) と (e,f) に何のイメージを割り当てればいいのかわからない。それこそ向きと大きさだけで位置を定めない、ベクトルそのもの？ そうかもね。そうなんですか？
2021年01月22日 (金) 「オブジェクト指向には、カメラがやっとついたころのガラケーのイメージがある - きしだのHatena」からの「現代のオブジェクト指向の class の割れ窓化と宣言的プログラミング」■副作用の分離(と集中)だと読んだ。ちょっと前に書いたこれも同じ視点でとらえ直せると思う。「「もし～ならこうする、さもなければこうする」という型のコードは２つの「こうする」に無制限に無関係な処理が書けるし、何もしないこともできるし、目的に対して自由度が高すぎる。もっと制限の強い型にはめれば読み手にいらぬ想定を強いることがない。コアとなるコードは「何かを出力する」となるべきであり、その何かを作るのに if 文を書いたり、if 文を含んだ関数を一度だけ呼び出したり、事前に用意しておいたデータファイルを読み込んだりするのが良い」 あっちで出力し、こっちで出力し、とコードの分岐のあちこちに副作用をばらまくのはやめましょうと。全然書けないけど Haskell あたりをたしなむとモナドなんて概念があって、自然と副作用をコントロールするスタイルが身につくのではないかという気がしている。全然、一行も書けないけど。
2021年01月21日 (木)
[Ruby] 箱入り娘というパズルがあるそうな。最短81手の初期配置を解く>箱入り娘.rb。何をもって一手と判断されるかはここを参考にした>「箱入り娘／解答」。パッとは書けなくて、じっくり時間をかけた。Ruby 1.8 対応はできなかったけど 1.9 と 2.5 と 2.7 は OK。ここでは最少 138 手の配置が紹介されている>「箱入り娘パズルの攻略法」 それもスクリプトに足しておいた。たしかに 138 手だった。■■■同じく Ruby で解いていた人がいる。「箱入り娘パズルをRubyで解く - yarbの日記」 22分かかるって書いてあるんだけど、s.visited という行を s2.visited に書き換えて８行か９行下に持って行くと、30秒もかからずに終了しましたよ(そして9305手の履歴を表示した)。そもそも Ruby 2.7 では元のままでも５分かからずに(書いてある通りに) SystemStackError が出たのであるが。■■■@2023-10-02 バグみっけ。箱入り娘.rb の 30 行目。Array#uniq にブロックを渡して処理を行っているが、このブロックは uniq メソッドの一部として働くのであって、uniq した結果が渡されてくるわけではないんだよね。Array#split にブロックを渡す用法があるのを知って以来、隙あらば each を省こうと狙っているのだけど、Array#zip と Array#product は良くても uniq メソッドは間違い。処理が重複して無駄になっていた。
2021年01月17日 (日) いつの間にかセンター試験が終わっていた。なくなったという意味で終わっていた。時代は共通一次……ではなく共通テストらしい。
最終更新: 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月15日 (金)
最終更新: 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年01月13日 (水)
最終更新: 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月12日 (火) ブックオフオンラインの[カートに入れる]ボタンはタイミングや履歴に依存した処理をしている。どういうことか。本のページを開いて[カートに入れる]ボタンを押した。ブックオフオンラインは恒常的にサーバーレスポンスが激遅だから、待たずに他の本のページを開いて[カートに入れる]ボタンを押した。何が起こったか。最後に[カートに入れる]ボタンを押した本がカートに複数入って、代わりに一部の本がカートに入らなかった。レスポンスがコンマ数秒の Web サイトならタイミング依存も発覚しないかもしれませんけどね、あなたのサイト10秒でも20秒でも待たせるじゃない……。
2021年01月10日 (日)
「感情を説明することが難しいという話に対する詳しい説明」■Togetter のまとめより増田の方がわかりやすかった。思うに何が欠けているかと言えば、相手への働きかけではないか。自分の感情を見つめても答えは出ないのではないか。ブコメから抽出したというこれが典型的。「ご飯を作ってあげたときに「美味しいよ」とか「ありがとう」の前に「鶏肉をもも肉からむね肉にしたんだね、さっぱりとした味になっているね」とか言われたらそりゃモヤモヤするよ
」 相手に感謝を伝える、それは喜ばせようという働きかけであり、愛情があればその意思を持つのが当たり前である、ということを学習すればいいように思う。意図をもって働きかける意思が持てればいいと思う(操作か支配かと忌避感があるけどね)。変化を恐れず、相互作用を起こし、相手の反応を楽しむべく努力しよう。相手の喜びこそ自分の喜びとしよう。■私はそれができない。■「ふたりで、ひとつに、なれちゃうことを、きもちいいとおもううちに、すこしの、ずれも、ゆるせない、せこいにんげんになってたよ
」 善し悪しだけど良さをまだ知らぬ。
2021年01月08日 (金) 「東北大等の研究グループ、父親が高齢だと子が発達障害になりやすいとするマウス実験結果を発表 | スラド サイエンス」■このときの>20191224。結局、DNA 配列の変異を伴わない、メチル化、エピジェネティクスを中心に置いて読み解けば良かったのだということが理解できる発表内容。いやあ、それは難しいでしょう。全然著者が中心に据えている考えに導かれていかなかったよ。最初から前提となる考えを共有しているのでなければ理解できなかったよ。
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月31日 (木)
「KyashからRevolutへ移行中 - ただのにっき(2020-12-24)」■全然内容と関係ないことを書くんだけど、全然ってこともないかもしれないけど、自分は Kyash をずっと(黙読で)カイアッシュと読んでいるし、Revolut はレヴォルットと読んだ。レヴォルートも、e が欲しいところだがギリギリ、ありか。公式がどう読ませたいかは関係なく、読めるように、読みたいようにしか読まない。読めない名前、声に出せない名前ってそれだけで不利。識別子として役に立っていない。ましてそれがキャッシュではね。■ Costco が全然コストコじゃないってつい最近知ったんだけど、そのスペルと日本語話者の発音能力を考えるとコストコしかないって思う。どうせそのように読まれるし、そのようにしか発音できないし、それを、間違いですよと公式に言われてしまっては、もう指示語でしか語れない。あの……、あれ、コスなんとかっていう……。ヴォルデモート なの？ だからコストコはコストコでいい。
2020年12月25日 (金)
最終更新: 2020-12-26T00:15+0900
♪ [WR250R] ヘルメットホルダーが壊れたけどなんとかなったっぽい。
６年目に入った WR250R。ヘルメットホルダーがカチッと閉じなくなってただのフックと同じになった。
世の中には鍵付きのメットホルダーすら信用しない人がいるらしいが、自分はそこまでではない。だけど本屋なんかに行ったときにヘルメットを無造作にミラーに引っ掛けて、ということもできないので、その他の機会と合わせて月に数回から10回くらいの頻度で使用していると思う。酷使しているつもりはないが壊れた。壊れたメットホルダーを検索すると割と上位にこういうものが見つかった>「WR-Rのヘルメットホルダーが壊れた・・・ – Levico's BLOG」 お仲間。
メインキーと共用だというところに価値の半分があるので、新品交換で価値が半減しないかが心配。
T30 のトルクス１本で車体から外れる。バックプレートはプラスネジ２本。２本は同じだと思ったが組み直すときに一方が途中までしか入らなかったので入れ替えてみたらすんなり締まった。罠なのか？
バックプレートを外した状態。フックがあるのと反対側、車体側から見ている。表から見た形はこれとほぼ同じ>「【楽天市場】【在庫あり】DAYTONA デイトナ ヘルメットホルダー CT125：ウェビック 楽天市場店」
鍵をひねった状態。中央の銀色のパーツが逆時計回りに30度くらい回転した。色の関係で見にくいが回転軸に巻き付いて伸びた茶色の板バネがケースの上面をこすりながら力を蓄えている。
板バネにこすられて傷ついたケース上面。バネが傷に引っ掛かって位置が固定されるために蓄えた力が解放されない。結果としてフックを差し込んでもラッチが掛からない。残念なことに鍵をひねって強制的に閉じることはできない。スロットルワイヤーが開く・閉じるの２本１組であることの大事さがわかりますね。
一時しのぎだけどバネを取り付ける向きを180度回転させてケース下面をこするようにした。これでもう５年は大丈夫……かな？