/ 最近 .rdf 追記 設定 本棚

脳log[2021-09-15~]



2021年09月15日 (水) [AtCoder] 精進。ARC073-D「Simple Knapsack」(水 diff)。タイトルに騙されて制約も見ずに DP 用の配列を大きさ W で確保しようとしたら、サイズ1ギガの配列は大きすぎると Ruby に怒られた。Simple とは……。難しく考えて再帰関数で 64 ms の提出(#25855795)を作ったのだけど、これって DP からの退行では? Ruby のバージョン違いによるオーバーヘッドの差があるからそのままの数字を比較できないけど、連想配列で普通に DP をしても 30 ms で済んでいる>#11970957。そしてこちらのこの方は自分と同じく DFS を採用してらっしゃる>#25853638 (今日の提出)。AtCoder Problems で Ruby による最近の提出一覧を見て今日の一問を選んだのです。中身までは見てなかったので似てるのは問題から導かれる必然であり偶然の結果です。違うところは、ある重さのアイテムの採用数を一定レベルより下げても、他の重さのアイテムの採用数が上限に達して増やせなくなるポイントがあるので、その均衡点を見極めてループを打ち切っているところ。それが難しく考え過ぎだっていうんだけど、想定解が 400^3 のループで Ruby 勢を虐殺した ABC-D の恨みが記憶に新しいせいなんだよなあ。


2021年09月14日 (火) [AtCoder] 精進。ABC022-D「Big Bang」(青 diff)。2つの点集合を平行移動して回転させて縮尺の比を求める問題。最近あった座標問題2題「Congruence Points」「ほくろ」とは違って、個々の点の座標を一致させる必要はない。座標変換の具体的なパラメータを探索することが許されている制約でもない(2≦N≦10^5)。直径だけわかれば十分。しかし、どうやって? テキトーに並べてテキトーにいくつか距離を計って最大値を選んだら通りましたよ>提出 #25850608提出一覧から1つ2つ他の人のを覗いたら、重心からの距離の最大値を使っているみたいだった。重心は Congruence Points でもキーになっていたのに、また気が付かなかった。これはいけない。頭の悪さを晒しているぜ。役に立たないときに限って重心を持ち出している>20210406p01。■ところで今気が付いたけど、この回の ABC って 100 分でなく 120 分だ。途中までそうだったんだろうか。今は4問が6問になって、さらに難しい2問が追加されて、全8問で 100 分だよ。


2021年09月12日 (日) [AtCoder] 精進。ちょっと前の ABC215-E「Chain Contestant」(水 diff)。当日にこう書いている>「今日の感じだと E 問題 F 問題が解ける世界線はそう遠くないと思えるんだけど、つまりは、解けなかったってことなんだな。E 問題で TLE 解が作れただけ」。実際、日を改めれば解けるんだよ>提出 #25816607。それに、166 ms でだいぶイケてると思う>Ruby によるすべての提出。これを本番でだね……。■調子に乗って考え方を書いておこう。現在の状態をどうクラス分けできるか。これまでに出たコンテストの集合と最後に出たコンテストの種類のペアで分けられる。それだけが区別できれば十分。それが D = Array.new(11){[0]*(1<<10)} の部分。幅 10 のビットフラグが 10+1 個分。コンテストの種類は 10 なんだけど、余分な +1 を 10 個の合計の記録用に確保した(Ds = D[-1])。というのは、最後に出たコンテストの区別は現在のコンテストと同じか異なるかという二値で十分なのに、異なるものが9個に分かれてると集計が面倒だから。あとはコンテストの回を追って、参加した場合参加しなかった場合を数えていくだけ。■これは自分が DP を知らなかった昔に DP と知らずに書いたのと同じ形>20120214p01.02。Project Euler の 191 問目だった。


2021年09月11日 (土) [AtCoder] 今日は ABC218 の日だった。本番で青 diff 通したいねえ。F 問題「Blocked Roads」がそう。N の3乗が通らないだろうとは制約から読み取っていたけど、普通に BFS を繰り返すだけで通ったのが拍子抜け>提出 #25793701。なんだよー(まじめに書くと、繰り返しの上限が辺の数 M(≦N*(N-1)/2) ではなく最短経路の辺の数(≦N-1)だということが見抜ければ意外ではない)。だからと言って惜しかったとは感じないし悔しくもないけど。■ RE と WA を繰り返した最初の方針でも AC まで行けた>提出 #25812833。ちょっとした沼にはまっていたんだな。E 問題を通してから終了までのおよそ1時間のあいだ。


2021年09月10日 (金) 朝日新聞デジタル「300億年で1秒しかずれない極めて正確な光格子時計を開発した。従来の原子時計をはるかに超え、1秒の定義に採用される可能性もある。重力が大きいほど時間の進み方が遅くなるという相対性理論の効果を利用して、十数メートルの高低差まで検出できる。」 すごい! スケールが不明で何がすごいのか全然わからない!(十数メートルの高低差が認識できない人類おる?)■それはそれとして、ちょっと前に『精密への果てなき道 シリンダーからナノメートルEUVチップへ』という本を読んで、世界を計る解像度の向上は文明の発展度合いを示すわかりやすい尺度になるなあと思ったのだった。まる。知識と発展の源泉であるよ。


2021年09月09日 (木) [AtCoder] 精進。ABC036-D「塗り絵」。すごく難しかった>提出 #25696587。解答の形も式もほとんど 20210624 で解いた競プロ典型90問の「073 - We Need Both a and b(★5)」と同じ。というかあちらがこちらと同じ。だけどやっぱり難しかった。解説なしで解けたのだけが進歩か。これが昔の ABC の D 問題でギリギリ青色だってんだから、解かれすぎでは? 自分が苦手にしてるだけか。典型の方も★5つで中程度の評価だもんな。


2021年09月08日 (水) [AtCoder] 精進。この前の ABC217-F「Make Pair」。マイメロ(?)が「これ、ほぼ先週のFと同じってマイメロのママが言ってたよ https://t.co/31te6MkVI2」といって競プロ典型90問の「019 - Pick Two(★6)」をポイントしていたので、自分の提出(#22879312)を参考にして取り組んだ。2 WA、3 TLE のち AC>#25683515。おかしい、一度解いた問題が身になっていない。そんで、再帰関数で制限時間ぎりぎりだけど、DP 化するとだいぶ速いみたい。できませんけども。


2021年09月07日 (火) マジックナンバー使うな? どんどん使え! - Qiita」■これって逆張りに行っているようでやってることの実質はマジックナンバーの定数化と同じだよね。x*0.10mx*税率 にするのも 消費税額(x) にするのも、名前を付けているという点で同じ。名付ける対象がデータか手続きかという違いはあるし、それを定数で定義するか関数で定義するかという違いもあるけど、static メソッドでアクセスするシングルトンオブジェクトがグローバル変数と同じなのと同じ程度には同じ。■2つあるブコメにもそれぞれ一理はあって、「変更があるものは定数化した方がいい気がします.....」は、それはそう。ただし設定項目の一部であったりしてプログラムとは別のサイクルで変化する場合や、変更が複数箇所に及ぶ場合に当てはまる話であって、同じソースコード上にある現状であれば、定数定義を1か所変更することになるか関数定義を1か所変更することになるかという違いは、どうでもよくない? 「例がよくない。例示している消費税率はソースの至る所に存在するようになり、定数化しておくと法律が変わり修正が必要なときに修正漏れを抑えることができる。1度しか使わない値を定数化など何でもするはよくない。」というのも、それはそう。当たり前のことをこの記事に対してコメントするのはなぜか。たぶん記事の中の 消費税額 関数を否定はしていなくて、だけど 0.10m というマジックナンバーを利用する場所が絶対に 消費税額 関数1つにとどまらないだろうことを見越して「例が良くない」と言っているのだと思う。


2021年09月06日 (月) アルノサージュ(PS3)クリアした。アルトネリコ1もそうだったけど、けっこう特異なヒロインを造形するよね(見た目じゃなくて)。好き。


2021年09月04日 (土) 「東工大で接種してたら予診票のこの部分をみて「え?この部分は医師の診察説明を受けてからではないんですか??」みたいなこと言って揉めてる人いて東工大生だなぁとなった。 https://t.co/9wonz8qSgr」 / Twitter」■文面はこうなんだけど「医師の診察・説明を受け、接種の効果や副反応などについて理解した上で、接種を希望しますか。」 もうひとつの解釈もあるなと思った。つまり、東工大生の解釈は「(医師の診察・説明を受け、理解しました。) 接種を希望します。」なんだけど、(たぶん想定されない)別解釈は、「(医師の診察・説明を受け、理解した場合には) 接種を希望します。」 だからまあ、先んじて希望することを表明しておいて、医師が診察・説明を正しく履行することを確かめるつもりでいれば、揉めないでもいいんじゃないかなと。方便だけど。■自分は名簿とボールペンを前にした状況で、「おなまえよろしいですか」と言われた瞬間に (え? 名前が、宜しい? それってどういう。何が Yes で何が No ?) と不可解な言葉の解釈に囚われてフリーズした(東工大生ではない)人間だけど、昔の話。


2021年09月03日 (金) お金のやりとりだけセルフ式のレジにて。財布から小銭を取り出してバーコード読み取り完了を待機しているあいだにふと気になって聞いてみた。「今の段階で先に小銭を投入すると問題がありますか?」 答えは、「支払い方法で現金を選ぶまでは中に仕切りがあってお金が飲み込まれないので問題ない」 予想外にサバけた答えだった。もちろんこういうレジの常として、前の客がぐずぐずしているときに割り振る2番目の精算機があるので、小銭を投入しておいた方に間違いなく割り振ってもらわなければいけないだろう。だけどそんな意地悪はしないよね? 財布の小銭を全部投入してからお札を持って待機していた。■レスじゃないって? iD が名前をかぶせて利用を妨害してくる前から楽天Edy に名前が変わるまでのあいだは W53S で Edy を使っていたし、今でこそこのスーパーも Edy その他に対応してるけど、時流が俺から離れていったんだな。


2021年09月02日 (木) [AtCoder] 精進。ARC056-B「駐車場」。20210814で解いた2問に連なる、アレだと気が付くのが難しい、気が付けば実装が終わっているシリーズの1つ。考察が2段構えだったのでこれが一番難しかったかな。ある状況とある状況が独立に生じるのではなく依存関係にあって、それによって起こりえない状況が生じるのだけど、そのありえない状況に惑わされないために考えを巡らせる必要があった。それというのは、「3つの駐車スペース i < j < k があって、i に車が止まっていると j に車を止めることができず、j に車が止まっていると k に車が止められないとする。今、i に車が止まっているために j が空いているなら、k に車を止めることが可能かどうか」という状況。それに答えが出たから書けた>提出 #25521687。賢い人は「え、そこ悩むところ?」って言うのかな。


2021年08月31日 (火) [AtCoder] 精進。ARC051-C「掛け算」 昔の青 diff。制約が最大ケースで1ギガの数を1ギガ回掛けるとかなので、手続き的な解法は望めない。扱う数の種類 N は 50 以下とごく限られている。どうするか。たとえばすべての数が A より小さい場合や、どの2数の差も A より小さい場合は、ソートして前から均等に × A を割り振ればいい。一般化すると、すべての数を A^b の形で表して、b 乗の部分が平らになるように B 個の × A を分配する。一発 AC!>提出 #25492066。だが時間をかけた。これが虚無埋めならわざわざ日記に「解けたぞ わーい」って書いてないからね。