windowsでもかっこいいCUI環境を作りたかった
Windowsのコマンドプロンプトってよくわからないですよね? だからと言ってbash on Windowsインストールしても結局ウィンドウはWindowsのものなのでダサいですよね?
どうせなら少しでもかっこよくしようということで環境を作ったのでメモ
まずはbashを入れる
こちらの記事を参考にbashをwindowsで使えるようにします。
これだけでbashは使えるようになるのでls
コマンドとかが使えるようになります。
Cドライブは /mnt/c
にマウントされている状態なのでwindowsのファイルシステムで管理されているファイルも普通にアクセスできます。
見た目をどうにかする
一番重要な見た目ですがcmderという素晴らしいソフトウェアがあるのでこれをダウンロードして使います。 初期状態だとcmd.exeが上がるようになってるのでbashが上がるようにします。
ついでに全画面にしたときに余計な部分が消えるように設定すると見た目をだいぶかっこよくできます。 設定方法はこちらのサイト
あとはzshにしたりtmuxいれたり
このあたりを見ながらbashではなくzshにしてtmuxとか入れると楽しくなります
(スクショはまだまだカスタム中なので省略)
ARC098/ABC098 D - Xor Sum 2
復習日記
問題概要
- 長さの整数列が与えられる
- を満たすの組の個数を求める
考え方
サンプルを見てみると、
となっていて、の時にちょうど1の位置がお互いに干渉していないことがわかります。
例えば、1がどこかの桁に2つ以上あるときにをとると0になってしまいますが、加算をすると繰り上がって1の位置がずれてしまいます。
ということは、区間のすべての桁について1の個数が1個または0個になるような区間を求めれば答えを求めることができることがわかります。
というのが解説にもありますが、区間を尺取りで実際に計算しながら求めれば答えを求めるのには十分です。
数える実装が上手くきれいに書けなくてサンプルがなかなか通らなかったです。 結局右側を順番に回して左側を詰めていく実装に落ち着きました。 あとほかの人の実装が頭よかったので参考にしました。
ABC109参加してない記録
本番は参加できませんでしたが解いてみた感じで書きます
A - ABC333
が奇数になるCが存在するか確かめる問題
偶数に何をかけても偶数なのでが偶数かどうかで判定
B - Shiritori
しりとりが正しいか判定する問題
これは本当にやるだけ。出現済みかどうかはHashSet等で管理すれば楽だと思います。
C
すべての都市を訪れることが可能な最大の移動距離を求める問題
ずつ移動するので移動距離はの倍数になります。
番目と番目の都市を移動するときの距離が必ずの倍数でないといけないので、
逆を言うとすべての都市のからの距離がの倍数であればどの順番であってもちょうどたどりつくことができます。
以上のことから、すべての都市の座標のXからの距離の最大公約数を求めると以上の条件に当てはまる最大の移動距離を求めることができることがわかります。
D
指定された操作を行いコインが偶数枚置かれたマスを最大化する問題
マス目上の全てのコインを足したときに偶数枚であれば何らかの操作ですべてのマスのコインのマスを偶数枚にすることができると予想できます。
また、奇数枚であればどこか1か所を除いて偶数枚にすることができると予想できます。
ということはどこか一か所に向かってコインを集めるような操作をすればうまく偶数枚にすることができそうです。
実装として簡単なのは全体を横に移動してから端の縦を下に移動させる方法だと思います。
ARC101/ABC107 D - Median of Medians
復習日記
解説その他諸々を見ながらやっていきます。
問題概要
- 長さの数列を昇順に並べたときの番目の要素の値を中央値とする
- 長さNの数列の各についての中央値をと置く
- すべてのに対してのを集めた数列を作り、その数列の中央値を求める
考え方
まず、中央値について考え方を整理します。問題概要には中央値の定義は、
長さの数列を昇順に並べたときの番目の要素の値を中央値とする
と書かれていますが、これを言い換えると、長さの整数列の中央値をとしたときに、
- の中に以上の要素が個以上含まれるの中で最大の整数
であるといえます。
この「条件を満たすものの中で最大のもの」という考え方に注目すると二分探索で解くことができることがわかります。
これは連続部分列の中央値を並べた数列にも同様のことが言えて、最終的にこの問題は、
- のうち以上の要素は何個か?
という質問に置き換えることができます。
ここでについて言及するように言い換えると、
- の連続部分列 のうち, 以上の要素を個以上含むものは何通りか?
という質問になります。
次に、この質問に対してどのような解法をとるかを考えます。
毎回数えてしまうと計算量が多く間に合いません。そこでより大きい数を、より小さい数をに置き換えて累積和を取ります。
そうするとその区間の累積和が0以上であればより大きい数の個数が過半数であるということがわかります。
さらに言えば、からまでの累積和を取っておけば、
と計算をすることで求めることができます。
最後に、区間の累積和が0以上である区間の個数を求める方法ですが、としたときに、
- であるの組み合わせの個数
と言い換えることができます。これは反転数を求めるアルゴリズムを使うと高速に求めることができます。 反転数のアルゴリズムについては蟻本のp162または螺旋本のp175に載っています。
提出コード(諸々を写経)
かなり難しい700点ですね…
これを時間内に解くだけパフォーマンスが2000を超えるので、目標にしたいところです。
ABC108/ARC102 D - All Your Paths are Different Lengths
復習日記
700点問題はさすがに難しいので解説その他もろもろを見ながら解きました
問題概要
整数が与えられるので以下の条件を満たすグラフを一つ出力。
- 頂点が以下で頂点の番号はまで
- 辺数が60以下で長さが
- 辺は頂点の数字が小さいほうから大きいほうに引く
- 頂点1から頂点までのパスがちょうど個あり、各パスの長さがまで
考え方
一つ目のサンプルが少しヒントになっていると感じました。 ポイントは長さ1でつながってるパスがあり、そのパスに対して長さ0の辺を引いているところ。 長さの順にパスを並べてみると、
- [0, 0, 0, 0]
- [0, 0, 0, 1]
- [0, 0, 1, 1]
- [0, 1, 1, 1]
というようになっていて、ここから2進数のように見える発想が出れば解法の半分までたどり着くことがで来そうです。
個の頂点に対して辺の長さを1だけでなくてと変えて同じように0の辺を作ればのパスを作ることができます。
これでちょうどの時なら作ることができました。
ここで例えばだとすると上の図ではのパスが足りません。
この時に、下の図のように1本辺を足すとまでのパスが4通り増えて必要なパスをすべてそろえることができます。
パスの数を足すには例えば6本足したいときには2本と4本()に分けてパスを追加することで過不足なくパスを増やすことができます。
最後に制約の確認をすると、
- 頂点は20個までなので、なので
- 辺は20個の頂点の時に、
となるので問題なさそうです。
やはり700点問題は難しいですね。
インターンシップでの課題を自分でも作ってみた
先日書いたインターンシップでの課題を自分も考えてみたの内容について、 考えてみたのだから実際に触れるものを作ろうということで簡単なものを作りました。 ちなみに細部がかなり手抜きですが、そこらへんは短時間で作ったのであしからず。
画面
できたものはこんな感じ。
予算と実績が入力できて、日別のグラフをクリックするとその日の詳細を見ることができます。 データベースへの保存の実装は省略。Reactを使って作ったのでデータはStateに保持するだけになっています。
Reactはチュートリアルをやったくらいだったのでちょうどいい練習になりました。
実際に作ってるときはReactよりもMaterial UIにてこずることが多かったです。(いまだによくわかってないところが残っている)
ちなみにかかった時間は7,8時間くらいだったと思います。
ソースはこちら → GitHub/money-manager-app
あとは何かの言語の練習のついでに裏側も作るかも…?
インターンシップでの課題を自分も考えてみた
インターンの内容
会社のインターンで学生にWebアプリケーションを作ってもらっています。
期間は2週間。形式としては数人でチームになって開発をしてもらう形です。
内容については、こちらからはテーマと最低限実装してほしい機能を与えてあとは自由に作ってくださいと伝えています。
フレームワークはSpring Bootを指定。自分はアドバイザーなので技術的な問題が発生したときや解決できないときにアドバイスをする立場です。
作ってもらっているもの
テーマは「お小遣いを管理するためのアプリケーション」
理由はいろいろありますが、学生がイメージしやすいものを作ってもらったほうが拡張機能を作りやすいのかなといった目的もあります。
(お小遣いを工数と読み替えると仕事でつかえるものになるかも?)
こちらから提示しているアプリケーションが満たすべき最低要件は、
- 予算を入力することができる
- 実績を入力することができる
- 予算と実績の差を見ることができる
の3つだけです。最低要件以外の、
- グラフやカレンダー
- ログイン機能
などは時間がある限りは好きに実装していいということになっています。
学生の中間発表を見て自分ならどう作るか少し考えてみた
数チームに分かれて作ってもらっていますが、どのチームも見た目が違って面白いです。 そこで自分が作るならどんな見た目にするか考えてみました。
考えて作ってみた画面設計がこれ(パワポ便利ですね)
大事にしたところは以下の3つ
- 画面遷移をしないで1画面に収める
- 予実の差を数値とグラフの両方で見ることができる
- ダッシュボードっぽい見た目
もう少し細かいものはGitHubにあげておきました → GitHub - money-manager-app/overview
Reactの練習ついでに後々作ってみようと思います