bouzuya.hatenablog.com

ぼうずやのにっき

CODE FESTIVAL 2017 qual A A, B, C

CODE FESTIVAL 2017 qual A A, B, C 考察

code-festival-2017-quala A - Snuke's favorite YAKINIKU

S が YAKI からはじまるかを調べれば良い。 Rust なら starts_with がある。

https://atcoder.jp/contests/code-festival-2017-quala/submissions/17090719

code-festival-2017-quala B - fLIP

N, M <= 10^3 なので O(NM) で選択する行と列を 1 ずつ増やして全探索すれば良い。反転するので行と列の両方で選ばれたマスは白になる点に注意する (入力例のおかげで気づくことができる) 。

0..=N 0..=M のように N M を含みそびれていて 2 WA 。

https://atcoder.jp/contests/code-festival-2017-quala/submissions/17090773

code-festival-2017-quala C - Palindromic Matrix

1x1 から 4x4 くらいまでを実際に書いて確かめつつ各パターンをカバーできるように実装した。

まず各文字と個数を数える。これを BinaryHeap で個数の大きいものから順に取り出して個数を減らして戻すを繰り返していく。

偶数 x 偶数の場合は 4 ずつ減らして最後までいけるなら OK 。

偶数 x 奇数 (または奇数 x 偶数) の場合は奇数側の 1 行 (列) を残してほかは 4 ずつ減らす。これで偶数 x 1 (または 1 x 偶数) になる。あとは 2 ずつ減らして最後まで (1 残るものは無視) いけるなら OK 。

奇数 x 奇数の場合はさらに 3 つに分けられる。

1 x 1 の場合は OK 。

1 x 奇数 (奇数 x1) の場合は 2 ずつ減らして最後まで (1 残るものは無視) いけるなら OK 。

奇数 x 奇数の場合は中央を通る縦横 1 行・ 1 列を残した他のマス分だけ 4 ずつ減らす。あとは 2 ずつ減らして最後まで (1 残るものは無視) いけるなら OK 。

https://atcoder.jp/contests/code-festival-2017-quala/submissions/17101282

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

AGC003 A, B

AGC003 A, B 考察

agc003 A - Wanna go back home

移動量は調節できるので東西・南北のそれぞれで 1 以上のペアまたは 0 のペアをつくれるなら家に戻れる。逆に言うと東西・南北のいずれかで 1 以上と 0 のペアになってしまうと家に戻れない。

https://atcoder.jp/contests/agc003/submissions/17079316

agc003 B - Simplified mahjong

解説 AC 。問題文を読み間違えていた。「同じカードが複数のペアに使われないように」を「同じ整数が複数のペアに使われないように」だと勘違いしていた。

誤った解答の「同じ整数が複数のペアに使われないように」で考えると各ペアを使ったか使っていないかを調べて使っていれば次の要素ではペアとして使えない。そういう DP で解けたと思う (たぶん) 。

正しい解答は同じカードを複数回使わなければ良いので先頭から貪欲にペアをつくっていくだけ。途中 A_i が 0 のところでペアをつくれなかったカードが残ってしまう。それ以外はすべてペアになる。

https://atcoder.jp/contests/agc003/submissions/17085812

仕事中に体を伸ばしたら首をひねってしまったらしい。寝違えたみたいになっている。

あとはなんだか寒気がする。

2020-W39 ふりかえり

2020-W39 をふりかえる。

2020-W39 の目標 とその記事

目標。

記事。

つくったもの

(なし)

よんだもの

(なし)

一応『ユースケース駆動開発実践ガイド』をざっとは読んだ。

みたもの

その他

勉強会。なし。

おでかけ。なし。

ゲーム。『ポケモンスナップ』をクリアした。リングフィットアドベンチャーを続けている。 100 日を超えた。

買い物。 SwitchBot Hub Mini を買った。

体調。連休明けで疲れた。

