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の練習ついでに後々作ってみようと思います
ARC099/ABC101 D - Snuke Numbers
復習日記
D - Snuke Numbers
整数に対して
を
の各桁の和とする
この時、に対して
を満たす
をすぬけ数と呼ぶ
が与えられるのですぬけ数を小さいほうから
個出力する
とりあえずサンプルを見ると1桁の時だけルールが違いそうなので2桁以上を考えてみる。
何となく手計算すると下の方は必ず9になるような気がする。
実際にすぬけ数となる数は1桁目から
(
の桁数)桁目まではすべて9になる。(証明は略)
ただ、dが何桁目なのかは実際に計算してみないとわからないので計算をする。
これを小さいほうから順番に探していけば時間内に答えを求めることができる。
この問題は解説を読んでも理解がふわふわしたままでした。 もう少しいろいろな問題を解いた後にもう一回解きなおします…
ABC106参加記録
相変わらずDが安定しないです。
A - Garden
畑の面積を求める
で終わり
B - 105
１からまでの正の整数で約数がちょうど8個ある奇数の個数を求める
が200までなので愚直に全部やれば間に合います。
C - To Infinity
1日たつと2が22、3が333みたいに増えるので5000兆日後の左からK文字目を求める
5000兆日後は1以外の数字がなんかすごいいっぱい並ぶので元の文字のK文字目までの中に1以外の数字があればそれが答え、
なければ1が答えになります。
D - AtCoder Express 2
列車の走る区間とクエリの区間が複数与えられる。 クエリで与えられた区間の中に走る区間がすべて含まれている列車の個数をそれぞれ調べる。
おそらく事前に累積和とかとっておくんだろうなと考えていましたがうまく実装できず…
累積和の取り方が区間]を走る電車の本数の二次元配列の横をとって、
クエリごとの解を求めるごとに横区間の和を出すやり方でも十分間に合いました。
2次元累積和はあとで実装しなおした時にやってみることにします。
ARC100/ABC102 D - Equal Cut
復習日記
D - Equal Cut
区間を区切った時の和の差が最小になるようにする問題
区間の和については累積和を持っておくことでとある区間の和は簡単に求めることができます。
この問題の答えを求めるときのポイントは真ん中を決め打ちしてから左右をそれぞれ求めるということ。
真ん中が決まってしまえば残りの半分はできるだけ均等に分ければいいのでで位置を求めることができる。
(例えばこれを極端にバランスを悪く切ってしまうとそこの差が大きくなってしまう)
これに加えて真ん中を左から右へずらすと残りの2カ所も必ず左から右へずれる。 この性質を使うと尺取り法で効率よく切る位置を求めることができる。
ここまでわかれば後は実際にシミュレートして最小値を求めることができる。
計算量はになります。
この問題は比較的実装が楽でした。
どこか1カ所を決めれば残りがで求められるので、シミュレートできる性質がこの問題に似ている気がします。
ABC062 C - Chocolate Bar
ABC105 D - Candy Distribution
復習日記
ABC105 D - Candy Distribution
均等に配れる飴の個数を取り出す組み合わせの総数を求める問題
最初に、制約から全パターンを試すのは無理(105 * 105)
ということはまずパターンをどうやって少なくするかだが、
これは1番目からi、j番目(i ≦ j)までの和をそれぞれとするとi番目からj番目の和は
とあらわすことができる。
そのため先に先頭から累積和をもとめておけばパターンを網羅する計算量を落とすことができる。
次に、がMで割り切ることができるのはどのようなときか求める。
当然、がどちらもMの倍数であれば割り切ることができる。
がMで割った時に1余る場合
がMで割って1余れば
がMで割り切ることができる。
つまりMで割った時にあまりが同じもの同士が
の組み合わせの候補となることがわかる。
このことから先に求めておいた累積和の配列を余りが同じ物ごとにまとめて数を数えたのち組み合わせを計算することで最終的な答えを求めることができる。
