notepad.exe

つまり覚え書き

windowsでもかっこいいCUI環境を作りたかった

Windowsコマンドプロンプトってよくわからないですよね? だからと言ってbash on Windowsインストールしても結局ウィンドウはWindowsのものなのでダサいですよね?

どうせなら少しでもかっこよくしようということで環境を作ったのでメモ

まずはbashを入れる

こちらの記事を参考にbashwindowsで使えるようにします。 これだけでbashは使えるようになるのでlsコマンドとかが使えるようになります。

Cドライブは /mnt/cにマウントされている状態なのでwindowsファイルシステムで管理されているファイルも普通にアクセスできます。

見た目をどうにかする

一番重要な見た目ですがcmderという素晴らしいソフトウェアがあるのでこれをダウンロードして使います。 初期状態だとcmd.exeが上がるようになってるのでbashが上がるようにします。

ついでに全画面にしたときに余計な部分が消えるように設定すると見た目をだいぶかっこよくできます。 設定方法はこちらのサイト

あとはzshにしたりtmuxいれたり

このあたりを見ながらbashではなくzshにしてtmuxとか入れると楽しくなります

(スクショはまだまだカスタム中なので省略)

ARC098/ABC098 D - Xor Sum 2

復習日記

問題ページ

問題概要

  • 長さ Nの整数列 Aが与えられる
  •  A_l xor A_{l+1} xor ... xor A_r = A_l + A_{l+1} + ... + A_rを満たす (l, r)の組の個数を求める

考え方

サンプルを見てみると、

  •  2 = 0 0 1 0
  •  5 = 0 1 0 1
  •  4 = 0 1 0 0
  •  6 = 0 1 1 0

となっていて、 (l, r) = (1, 2)の時にちょうど1の位置がお互いに干渉していないことがわかります。 例えば、1がどこかの桁に2つ以上あるときに xorをとると0になってしまいますが、加算をすると繰り上がって1の位置がずれてしまいます。
ということは、区間のすべての桁について1の個数が1個または0個になるような区間を求めれば答えを求めることができることがわかります。

というのが解説にもありますが、区間を尺取りで実際に計算しながら求めれば答えを求めるのには十分です。

提出コード

数える実装が上手くきれいに書けなくてサンプルがなかなか通らなかったです。 結局右側を順番に回して左側を詰めていく実装に落ち着きました。 あとほかの人の実装が頭よかったので参考にしました。

ABC109参加してない記録

本番は参加できませんでしたが解いてみた感じで書きます

A - ABC333

 A * B * Cが奇数になるCが存在するか確かめる問題

偶数に何をかけても偶数なので A * Bが偶数かどうかで判定

提出コード

B - Shiritori

しりとりが正しいか判定する問題

これは本当にやるだけ。出現済みかどうかはHashSet等で管理すれば楽だと思います。

提出コード

C

すべての都市を訪れることが可能な最大の移動距離を求める問題

 Dずつ移動するので移動距離は Dの倍数になります。  i番目と j番目の都市を移動するときの距離が必ず Dの倍数でないといけないので、 逆を言うとすべての都市の Xからの距離が Dの倍数であればどの順番であってもちょうどたどりつくことができます。
以上のことから、すべての都市の座標のXからの距離の最大公約数を求めると以上の条件に当てはまる最大の移動距離を求めることができることがわかります。

提出コード

D

指定された操作を行いコインが偶数枚置かれたマスを最大化する問題

マス目上の全てのコインを足したときに偶数枚であれば何らかの操作ですべてのマスのコインのマスを偶数枚にすることができると予想できます。 また、奇数枚であればどこか1か所を除いて偶数枚にすることができると予想できます。 ということはどこか一か所に向かってコインを集めるような操作をすればうまく偶数枚にすることができそうです。
実装として簡単なのは全体を横に移動してから端の縦を下に移動させる方法だと思います。

提出コード

ARC101/ABC107 D - Median of Medians

復習日記

解説その他諸々を見ながらやっていきます。

問題ページ

問題概要

  • 長さ Mの数列を昇順に並べたときの \frac{M}{2} + 1番目の要素の値を中央値とする
  • 長さNの数列の各 (l, r) (1 \leq l \leq r \leq N)について \{ a_{l}, a_{l+1}, ..., a_{r} \}の中央値を m_{l,r}と置く
  • すべての (l, r)に対しての m_{l,r}を集めた数列を作り、その数列の中央値を求める

考え方

まず、中央値について考え方を整理します。問題概要には中央値の定義は、

長さ Mの数列を昇順に並べたときの \frac{M}{2} + 1番目の要素の値を中央値とする

と書かれていますが、これを言い換えると、長さ Mの整数列 bの中央値を xとしたときに、

  •  bの中に x以上の要素が \lceil \frac{M}{2} \rceil個以上含まれる xの中で最大の整数

であるといえます。
この「条件 Pを満たすものの中で最大のもの」という考え方に注目すると二分探索で解くことができることがわかります。
これは連続部分列の中央値 m_{l,r}を並べた数列にも同様のことが言えて、最終的にこの問題は、

  •  m_{l,r} (1 \leq l \leq r \leq N) のうち x以上の要素は何個か?

という質問に置き換えることができます。
ここで m_{l,r} (1 \leq l \leq r \leq N)について言及するように言い換えると、

  •  a の連続部分列 a[l, r] (1 \leq l \leq r \leq N) のうち, x 以上の要素を \lceil \frac{r−l+1}{2}\rceil個以上含むものは何通りか?

という質問になります。

次に、この質問に対してどのような解法をとるかを考えます。
毎回数えてしまうと計算量が多く間に合いません。そこで xより大きい数を1 xより小さい数を-1に置き換えて累積和を取ります。 そうするとその区間の累積和が0以上であれば xより大きい数の個数が過半数であるということがわかります。
さらに言えば、 1から Mまでの累積和を取っておけば、

  •  m_{l,r} (1 \leq l \leq r \leq N) = m_{1,r} - m_{1,l}