育児。ズボンを自分ではけるようになっている。となりのトトロにはまっているようで毎日のようにトトロトトロとうったえてくる。週に 3 回は観ている。(2020-09-26)

先週の模様替えからの流れで押し入れを片付けた。もっと物を減らしたほうがいいか……。

AtCoder 。 ACL Beginner Contest に参加した。連敗を止めてレートが微増した。 ac-library-rs の Segtree をぼくの使える状態にした。スキル的な問題で実際に使えるかは分からない。 AtCoder Problems によるとぼくの解いていない緑 diff の問題はあと 20 問ある。 1 日 1 問で 20 日……。解いていく。

SwitchBot カーテンを設定した (2020-09-24) 。 Google Assistant 経由での操作のために SwitchBot Hub Mini を買って設定した。しばらく試す。

『ユースケース駆動開発実践ガイド』はきちんと読んだとは言い難いので改めて読みたい。

ある考えごとに土日のうち半日以上をつかっている。まだしっくりこない。

2020-W40 の目標

押し入れを片付けた

押し入れの片付けをした。要らないものを捨てるとすっきりする。

ACL Beginner Contest に参加した。微増だけど早解きによるもので不満がある。

CODE FESTIVAL 2015 あさぷろ Middle の A, B を解いた。 LCS の長さの求め方を忘れて困った。

育児。ズボンを自分ではけるようになっている。となりのトトロにはまっているようで毎日のようにトトロトトロとうったえてくる。週に 3 回は観ている。

ARC035 A, B, C / リングフィットアドベンチャー 100 日目

ARC035 A, B, C 考察

arc035 A - 高橋くんと回文

前からと後ろからで 1 文字ずつ走査する。両方の文字が一致せず両方とも * でないものがあればそれは NO それ以外は YES 。

https://atcoder.jp/contests/arc035/submissions/16994978

arc035 B - アットコーダー王国のコンテスト事情

早く解けるものから順に解けばコンテストペナルティは最小になる。同じ時間で解けるものがあるときその並び替えの数だけ解き方がある。 BTreeMap で昇順に並べつつ個数を数える。現在の時刻とコンテストペナルティの合計を計算して最小値を求める。問題の時間ごとに 10^9 + 7 で剰余を取りつつ個数の階乗を求めてそれらをかけ合わせて解き方の数を求める。

https://atcoder.jp/contests/arc035/submissions/16995039

arc035 C - アットコーダー王国の交通事情

N 個の頂点と M 個の辺の無向グラフがある。各頂点間の最短距離の合計を S とする。 K 個の辺を追加するときそれぞれの S を求める。……という問題。

初期の各頂点間の最短距離はダイクストラ法などで O(N(N+M)logN) で求められる。 N <= 400 M <= 1000 なのでこれなら間に合う。ただこれを K 回の辺の追加ごとにやると K <= 400 なので間に合わない。

そこで初期の各頂点間の最短距離と X_i Y_i Z_i (1 <= i <= K) を使う。各頂点間の距離 (j から k の距離とする) を j から X_i までの距離と Z_i と Y_i から k までの距離で短くなるなら更新する。これによって K 回の O(N^2) で各頂点間の最短距離の合計を求められる。これだと間に合う。

https://atcoder.jp/contests/arc035/submissions/16995686

リングフィットアドベンチャー 100 日目 ワールド 16 レベル 159 。

SwitchBot カーテンで不快な思いをした / ABC094

SwitchBot カーテンが届いた。

いろいろ購入前の説明をきちんと読めていなくて不快な思いをした。

まず箱のシールがイマイチなのと箱がキツキツになっていて開けにくかった。レールにはめるとマイナスドライバーなしに外せる気がしない。外さないと充電できないのでイライラした。

【片開き＆両開きカーテンに対応】

片開きはもちろん、両開きカーテンにも対応可能です。付属のクリップをカーテンにとめれば、 本来両開きのカーテンを片側開きのカーテンとして使うこともできます。

