自作キーボード「ABQ」を語る
友人のsuikaさんがキーボードを制作してまして、現在私は業務でもプライベートでもこちらのキーボードをバリバリ使い倒させてもらっています。
今はもうこのキーボードなしには仕事になりません。普段はリモートで働いていますが、たまの出社時にこれを忘れた日には、ただでさえ低い生産効率が半分になります。
ABQと名付けられたこちらのキーボード、これを作ってくれた友人への感謝も込めて、その魅力を語っていきたいと思います。
出会い
ーーー８月某日
「例のもの、持ってきましたよ」
そう言うと友人はリュックから黒い箱を取り出しました。今日は待ちに待ったキーボード受け渡しの日です。
「ついに自分もマイキーボードを持つことができる…！」と、期待に胸を踊らせ蓋を開けました。
出てきたものがこちら。
.
.
.
.
.
.
.
.
.
.
どうみても鉄塊です本当にありがとうございました。
話を聞くと、どうやらこの"キーボード"がちゃんと私の知っているキーボードになるためには、ここから更に「キースイッチ」と「キーキャップ」なるものを買わなきゃいけないようです。
この頃は本当にキーボード界隈に対する知識が皆無だったので、 割とめんどくせー！と思いながら情報収集をしてました。
鉄塊をイケてるキーボードにすべく、let's組み立て！ということで出会い編終わりです。
組み立て
購入！
揃えるもんは揃えたぜ！と思ったところに友人からLine。「ちゃんとルブ買いました？」
lubricant、潤滑剤です。キースイッチ内部の軸、スプリング、外殻との間で生じる摩擦を低減することで、タイピングエクスペリエンスの向上が見込めるそうです。なんだタイピングエクスペリエンスて。
しかも自転車のチェーンみたく「スプレーでパパっと塗布」とかではなく、一個一個キースイッチを分割して筆で潤滑剤を塗りつける必要があるみたいです。イヤだー！！めんどくさいー！！
でもまぁ、¥10,000以上出してキースイッチ＆キーキャップを買ってる時点で一般人からしたらだいぶアレなので、もう沼るところまで沼ることにしました。
作業！
.
.
そしてキーキャップをすべてのスイッチに嵌め込んだら.......
.
.
.
.
.
完成〜〜〜🎉🎉🎉
ということで無事にABQを「僕の知っている」キーボードに仕上げることができました。
スイッチとか潤滑油とか、その他作業に必要な工具とかも揃えたらだいたい¥12,000円はかかっちゃいましたね。。。これもタイピングエクスペリエンスのため。。。！
ABQのいいところ
本題です。ABQは何が素晴らしいのか、語っていきたいと思います。
①コンパクト
まずはなんと行ってもそのサイズに目が行きます。とにかくコンパクトで、キー数はわずか41個です。
これの何がいいって、ほぼすべてのキーがホームポジションから1キー以内の場所に収まっているんですよね。例外は最下段の両端キーとBキーのみです。
特にエンターキーがホームポジションセット時の右手親指にあるのは本当にありがたいですね。JISだろうとUSだろうと、市販規格はエンターキーが遠すぎるんです。
数字キーが近いのも素晴らしい、、、を話す前に、どうやってこのキーボードで数字を打つのかについて軽く説明すると、レイヤーキーを使います。
ShiftとかControlと似たような種別のキーで、これを押している間は各キーに別の文字種が割り当てられます。
- エンターキーを押しっぱなしにして数字レイヤーに切り替える
- そのままEキーを押す
と数字の3が打てます。
ABQに変えたことで、ホームポジションを一切崩さずにタイピングできるようになりました。
これだけで相当ストレスが減るので、みなさんもキーボード購入の際は40%キーボードを検討の候補に入れてみてほしいです。
② キー配置の変更が簡単
自作キーボードの魅力として、「キー配置を自分の好きなように変えられる」ことがあげられるかと思います。ただ、一般的にこの作業はそこそこめんどくさいらしく、やれ「ファームウェアをキーボードのマイコンに書き込む」だの、「C言語にてキーマップのコードを変更してファームウェアをビルドする」だの、それなりに面倒くさげな作業を伴うようです。
ABQはブラウザから簡単にキー配置を変更できます。 百聞はなんとやら、ということで配置変更している様子がこちら。
キーボードを繋いで、Remapというこちらのwebアプリにアクセスするだけです。
自分の用途・好みにあったキー配置を決めるのもまた自作キーボードの楽しみかと思います。特に最初の頃は適切な配置が全然決まらず、ひたすら試行錯誤を経るフェーズがあります。自分に至っては、半年経った今でもまだ配置に改良の余地が見つかっています。
この過程が簡単に行えるというのもまた、ABQの良さですね。
③ はんだづけ不要
地味にこれが一番でかいかもです。一切のハンダ付けが不要です。
どうも世の中の大概の自作キーボードにはハンダ付けが必須みたいです。当たり前のように必須なので、もはやビルドガイドの「必要なもの」項にも書かれていないレベルです。
でも一般家庭にハンダはないし、一般人にハンダの技術はないんですよね。
ABQは本当に一切のはんだ付け作業がいりません。
【必要なもの（本当）】
・キースイッチ
・キーキャップ
・（タイピングエクスペリエンスにこだわりたい人のみ）潤滑剤
面倒くさい作業はすべて開発者が巻き取ってくれています。なんてユーザー思いなプロダクトでしょう。
ABQをおすすめしたい人
というABQの良さを踏まえた上で、１ユーザーとして以下のような人にABQをおすすめしたいです。
coming soon...
どうやら友人氏、新しいキーボードの開発も進めているみたいで、そちらも軽く紹介。
いやかっけぇ。。。
角度がついたりキー数が少し増えたりしていますが、基本的なコンセプトはABQとほぼほぼ同じっぽいです。少なくとも上述したメリットは全部享受できそう。個人的にはRotary Encoder対応という点にワクワクが止まりません。
いくらするのかわかりませんが自分は値札を見ずに購入しようかと考えてます。新たなタイピングエクスペリエンスを求めて。。。。
友人氏の今後の展望に期待大ですね！
おわり
参考
友人氏のHP
AtCoder Beginner Contest 154
E - Almost Everywhere Zero
解法
AtCoderの解説に準じた解法で解きます。桁DPとよばれるタイプのDPを用います。
入力例3に対してdp_tableを埋めていく指針を説明します。
[入力例3] N = 314159 K = 2
このケースのdp_tableを先に描くと以下のようなものになります。
添え字が3つもあるので考えるのがちょっと大変です。
具体的に、例えば表中の緑色のセルが意味するところは、
「4桁目の時点で、0でない数字が2つあり、4桁目までの数字が314159と一致していない数字の個数はX個」
です。以下のような数字が具体例として挙げられます。
1100**, 3009**, 0890**, 0013**, ... は全部でX個
別例として、上の表中の緑色のセルが意味するところは、
「3桁目の時点で、0でない数字が1つあり、3桁目までの数字が314159と一致している数字の個数はY個」
です。
「3桁目までの数字が314159と一致している」数字の候補は
314***
のただ1つです。これは既に「0でない数字が1つ」ではないので、Yは明らかに0です。
以下表中のA,Bを足したものが本問題の解答になります。
Aは前例同様0です。なぜなら、「6桁目までの数字が314159と一致している」数字の候補は314159ただ1つであり、これは「0でない数字が2つ」ではないからです。
Bは「6桁目までの数字が314159と一致していない」数字であり、候補は314158個あります。
最終的に「314159」と「314159未満」の数字の中から条件に合致するものの個数を算出し、出力するという流れになります。
解説
初期状態
桁dpの初期条件は以下のような配置になります。
dp[0][0][0]、つまり「0桁目の時点で0でない数字が0つあり、0桁目までの数字が314159と一致している数字の個数」、は1個、それ以外は0個です。
解説動画の1:10:45あたりでこの初期状態に関する解説があるので詳しい話はそちらに譲ります。
1桁目への遷移
i = 1の行を考えます。このテストケースで1桁目にはどのような数字がとれるでしょうか。
1桁目の場合、明らかに0~3のいずれかになります。その中でどの数字を取ったかで遷移先が変わります。
1. 0をとった場合
取った数字が0なので、0でない数字は遷移元と同じ個数のj=0のままです。
1桁目に0をとり、1桁目の数字が314159と一致しなくなったので、k=1に遷移します。
遷移元のパターンが1通りで、新しく選ぶ数字が[0]の1つなので、遷移先のパターンは1個(=1 * 1)増加します。
2. 1,2を取った場合
取った数字が0ではないので、0でない数字は遷移元から1つ増えてj=1になります。
1桁目に1もしくは2をとり、1桁目の数字が314159と一致しなくなったので、k=1に遷移します。
遷移元のパターンが1通りで、新しく選ぶ数字が[1,2]の2つなので、遷移先のパターンは1個(=1 * 2)増加します。
3. 3を取った場合
取った数字が0ではないので、0でない数字は遷移元から1つ増えてj=1になります。
1桁目に3をとり、1桁目の数字は314159と一致しているので、k=0のままです。
遷移元のパターンが1通りで、新しく選ぶ数字が[3]の1つなので、遷移先のパターンは1個(=1 * 1)増加します。
2桁目への遷移
i = 2の行を考えます。このテストケースで2桁目にはどのような数字がとれるでしょうか。
これは1桁目の数字に依存します。もし1桁目が既に3、つまり、「1桁目までの数字が314159と一致している(k=0)」場合、2桁目に取れるのは0か1だけです。（例えばもし2をとってしまうと 32**** となり、その時点で314159をオーバーしてしまう）
逆に1桁目が3でない、つまり、「1桁目までの数字が314159と一致していない(k=1)」場合、2桁目には0~9の数字を自由にとることができます。
dp[1][0][1]からの遷移を考えます。この1個(0*****)に関しては、2桁目の数字を0~9の中から選ぶことができます。
0を取った場合は、0でない数字の個数は変わらず、j=0のままです。
1~9を取った場合は、0でない数字は1つ増え、j=1に遷移します。
どちらのケースにおいても、既にNと一致していない数字からの遷移であるため、k=1のままです。
遷移先の個数は、遷移元の個数 x 取れる数字の数だけ増加します。
dp[1][1][1]からの遷移を考えます。この2個(1*****, 2*****)に関しても、2桁目の数字を0~9の中から選ぶことができます。
0を取った場合は、0でない数字の個数は変わらず、j=1のままです。
1~9を取った場合は、0でない数字は1つ増え、j=2に遷移します。
どちらのケースにおいても、既にNと一致していない数字からの遷移であるため、k=1のままです。
dp[1][1][0]からの遷移を考えます。この1個(3*****)がとれる2桁目の数字は、0, 1のみです。
0を取った場合は、0でない数字の個数は変わらず、j=1のままです。
またこの場合、2桁目の段階で314159と一致しなくなったので、k=1になります
1を取った場合は、0でない数字は1つ増え、j=2に遷移します。
この場合、2桁目の段階で31****となり、314159と一致しているので、k=0のままです
遷移まとめ
遷移は以下のようになります。
x = "i+1桁目で取れる数の個数" for s in range(x): dp[i+1][next_j][next_k] += dp[i][j][k]
ただし、
if k==0: x = (Nのi+1桁目の数) else: x = 9 # k==0(i桁目までNと一致）なら、i+1桁目は自由にはとれない(Nのi+1桁目の数まで) if s == 0: next_j = j else: next_j = j+1 # 次にとる数が0のときのみjはそのまま if k==0 and s==(Nのi+1桁目の数): next_k = 0 else: next_k = 1 # k==0 (i桁目までNと一致)で、さらにi+1桁目もNのi+1桁目と一緒なら、next_k = 0
これを踏まえて3桁目への遷移を書くと以下のようになります。
Kをこえたjに関しては走査から除外して大丈夫です。この問題ではjが小さくなる方向に遷移することはないからです。
実装
N=int(input()) K=int(input()) def dp(N,K): keta = len(str(N)) table = [[[0,0] for i in range(K+1)] for j in range(keta+1)] table[0][0][0]=1 for i in range(keta): for j in range(K+1): for k in range(2): digit = int(str(N)[i]) if k==0 else 9 for x in range(digit+1): next_j = j if x == 0 else j + 1 next_k = 0 if k == 0 and x == digit else 1 if next_j > K: continue table[i+1][next_j][next_k]+=table[i][j][k] return table[keta][K][0] + table[keta][K][1] print(dp(N,K))
レート変化
AtCoder Beginner Contest 153
E - Crested Ibis vs Monster
atcoder.jp コンテスト中には解けませんでした。
解法
ナップサック問題です。
動的計画法を用いてdp_tableを埋めていき、右下隅の数字を出力します。計算時間はdp_tableを埋める時間と同じでO(HN)になります。
解説
入力例１に対してdp_tableを埋めていく指針を説明します。
[入力例1] 9 3 8 3 4 2 2 1
ここでXは、魔法1〜2を組み合わせて体力5を減らすための最小の魔力を表します。いきなりこの値を求めるのは困難ですが、上から順番にセルを埋めていくことで、この値を求めることができます。
最も左上からスタートします。ここのセルは魔法1: [8,3]を使って体力1を減らすための最小の魔力を示します。この値は3です。
同様に考えてこの行を埋めていくと以下のようになります。
2行目は魔法1〜2を組み合わせて体力hを減らすための最小の魔力を算出するフェーズです。ここから上の行の値を参照して値を求める必要が生じます。
ここで考えるのは魔法2を使うor魔法2を使わない(魔法1だけでその体力を削る)で、どちらがより少ない魔力で達成できるかの検討です。魔法2を使う場合、魔力の最小値は2です。魔法2を使わない場合は、魔法1だけを使って体力1を削る最小の魔力(=上のセルの数字)を持ってきます。ここでは魔法2を使うパターンのほうがより少ない魔力で体力1を削れるので、その値2を入れます。
考える体力が魔法iの攻撃力より低い場合は、魔法iの魔力 or 魔法iを使わないパターンの魔力を考えれば良いです。
体力5を削る時も、魔法2を使うor魔法2を使わない(魔法1だけでその体力を削る)で、どちらがより少ない魔力で達成できるかを考えます。この状況において言い換えると以下の2パターンの比較になります。
- 体力1 (=5-魔法2の攻撃力4)を削るための最小の魔力(2) + 魔法2を使うための魔力(2)
- 魔法2を使わずに体力5を削るための最小の魔力(3, このセルの直上の数字)
ここでは2.のほうが魔力が少ないので、そちらの値を代入します。
考える体力が魔法iの攻撃力より高い場合は、(体力-魔法iの攻撃力を削るための魔力+魔法iの魔力) or 魔法iを使わないパターンの魔力を考えることになります。
このように考えて2行目を埋めると以下のようになります。
3行目も同様に考えます。魔法3を使うパターンor使わないパターンで比較し、セルを埋めていきます。
このようにして右下のセル、つまり魔法1〜3を組み合わせて体力9を減らすための最小の魔力を求めることができました。
実装
H,N=map(int,input().split()) ls=[list(map(int,input().split())) for i in range(N)] def dp(H,N,ls): #↓0行目に「全てのセルの値が∞の行」をいれることで、1行目だけ特別なロジックを実装する必要がなくなります。 table=[[float('inf')]*(H+1)] + [[0]*(H+1) for i in range(N)] for i in range(1,N+1): atk,cost=ls[i-1][0],ls[i-1][1] for h in range(H+1): if atk>=h: table[i][h]=min(table[i-1][h], cost) else: table[i][h]=min(table[i-1][h], table[i][h-atk]+cost) return(table[-1][-1]) print(dp(H,N,ls))
まとめ
偉そうに書き殴りましたが競プロ界の重鎮けんちょんさんが私よりはるかに分かりやすく、より一般的な動的計画法の解説をしてくださっているので、そちらも参考にしてみてください。
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ - Qiita
貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題 - Qiita
レート変化
4完とはいえそれなりに早かったので上がるかと思いきやそうは問屋が下ろしてくれませんでした。
次回こそ！
東方Projectフルオーケストラ公演『幻想郷の交響楽団 - 夢現つ嘯風弄月 - 』感想
行ってきました！いつも通り！！一人で！！！
感想を言い合える友達が欲しい人生だった。だがしかし何も記さずに終えるのも勿体無いので感想をぽろぽろとしたためます。
開演前
JAGMOさんの公演は過去に５回ほど（東方４回、Undertale１回）参戦していますが、今回は演奏曲目がすごく自分好みなのもあって、奮発してSS席（税抜¥9,800）をとりました。
買ってから流石に高いかなぁと感じましたが、いざ座ってみると随分とゴキゲンなポジションで大変テンションが上がりました。
これまでずっと２階席で聴いてたのですが、そこと比べると明らかに臨場感や音の分離感が優れてました。単純に奏者との距離が近くなって、いろんな音がいろんな方向から聴こえるようになっただけだとは思うのですが、こっちのほうが耳が気持ちよかったです。
では感想をば。
感想（だいたい演奏順）
永夜抄
「竹取飛翔～Lunatic Princess」
「月まで届け、不死の煙」
親の声より聴いた曲。いい感じの前菜でオケに入り込む準備ができた感じ。
鬼形獣
「セラフィックチキン」「アンロケイテッドヘル」「偶像に世界を委ねて〜Idoratrize world」「聖徳太子のペガサス～Dark Pegasus」
偶像に〜が聴きたくて来たってのも６割くらいあったので非常に楽しみだった曲たち。肝心の曲はドラムスがゴリゴリにはっちゃけてて楽しかったと言えば楽しかったのですがツーバスが入ってきたあたりで多少過剰じゃないかという気がしてきました笑。割と曲自体キメキメで演奏するポイントが多いので、これはシンプルに原曲に寄せて演奏するだけでも十分楽しい曲になるんじゃないかなぁ。
星蓮船
「春の湊に」「感情の摩天楼」「平安のエイリアン」
感情の摩天楼が良曲過ぎ＆オケ映えし過ぎで終始涙腺を刺激されていました。Aメロでのバイオリン重奏、何回聞いても極まりますね。平安のエイリアンは不協和音の使い方とクレッシェンドでの盛り上げ方が大変お上手。わかっててもゾクゾクしてしまう。
憑依華
「夜が降りてくる」「砕月」「幽雅に咲かせ、墨染の桜～Border of Life」「憑坐は夢と現の間に～Necro-Fantasia」
墨染とネクロファンタジアの絡み方がよかった。でもやっぱり砕月が好き。幻想郷の原風景が一番想起させられるのは個人的にはこの曲。
紺珠伝
「故郷の星が映る海」「ピュアヒューリーズ～心の在処」
後半戦、雨音のSEに続いて故郷の星が映る海が入ってくる下りはもう完璧。終始鳥肌。でもピュアフューリーズの方はもっと激しめにして緩急つけてほしかったなという我儘。故郷の〜に溶け込み過ぎてて演奏されてるのわからんかった。
地霊殿
「ハートフェルトファンシー」「少女さとり〜3rd eye」「霊知の太陽信仰〜Nuclear Fusion」「死体旅行〜Be of good cheer!」「ハルトマンの妖怪少女」
ボス曲たちが暴れまわってて大変よろしおすなぁという所感です。古明地姉妹曲でわちゃわちゃして終わるかなーってところに霊知の太陽信仰が割り込んできたところ、空が全速力で戦いに割り込んでくるような絵が容易に想像できて笑ってしまいました。死体旅行はもっと長くやってほしかった！演奏されてるの初めて聴いたけど全然オケ負けしないわこれ。
旧作
曲と名前が一致しなくて苦しかった。「え何これめっちゃいい曲」ってなるたびに原曲をちゃんと知っておきたかったなぁと思った。
紅魔郷（アンコール）
親の声より聴いた曲で〆。セプテットはオケで演奏されるために生まれたような曲だなと思いました。よかったんだけどこれをアンコールにやるならダブルアンコールは欲しかった。安定の終わりすぎてちょっと物足りなさを感じた。
まとめ
- 終盤の地霊殿ボスラッシュがめちゃめちゃエキサイティングでそれだけで行った価値はありました。一方一番楽しみだった鬼形獣は伸び代がいっぱいあるのでこれから楽しみ。
- オケでのドラムスの存在、塩梅が難しいなぁと感じました。東方を原曲チックにやろうと思ったら欠かせないピースではあるものの、大抵の場合自己主張強過ぎて破綻気味になってしまいがち。ゆったり聴きたい音楽で２、４拍を強調されすぎると、オケ特有の浮遊感がなくなっちゃう気がします。全体的にもう少し溶け込み気味に、ソロみたいにはっちゃけるところでははっちゃけて、メリハリがついてほしい。
- 6ボス曲ウオオオオオEX曲ウオオオオオオオもいいんだけどそれ以外の曲にも日の目を当ててほしい。道中曲にもいっぱいいい曲ありますよー！！
的な。
でもなんやかんや言いながら次回も行きます。感情の起伏が少ない今日この頃、心を揺さぶってくれる数少ない機会であることは間違い無いので！
AtCoder Beginner Contest 152
D - Handstand 2
https://atcoder.jp/contests/abc152/tasks/abc152_d
場合分けがしんどかった。
解法
1〜Nを以下実装のフローで全探索する。
実装
入力値の先頭の桁の数、末尾の桁の数、その間の数を返す関数を作る
def bunkai(n:int): ls=list(str(n)) top,bottom=int(ls[0]),int(ls[-1]) if n<=99: middle=0 else: middle=int("".join(ls[1:-1])) return top, middle, bottom
Nを分解して保持しておく
N=int(input()) Nt,Nm,Nb = bunkai(N) # N=47856 => (Nt, Nm, Nb)=(4, 785, 6)
探索中の数字iも分解して(t,m,b)で保持しておく。
b==0のときは飛ばして次の探索に行く（∵先頭の桁が0の数字はない）
t==bのときは(A,B) = (i, t)という組が取れるのでcount+=1
count=0 for i in range(1,N+1): t,m,b = bunkai(i) if b==0:continue if t==b:count+=1
N<=99のときは、(t,b)をひっくり返した2桁の数字がN以下ならcount+=1
if N<=99: if int(str(b)+str(t))<=N:count+=1 else:
N>=100のときは場合分けが必要。
まず、Nの数値によらず、「Nの桁数-1」の桁までは確定で候補に入れることができるのでこちらを先に考える。
(N,i)=(47856, 24)ののケースを試しに考える。
2桁：42 の1個 3桁：4X2 の10個 (X=0,1,2,3,...,8,9) 4桁：4XX2の100個 (X=0,1,2,3,...,98,99) つまりそれぞれの桁で、10の(桁数-2)乗だけcountに追加できる
keta = len(str(N)) for x in range(keta-2): count+=10**x
4XXX2、つまりNと同じ桁数を考える時、場合分けが必要。
Ntがbより大きい時は、遠慮なくXXX=000〜999の103個をcountに追加できる。
Ntがbより小さい時は、この桁数では条件をみたすXXXが存在しないので、count追加なし。
x+=1 if Nt>b: count+=10**x elif Nt<b: count+=0
今回のケースのように、Ntがbと同じ場合はさらに場合分けが必要
N=47856, i = 24 iがひっくり返って5桁になった4XXX2がNの範囲でどれだけとれるか考える 1. Nの最後の桁の数字Nbが、iの先頭の桁の数字tよりも大きい場合（今回のケースに該当） 40002, 40012, 40022, ... , 47842, 47852, の786個がとれる。これはNm+1個。 2. Nの最後の桁の数字Nbが、iの先頭の桁の数字tよりも小さい場合（たとえばN=47851のとき) 40002, 40012, 40022, ... , 47842, 47852<=こいつがとれない！ので785個がとれる。これはNm個。
elif Nt==b: if Nb>=t: count+=Nm+1 else: count+=Nm print(count)
以下コード全体
def bunkai(n:int): ls=list(str(n)) top,bottom=int(ls[0]),int(ls[-1]) if n<=99: middle=0 else: middle=int("".join(ls[1:-1])) return top, middle, bottom N=int(input()) Nt,Nm,Nb = bunkai(N) count=0 for i in range(1,N+1): t,m,b = bunkai(i) if b==0:continue if t==b:count+=1 if N<=99: if int(str(b)+str(t))<=N:count+=1 else: keta = len(str(N)) for x in range(keta-2): count+=10**x x+=1 if Nt>b: count+=10**x elif Nt<b: count+=0 elif Nt==b: if Nb>=t: count+=Nm+1 else: count+=Nm print(count)
レート変化
Eも解けた、が、解説を見る限りちょっと正攻法ではないような気がする。。。
なんにせよレートもブチ上がって一気に4桁が見えてきたのでこの調子で精進致す。
キーエンス プログラミング コンテスト 2020
B - Robot Arms
解法
ロボットを位置で昇順ソートして１体ずつ見ていき、腕がぶつかるロボットがいたら消していく。 ぶつかった２体の内、右腕がより右側に伸びているロボットを消す。
走査した時点でもっとも右に伸びている右手の座標を保持しながら走査すれば計算量はO(N)になる。
ロボットA：○ーーー●ーーー○ ロボットB： ○ーー●ーー○ この時はBを消す ロボットA：○ーーー●ーーー○ ロボットB： ○ー●ー○ この時はAを消す
実装
n=int(input()) ls=[list(map(int,input().split())) for i in range(n)] ls.sort() first_robot=ls.pop(0) max_right=first_robot[0]+first_robot[1] for robot in ls: left=robot[0]-robot[1] right=robot[0]+robot[1] if left<max_right: #ぶつかった時 n-=1 if right<max_right: #新しいロボットの方が右にはみ出ていないパターン max_right=right else: max_right=right print(n)
C - Subarray Sum
解法
l==r、つまり数列から1個だけ取り出してそれを合計とすることが許されているので、以下のように数列を組めばそれが解になる
例1) N,K,S = 5, 3, 10 => [10, 10, 10, X, X] (l,r)=(0,0),(1,1),(2,2) の計3つの組み合わせが条件を満たす。Xは適当な数 例2) N,K,S = 10, 7, 999 => [999, 999, 999, 999, 999, 999, 999, X, X, X] (l,r)=(0,0),(1,1),(2,2),(3,3),(4,4),(5,5),(6,6) の計7つの組み合わせが条件を満たす。Xは適当な数
ここで適当な数Xは、それを含む組み合わせの合計がSにならないようにしなくてはいけない。 （例えば例1でX=5とすると(l,r)=(3,4)も条件を満たしてしまい、組み合わせの数が4つになってしまう） Xは、Sが109ではないときには109にしておき、Sが109の時だけは109 -1にしておけばよい。
実装
n,k,s=map(int,input().split()) if s==10**9: x=10**9-1 else: x=10**9 ls_a=[s]*k ls_b=[x]*(n-k) print(" ".join(list(map(str,ls_a+ls_b))))
レート変化
レートを100あげるのに半年かかりました
AtCoder Beginner Contest 151
D - Maze Master
コンテスト中に解くことはできませんでした。
クソ萎えの翁。
解法
迷路の解として考えられるルートを全部考える。 スタート地点を1つ決めて、そこからもっとも遠い場所への距離を求める。
左上がスタートの場合 ##### #0..# #.#.# #...# #.#.# ##### ##### #01.# #1#.# #...# #.#.# ##### ##### #012# #1#.# #2..# #.#.# ##### ##### #012# #1#3# #23.# #3#.# ##### ##### #012# #1#3# #234# #3#.# ##### ##### #012# #1#3# #234# #3#5# ##### よって最長距離は5 その右がスタートの場合 ##### #.0.# #.#.# #...# #.#.# ##### ##### #101# #.#.# #...# #.#.# ##### ##### #101# #2#2# #...# #.#.# ##### ##### #101# #2#2# #3.3# #.#.# ##### ##### #101# #2#2# #343# #4#4# ##### よって最長距離は4 以下繰り返し
みたいなことをうまい具合に達成できるコードを考える。 最短距離を考える計算がO(HW)、スタート位置の決め方がHW通りなので、計算時間はO(H2 W2)。
制約が1≦H, W≦20とゆるいのでこれでも通る。
実装
探索中のIndexErrorを防ぐため迷路の周りを壁で囲む。
import copy h,w=map(int,input().split()) maze = [['#']+list(input())+['#'] for i in range(h)] maze.insert(0,['#']*(w+2)) maze.append(['#']*(w+2)) """ ... .#. ... .#. ↓ ##### #...# #.#.# #...# #.#.# ##### """
迷路とスタート地点の座標を引数に取り、迷路におけるスタート地点からもっとも遠い座標までの距離を返す関数を作る。
def get_max_length_from_start(maze,x,y): tmp_maze=copy.deepcopy(maze) length=0 #スタート地点からの距離 searching = [[y,x]] #スタート地点からの距離がlengthである座標の集合 while len(searching)!=0: next_searching_list=[] for point in searching: tmp_maze[point[0]][point[1]]='/' #探索済の座標を埋める mawari = [ [point[0]+1,point[1]], [point[0]-1,point[1]], [point[0],point[1]+1], [point[0],point[1]-1] ] #探索点の四方をチェック next_searching = list(filter(lambda x:tmp_maze[x[0]][x[1]]==".",mawari)) #四方のうち、道であるものを格納 if len(next_searching)==0: #末端にいる場合、長さをmax_lengthとして保持 max_length=length continue next_searching_list += next_searching searching = list(map(list, set(map(tuple, next_searching_list)))) #next_searching_listの重複した要素を排する length+=1 return max_length
迷路中の全部の点に対して最長距離を更新しながら取得していく
ans=0 for y in range(1,h+1): for x in range(1,w+1): if maze[y][x]=='#': continue max_length=get_max_length_from_start(maze,x,y) ans = max_length if max_length>ans else ans print(ans)
レート変化
THE 停滞期。
