bouzuya.hatenablog.com

ぼうずやのにっき

ABC012

ABC012 考察

abc012 A - スワップ

A B の入力を受けて B A で出力する。

https://atcoder.jp/contests/abc012/submissions/16581487

abc012 B - 入浴時間

秒を時分秒に直す。 n % 60 が秒。 (n / 60) % 60 が分。 (n / 60) / 60 が時。あとはゼロ埋め 2 桁で出力する。

https://atcoder.jp/contests/abc012/submissions/16581547

abc012 C - 九九足し算

まず九九の総和を求める。そこから N を引く。その数と一致する数を 1 * 1, 1 * 2, ... 9 * 9 まで 2 重ループで走査して出力する。

https://atcoder.jp/contests/abc012/submissions/16581626

abc012 D - バスと避けられない運命

問題文が分かりづらい。頂点が N 辺が M の重み付き無向グラフがある。各頂点について他の頂点への最短距離を求めてそれらの最大のものを求める。それらのうち最小のものを求める。

ワーシャルフロイドかダイクストラか。どちらでもだいたい O(N^3) くらいのはずなので N <= 300 だし間に合うはず。ぼくはダイクストラ法で解いた。

https://atcoder.jp/contests/abc012/submissions/16581872

リングフィットアドベンチャーを続けている。

『リトル・マーメイド』を観た。

AGC038 A

AGC038 A 考察

agc038 A - 01 Matrix

解説 AC 。

解説参照。入力例を変形して整理するとそうなるっぽい……けど分からなかった。

https://atcoder.jp/contests/agc038/submissions/16553186

リングフィットアドベンチャーを続けている。ワールド 15 。まだ少なくとも上に 2 ワールドは見えている。

MyBatis と Spring Boot の間に居る。

http://mybatis.org/spring-boot-starter/mybatis-spring-boot-autoconfigure/ とかそのへん。

2020-W36 ふりかえり

2020-W36 をふりかえる。

2020-W36 の目標 とその記事

目標。

  • ☑ 『ずうのめ人形』を読む

記事。

つくったもの

よんだもの

みたもの

なし。

その他

勉強会。なし。

おでかけ。なし。

ゲーム。リングフィットアドベンチャーを続けている。

買い物。なし。

体調。睡眠時間が安定していない。

育児。「おとうさんが〜」という形で話すことがある。氷を喜んで食べている。

AtCoder 。 AtCoder Problems の Recommendation を解く取り組みを続けている。 Longest Streak が途切れてしまった。 Recommendation の 1 問手前で止まった。 ARC で解いていたのだけど実は過去に ABC で解いていたらしく途切れた。気にしても仕方ないので続けていく。

『ずうのめ人形』・『ししりばの家』・『などらきの首』を読んだ。

2020-W37 の目標

  • 『ユースケース駆動開発実践ガイド』を読み進める
  • Corne Chocolate をつくる
  • rust-memo v0.3.0 の Issue をつくる

全国統一プログラミング王決定戦予選 A, B, C / 『ししりばの家』・『などらきの首』

全国統一プログラミング王決定戦予選 A, B, C 考察

nikkei2019-qual A - Subscribers

両方を読んでいる数の最大は A と B の小さいもの。最小は A を読んでいない人に最大限 B を割り当ててはみでた分 (B - (N - A) = A + B - N) で 0 以上の範囲のもの。

Rust で usize で確保しているとマイナスになると RE になるので注意する (saturating_sub を使える)。

https://atcoder.jp/contests/nikkei2019-qual/submissions/16516372

nikkei2019-qual B - Touitsu

先頭から順に 3 つの文字列の同じ位置の文字を比較する。 3 文字が同じなら +0 で 2 文字が同じなら +1 そうでないなら +2 。最後まで走査すれば求まる。 N <= 100 なので O(N) で間に合う。

https://atcoder.jp/contests/nikkei2019-qual/submissions/16516517

A より解きやすく感じた。

nikkei2019-qual C - Different Strokes

証明なし。 A 側だと考えたとき自分を大きくしたいので A_i のなるべく大きいものを選びたいし相手を小さくしたい (大きいものを取らせたくない) ので B_i のなるべく大きいものを取ると良さそうだ。 A_i + B_i の降順で並び替えてあとは指示通りのシミュレーションすると良い。ソート部分が O(NlogN) で N <= 10^5 なので間に合う。

https://atcoder.jp/contests/nikkei2019-qual/submissions/16516743

『ししりばの家』・『などらきの首』を読んだ。

リングフィットアドベンチャーを続けている。

ARC034 A, B

ARC034 A, B 考察

arc034 A - 首席

N <= 3049 なので指示通りに走査・計算して最大値を求めて問題ない。

https://atcoder.jp/contests/arc034/submissions/16496243

arc034 B - 方程式

N <= 10^18 なので x を 1 から順に N まで走査すると間に合わない。ヒントを探す。

x = 10^18 に近い最大の f(x) を考えると 9 が 17 個並ぶ。 9 * 17 = 153 。 1 <= f(x) <= 153 であることがわかる。それを踏まえて x + f(x) = N を考えると x からせいぜい 153 増えた範囲に N がないといけない。この範囲なら全探索で十分に間に合う。

最初はせいぜい 3 桁程度だろうと N の近くの 1000 件ほど探索したのだけど範囲を誤っており 1 WA した。

https://atcoder.jp/contests/arc034/submissions/16505849

リングフィットアドベンチャーを続けている。

AGC014 A, B / 『ずうのめ人形』

AGC014 A, B 考察

agc014 A - Cookie Exchanges

未証明 AC 。パッと見だと A, B, C <= 10^9 なので指示通りのシミュレーションはまずそうに見える。ただ足して 2 で割る操作を繰り返すので差 (?) がなだらか (?) になる時間計算量は O(logN) になりそうだ。無限ループになる条件は全部が偶数で操作を繰り返しているのでどれもほとんど同じ値になっているはずだ。交互に値を入れ替わって……というのはなさそうだ。前の値と同じなら無限ループだと思って良さそう。

上記の推測から指示通りにシミュレーションして AC 。解説によると最大と最小の差が 1/2 になっていくらしい。それを繰り返すのだから O(logN) 。無限ループになるのは全部が同じ値のときらしい。

https://atcoder.jp/contests/agc014/submissions/16477949

agc014 B - Unplanned Queries

解説 AC 。未証明なら可能性はあるけど……。これが緑とは……難しい。

r を根とする根付き木を考えると a <-> b のパスは a -> r と r -> b と解釈して良い。根を通るときはもちろんそうでないときも偶奇の判定だけなので問題ない。あとは a の出現回数と b の出現回数が偶数になっていれば YES そうでなければ NO になる。奇数のときダメな理由としては奇数のうちもっとも深い頂点とその手前の頂点の間の辺は奇数回になってしまうから。

https://atcoder.jp/contests/agc014/submissions/16487996

『ずうのめ人形』を読んだ。面白かったよ。

リングフィットアドベンチャーを続けている。

Tenka1 Programmer Contest C

Tenka1 Programmer Contest C 考察

tenka1-2017 C - 4/N

n, h, w <= 3500 なので全探索すると 10^9 を超えてしまい間に合わない。そこで n と h について全探索し w は 4/N=1/h+1/n+1/w を変形することで求める。

ここまではすぐ発想できたのだけど変に割り算を残してしまい 4 WA した。割り算は避けよう。

https://atcoder.jp/contests/tenka1-2017/submissions/16467763

リングフィットアドベンチャーを続けている。

毎日のように考えなくてもいいことを考えているような気がする。一歩引いて広く見よう。