※両開き状態には SwitchBot カーテン２台が必要です。

この説明から見出しと最後の※部分だけを読んで「両開きには 2 個必要なのだ」と勘違いして 2 個買ってしまった。ただでさえ高いのに 2 台も。

タッチアンドゴーは壊れそうで使える気がしなかった。設置位置が普通にズレるんだけどこれでいいのか……ってなる。数回試してオフにした。

SwitchBot Hub Mini を買わなかったので Google Assistant との連携ができなくてがっかりした。あとから確認したら商品詳細に「併用すると」と確かに書いてあった。商品名が「 SwitchBot スイッチボット カーテン スマートホーム アレクサ - Google Home IFTTT イフト Siri LINE Clova に対応 自動開閉 遠隔操作 取付簡単 充電可能 U 型/角型レールに対応 」とあるから単体で連携できるものと勘違いした。

SwitchBot Hub Mini を注文した。

ABC094 考察

abc094 A - Cats and Dogs

A <= X <= A + B なら YES そうでなければ NO 。

最初 A <= X <= B と間違えて 1 WA 。

https://atcoder.jp/contests/abc094/submissions/16980369

abc094 B - Toll Gates

N <= 100 と小さいので N + 1 の領域を取って M 個の料金所を記録したあと X から 0 への方向と N への方向の両方を試せば良い。

https://atcoder.jp/contests/abc094/submissions/16990737

abc094 C - Many Medians

中央値は 0-based で N / 2 - 1 と N / 2 のどちらかになる。並び替えたときに N / 2 未満なら N / 2 側の中央値そうでなければ N / 2 - 1 側になる。最初の位置と組にして A_i で並び替える。並び替え後の位置でそのときの中央値と最初の位置を組にする。最初の位置で並び替えて各中央値を出力すれば良い。

https://atcoder.jp/contests/abc094/submissions/16991040

abc094 D - Binomial Coefficients

解説 AC 。 nCr の n は大きいほうが良いだろうとは思ったけど r を n / 2 にどれだけ近いかで選ぶという発想が出てこなかった。

https://atcoder.jp/contests/abc094/submissions/16991505

キーエンス プログラミング コンテスト 2020 A, B, C

キーエンス プログラミング コンテスト 2020 A, B, C 考察

keyence2020 A - Painting

ペイント操作は少ないほうが良いので 1 回の操作で塗れるマスが多い方が良い。行か列の大きい側を選んで塗る。これが 1 回の操作で塗れるマス数になる。その単位で塗って N を超えるのに何回かかるかなので割って切り上げれば良い。 (N + MAX(H, W) - 1) / MAX(H, W) で求まる。

https://atcoder.jp/contests/keyence2020/submissions/16974316

keyence2020 B - Robot Arms

最初に思いついたのはロボットの手を広げた状態でロボットごとに重なる個数を調べて 2 個以上になったものを取り除く方法。この方法だと O(N^2) になるので間に合わない。

重なっているかを調べるには広げた手の位置で並べたときに隣り合っているものを調べれば良い。左手の位置で並べて前のロボットの右手より左に左手があるなら重なっている。どちらを取り除くべきかはより右手の位置が右にあるほうだ。そのほうが次の要素が重なりにくくなる。どちらを取り除くにせよカウントは 1 増える。最後は全体の個数から取り除いた個数を引けば答えになる。

ソートと貪欲法で O(NlogN) になる。

https://atcoder.jp/contests/keyence2020/submissions/16975491

keyence2020 C - Subarray Sum

解説 AC 。解説を読むとかんたんだと分かる。もう頭が回っていなかった。

l = r が許されているので各要素を S にし K 個並べれば良い。残りの箇所で S がつくれないようにすれば答えになる。 S < 10^9 なら S+1 で S = 10^9 なら 1 などにすると N 個並べても S がつくれない。

https://atcoder.jp/contests/keyence2020/submissions/16975701

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