と計算をすることで求めることができます。

最後に、区間の累積和が0以上である区間の個数を求める方法ですが、 S_i = \sum_{j=1}^{i}{a_{i}}としたときに、

  •  S_i \leq S_j (i \lt j)である (i, j)の組み合わせの個数

と言い換えることができます。これは反転数を求めるアルゴリズムを使うと高速に求めることができます。 反転数のアルゴリズムについては蟻本のp162または螺旋本のp175に載っています。

提出コード(諸々を写経)

かなり難しい700点ですね…
これを時間内に解くだけパフォーマンスが2000を超えるので、目標にしたいところです。

ABC108/ARC102 D - All Your Paths are Different Lengths

復習日記

700点問題はさすがに難しいので解説その他もろもろを見ながら解きました

問題ページ

問題概要

整数 Lが与えられるので以下の条件を満たすグラフを一つ出力。

  • 頂点が N以下で頂点の番号は 1 ~ Nまで
  • 辺数 Mが60以下で長さが  0 \leq M \leq 10^{6}
  • 辺は頂点の数字が小さいほうから大きいほうに引く
  • 頂点1から頂点 Nまでのパスがちょうど L個あり、各パスの長さが1 ~ L - 1まで

考え方

一つ目のサンプルが少しヒントになっていると感じました。 ポイントは長さ1でつながってるパスがあり、そのパスに対して長さ0の辺を引いているところ。 長さの順にパスを並べてみると、

  • [0, 0, 0, 0]
  • [0, 0, 0, 1]
  • [0, 0, 1, 1]
  • [0, 1, 1, 1]

というようになっていて、ここから2進数のように見える発想が出れば解法の半分までたどり着くことがで来そうです。
 N個の頂点に対して辺の長さを1だけでなくて 1, 2, 4, ... , 2^{N-1}と変えて同じように0の辺を作れば 1 ~ 2^{N-1}のパスを作ることができます。 f:id:mosmos_21:20180903173143p:plain

これで 2^{N}ちょうどの時なら作ることができました。 ここで例えば L = 12だとすると上の図では 8 ~ 11のパスが足りません。
この時に、下の図のように1本辺を足すと Nまでのパスが4通り増えて必要なパスをすべてそろえることができます。 f:id:mosmos_21:20180903195818p:plain

パスの数を足すには例えば6本足したいときには2本と4本( 2^{k}本)に分けてパスを追加することで過不足なくパスを増やすことができます。

最後に制約の確認をすると、

  • 頂点は20個までなので、 2^{20} - 1 = 1048575なので  L = 10^{6} \lt 2^{20} - 1
  • 辺は20個の頂点の時に、 19 * 2 + 19 = 57 \lt 60

となるので問題なさそうです。

提出コード

やはり700点問題は難しいですね。

インターンシップでの課題を自分でも作ってみた

先日書いたインターンシップでの課題を自分も考えてみたの内容について、 考えてみたのだから実際に触れるものを作ろうということで簡単なものを作りました。 ちなみに細部がかなり手抜きですが、そこらへんは短時間で作ったのであしからず。

画面

できたものはこんな感じ。 f:id:mosmos_21:20180830221249p:plain f:id:mosmos_21:20180830221408p:plain

予算と実績が入力できて、日別のグラフをクリックするとその日の詳細を見ることができます。 データベースへの保存の実装は省略。Reactを使って作ったのでデータはStateに保持するだけになっています。

Reactはチュートリアルをやったくらいだったのでちょうどいい練習になりました。
実際に作ってるときはReactよりもMaterial UIにてこずることが多かったです。(いまだによくわかってないところが残っている) ちなみにかかった時間は7,8時間くらいだったと思います。

ソースはこちら → GitHub/money-manager-app

あとは何かの言語の練習のついでに裏側も作るかも…?

インターンシップでの課題を自分も考えてみた

インターンの内容

会社のインターンで学生にWebアプリケーションを作ってもらっています。
期間は2週間。形式としては数人でチームになって開発をしてもらう形です。 内容については、こちらからはテーマと最低限実装してほしい機能を与えてあとは自由に作ってくださいと伝えています。
フレームワークはSpring Bootを指定。自分はアドバイザーなので技術的な問題が発生したときや解決できないときにアドバイスをする立場です。

作ってもらっているもの

テーマは「お小遣いを管理するためのアプリケーション」
理由はいろいろありますが、学生がイメージしやすいものを作ってもらったほうが拡張機能を作りやすいのかなといった目的もあります。 (お小遣いを工数と読み替えると仕事でつかえるものになるかも?)
こちらから提示しているアプリケーションが満たすべき最低要件は、

  • 予算を入力することができる
  • 実績を入力することができる
  • 予算と実績の差を見ることができる

の3つだけです。最低要件以外の、

  • グラフやカレンダー
  • ログイン機能

などは時間がある限りは好きに実装していいということになっています。

学生の中間発表を見て自分ならどう作るか少し考えてみた

数チームに分かれて作ってもらっていますが、どのチームも見た目が違って面白いです。 そこで自分が作るならどんな見た目にするか考えてみました。

考えて作ってみた画面設計がこれ(パワポ便利ですね) f:id:mosmos_21:20180827222944p:plain

大事にしたところは以下の3つ

  • 画面遷移をしないで1画面に収める
  • 予実の差を数値とグラフの両方で見ることができる
  • ダッシュボードっぽい見た目

もう少し細かいものはGitHubにあげておきました → GitHub - money-manager-app/overview

Reactの練習ついでに後々作ってみようと思います