脳log
http://vvvvvv.sakura.ne.jp/ds14050/diary/
ds14050
Copyright 2024 ds14050 <ds14050@vvvvvv.sakura.ne.jp>, copyright of comments by respective authors
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20240329.html#p01
2024-03-29T01:13:29+09:00
パ研合宿2023 第1日「SpeedRun」
ds14050
AtCoder
AtCoder をプラットフォームとして利用する有志コンであり、AtCoder の問題ではないけども、競プロカテゴリとして AtCoder に分類しています。 リアルタイム参加はしていない。ABCDFHIE をこの順に解いたのでふりかえって書く。 A - Kazuate Game (100 点) 出現数を数える。Array#tally そのもの。 提出 #51702284 (AC / 67 Byte / 103 ms) B - Cutting Circle (100 点) 2本の線が一致することはないので、必ず3つか4つに分割される。ソートするなりしてうまく分類する。 提出 #51702526 (WA) うまくできませんでした。 提出 #51702670 (AC / 146 Byte / 51 ms) C - Infinity (200 点) 数列が a,1,b であるとする。そうすると、b=a+1、a=b+1、b=a+1 と操作を繰り返すことで無限に大きな要素を作ることができる。A[1]=1 の場合であっても、A[1] を無限大にすることができる。初期数列が1以上の要素を含んでい..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20231219.html#p01
2023-12-20T20:06:57+09:00
JOI 2023/2024 二次予選 過去問
ds14050
AtCoder
AtCoder の問題ではないが精進。ABCE の4問。 A 問題 カードゲーム 2 (Card Game 2) 基本的にはカードを順番にスキャンして判断をする。ハッシュ表を使って自分が一番小さいカードである場合、2番目、3番目の場合の3パターンについてカードが3枚揃っているかを確かめる。もしくは、昇順にソートして自分が一番大きいカードであるケースについてカードが揃っているかを確かめる。 提出 #48433809 (AC / 121 Byte / 125 ms) B 問題 買い物 2 (Shopping 2) N 個の商品がありそれぞれの商品は M 種類の商品カテゴリのどれかに属している。M 日間のセールがあり、セール期間のある一日にはあるひとつのカテゴリの商品が半額になる。Q 人の客がそれぞれある日に訪れ、ある範囲の連続する商品を購入する。さていくら? Q 個答えよ。 割引がなければ範囲の総和を知るのに累積和を引くだけ。しかしある日にはあるカテゴリの商品が半額になっているので、範囲内にそのカテゴリの商品がいくつあるか知りたい。カテゴリごとに位置を昇順に記録して二分探索をした。 カ..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20220129.html#p01
2023-07-22T18:09:32+09:00
JOIG 2021/2022 本選 過去問/F 問題 タクシー 2 (Taxis 2)
ds14050
AtCoder
ステップ1 タクシーが赤色の場合,乗車後の所持金が a−1 円になる. タクシーが青色の場合,乗車後の所持金が「a÷2 を整数に切り捨てた値」円になる. 町 1 から出発し,1 円以上の所持金を残した状態で町 Tj に到着するために,最初に少なくとも何円の所持金を持っている必要があるか 問題のこの部分は、まあ、逆に考えます。所持金が1の状態でスタートして、所持金が +1 になる、×2 になる、というように。そうすれば初期金額を探索しなくて良い。ただしそれぞれの町をスタート地点に設定して町1への最短経路を繰り返し求めるということは許されていないので、スタート地点は町1のままにしておきたい。 ところが町1を1円でスタートして、+1/×2 しながら各町に着いたときいくらになっているかをダイクストラ法で求めてもサンプルが合わない。合わなかった。 たぶん、-1/÷2 の逆計算は +1/×2 でいいのだけど、((((-1)-1)÷2)-1)÷2 の逆計算は ((((×2)+1)×2)+1)+1 ではないとか、合ってるけどその通りに計算できていないとか、そういう理由。 わからんなりにテ..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20230529.html#p01
2023-05-29T23:00:26+09:00
事故の顛末
ds14050
WR250R
先月 28 日 横断歩道わきに人を見つけて止まったら後ろを走っていた車に追突されたよ。 けが 車は軽自動車で、双方ゆっくりペースで走っていたみたいなので、わけがわからんまま地面を転がったけど骨折などはなし。さすがに無傷ではなく肩と腰にぶつけたような筋肉痛のような痛みがあったのと、右のすねに4点の血の穴があった。位置と配列からステップのギザギザ(※オフ車のステップにはラバーがない)にガツンとぶつけたのかなという感じ。普通に歩けはする。 肩は最も簡素なものではあってもプロテクターが初めて役に立った結果といえる。ニーシンガードは……足首付近までカバーしてるわけではないから仕方ないね。 バイク 押し倒されて後輪に乗り上げられて冷却液をドボドボとかけ流しにされていた。 ナンバープレートやナンバーステーがぐんにょりひしゃげてるのが一番のダメージ。スイングアームの表面やアクスルナットも削られてギザギザしてた。 場所 目の前が消防署であって、隊員の人が一番にかけつけてくれて怪我の確認やら事故車の退避やら道路上の液体に砂を撒いて掃き清めるや..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20230301.html#p01
2023-03-02T03:41:27+09:00
第12回 アルゴリズム実技検定 過去問
ds14050
AtCoder
自分のすべての提出 A - 信号機 赤になってから Z 秒時点でボタンを押したら X 秒後に青に変わるけど、最低 Y 秒間は赤の時間が確保されているように。[Z+X,Y].min B - クレジット 正整数 を 100 で整数除算する。桁数が 50 万と 1 になることがあるのでうっかり gets.to_i してはいけない。いや、案外平気かも。文字列として2桁削ればいいけど N が2桁以下のときに 0 を出力するのを忘れない。 C - 偏ったサイコロ 出目の和ごとに場合の数を記録する DP。6×6×6×18 程度の計算量。 D - 採点 辺の集合が与えられたときに多重辺と自己ループの有無を調べる。 強いて注意点を挙げるなら、多重辺を調べるときに文字列のまま比較すると 1 2 と 2 1 の同一性を見逃してしまうことと、隣接頂点リストを配列として持つと星型のグラフで多重辺のチェックが O(N) になってしまって全体が O(N^2) で TLE になってしまうこと。Ruby なら Hash で隣接頂点を管理する。 E - 棒倒しゲーム 問題文に書かれている通りにスコアを消費していって、..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20230207.html#p01
2023-02-08T02:07:56+09:00
Ruby クイズ (複合代入編)
ds14050
Ruby
a = b = 0 # 初期化 a += b += a += 1 # 本題 p a #= 1? 2? 右から順番に a に 1 を足して(a=1)、b に a を足して(b=1)、a に b を..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20220202.html#p01
2022-02-10T03:41:03+09:00
Ruby が謎に止まる。(解決済み)
ds14050
Ruby
先日解いていた「JOIG 2021/2022 本選競技課題」(テストケースのダウンロードができる) の F 問題へのこの提出に関して20220129p01.05。 Hash#shift を可能な限り繰り返したあとで Hash#clear を呼ぶようにしている。shift は破壊的なメソッドだから shift を十分に呼び出した後の Hash は空になっているはずで、clear を呼ぶ意味はなさそうに思える。それでも呼ぶようにしているのは、これがないとテストケースの in/05-01.txt に限ってスクリプトの応答がなくなって TLE になると思ったから。少なくともローカル Windows 環境では Ruby-2.7 と Ruby-2.5 で止まる。Ruby-1.9 は平気。他のテストケースでは止まらないけど、問題のケースでは必ず止まる。止まるタイミングはバラバラだけど、いずれも Hash への代入で止まっているようだった。 再現スクリプトはこんな感じ(これを見つけたから日記に書いている)。他所で再現するかは、どうでしょうね。 Many = 100 # 10 回では少ない。テキトー..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20211210.html#p01
2021-12-11T17:59:17+09:00
JOIG 2021 過去問/F 問題 デジタルアート (Digital Art)
ds14050
AtCoder
D と E についてはここに書いた20211206。A,B,C については ABC-C までの難易度帯という感じで特に何ということもなく解けたので書いていない。最後に F 問題が残っていた。 考え方 色ごとにその色を完全に覆い隠せる矩形を考える。矩形は左上座標と右下座標で特徴付けられる。面積 S を超えない範囲でどのような矩形を選べばできるだけ多くの色を隠せるだろうか。 制約 グリッドの一辺は最大 1000 なので、グリッド上の点は最大 100 万個。いくら面積 S を超えない範囲でできるだけ大きな矩形のみを考えるとしても、グリッドから2点を選ぶ組み合わせは1メガ×1メガに近い数になる。これは制限時間1秒で扱える数ではない。 色数の上限が 256 に抑えられている。256 の3乗は約 1600 万だから、Ruby の場合、定数倍が 1/2 とかなら3乗がなんとかなるかな、という雰囲気。 どうやる? 二次元累積和であるとか「Range Set Query」が思い浮かんだけど、どうにも(知っている)定型の処理に当てはまらない。 矩形の左上座標と右下座標を探索することが許されるなら、色を..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20211107.html#p01
2021-11-08T09:31:26+09:00
AtCoder Beginner Contest 226/E 問題 Just one
ds14050
AtCoder
解けなかった。 提出 #27107258 (WA×9 / AC×24) これはコンテスト中の提出。WA と AC の比率からして惜しいのかなという感じ。おそらく 0 を返すべきケースで 0 が返せていない。それはどういうケースか。連結成分が8の字になっていたりして輪っかが1つではないケース。 しかしそれをどうやって検出するのか解らなかった。 提出 #27118298 (AC) これはコンテスト終了後の提出。さっきの..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20211023.html#p01
2021-10-24T01:36:12+09:00
AtCoder Beginner Contest 224/D,E
ds14050
AtCoder
D 問題で TLE に苦しんだ。E 問題も TLE に苦しんだ。そのまま E 問題が解けなかったので F 問題は読めなかった。 D 問題 8 Puzzle on Graph 全探索が許されそうな制約。重複チェックのためのハッシュ表のキーを文字列にするか配列にするかで悩んだ。結果的に文字列ベースの探索で AC になった。 提出 #2676864..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20211022.html#p01
2021-10-22T21:25:08+09:00
AtCoder Regular Contest 120/C 問題 Swaps 2
ds14050
AtCoder
精進ですよ。水 diff だけど難しい。考えがまとまるまで1日かかった。 問題の操作 隣接2要素をスワップして +1/-1 するというけど、考えやすいように複数の操作をまとめるとこう。 ある要素 Ai を右に(左に)いくつか移動する。 たとえば右に5移動したなら移動先の値は Ai-5 になる。 たとえば右に5移動したなら、飛び越された5つの要素..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20211010.html#p01
2021-10-13T03:24:33+09:00
エクサウィザーズプログラミングコンテスト2021(AtCoder Beginner Contest 222)
ds14050
AtCoder
大反省回。未だに ABC で ABC の3完敗退を繰り返していることに驚きを隠せない。今回がそうだしついこの前の ABC219 もそうだった20210918。ついでに言うと3年以上前の第2回参加回もそうだった☞。まるで成長していない……。戒めとして普段はとばす A 問題から振り返る。 A - Four Digits 20 年前の自分だったら N の常用対数から N の桁数を求めてくっつける 0 の数を決定していた。 だけどとある WSH 関連の掲示板で、十分な数の 0 をくっつけてから必要な文字数だけ切り出す方法を知った。 提出 #26434564 (AC / 25 Byte) 他の人の提出を見ると printf かそれに類するメソッドを使うものが多かった。Ruby で最初に提出した人は rjust を使っていた。目的にぴったりのメソッド(rjust)がある以上、それを使うのが最善だった。 B - Failing Grade コメントのしようがない。スクリプトを読んで。 提出 #26437560 (AC / 63 Byte) C - Swiss-System Tournament ..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20211004.html#p01
2021-10-07T15:13:43+09:00
AtCoder Beginner Contest 221/F 問題 Diameter set
ds14050
AtCoder
精進ですよ。おとといあった ABC の F 問題。 コンテスト時間中は木の中心についての理解がぼんやりで解答に至らなかった。そもそも木の中心などというものを考えたことがなく、でもサンプルの2のようなスター型の木で制限時間内に答えを数えきるためには、中心を中心とした組み合わせを考えるしかなかった。 木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を2度呼び出して答えとしたことがあった。後にそれが運任せではなく確かな手段らしいことを知った。証明は知らない。 木において辺とは頂点集合を左右に分けるものだということを知っている。どの辺でもいいので1本選んで真ん中に横向きに置いて形を整えるとアレイ(亜鈴)型になるイメージ。コンテスト中には思い出せなかった。そのせいで問題の木を具体的にイメージする力が弱かった。このことは今朝のトイレで考えるでもなくふと思い浮かんだ。 たとえば直径..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20210928.html#p01
2021-09-28T09:08:18+09:00
AtCoder Beginner Contest 220/F,E
ds14050
AtCoder
昨日あった ABC。今回は全体に易化傾向で、D 問題で茶 diff。F 問題でも水 diff。ただし同じく水 diff だった E 問題の方が F 問題より解かれていない。ABC は5完6完を狙いたいところなんだけど、ABCD を 17 分4完でレートは微減。あなたは残りの 103 分間何をしていたのですか? F 問題 Distance Sums 2 こちらが先に解けた。やり方はすぐにわかる。1か所だけ素直に求めて、あとは辺の左右にあるノード数の差を見ながら差分を更新する。すぐに実装できたかというとそうはいかない。どう..
-
http://vvvvvv.sakura.ne.jp/ds14050/diary/20210925.html#p01
2021-09-26T00:35:52+09:00
AtCoder Regular Contest 127/A,B
ds14050
AtCoder
A 問題 Leading 1s 制約上の上限が 16 桁だっていうから、f の値の上限も 16。たとえば f(x) = 5 のとき、x のプリフィックスは 11111 か 111110 に限られる。f の値..