2020-08-01から1ヶ月間の記事一覧
2020-08 をふりかえる。 2020-08 の目標 ☑ リングフィットアドベンチャーを続ける ☑ 『プログラミングコンテストチャレンジブック』 初級編を読む ☑ Rust で小さいものをつくる 週別のふりかえり 2020-W31 2020-W32 2020-W33 2020-W34 2020-W35 つくったもの…
2020-W35 をふりかえる。 2020-W35 の目標 とその記事 目標。 ☑ 『デザインの輪郭』を読む ☐ 『合格る確率+場合の数』を読む 記事。 2020-08-29 ARC036 A, B 2020-08-28 ARC031 A, B 2020-08-27 ARC023 A, B 考察 2020-08-26 AtCoder Petrozavodsk Contest 0…
ARC036 A, B 考察 arc036 A - ぐっすり 前から走査する。最後までなければ -1 。 https://atcoder.jp/contests/arc036/submissions/16291212 arc036 B - 山のデータ N <= 3 * 10^5 なので二重以上のループで調べることはできない。数字が大きくなっていると…
ARC031 A, B 考察 arc031 A - 名前 回文判定。前からと後ろから 1 文字ずつ一致していることを確認していく。回文の判定では奇数の中央は無視できるので 0..n / 2 の範囲を前から走査で良い。 https://atcoder.jp/contests/arc031/submissions/16270964 arc0…
ARC023 A, B 考察 arc023 A - 経過日数 指示通りのプログラムを書く。日数計算は 2 回出てくるので関数化すると良さそう。 1 月 2 月を 13 月 14 月と読み替えたときに前年に戻すのを忘れていて入力例がなかなか通らなかった。 https://atcoder.jp/contests/…
AtCoder Petrozavodsk Contest 001 A, B, C 考察 apc001 A - Two Integers X が Y の倍数だと条件は満たせないので -1 。そうでない場合はたぶんある (未証明) 。 X + X から X ずつ大きくして Y で割り切れるかを確認していけば良い。 https://atcoder.jp/c…
CODE FESTIVAL 2014 決勝 A, B, C, D, E 考察 code-festival-2014-final A - 50 m 走 50 m の秒数 s が与えられるので平均の秒速を求める。 1 秒あたりの距離が秒速なので 50 / s で求める。絶対誤差・相対誤差の意味はよく分からない 10^(-3) の誤差なので …
天下一プログラマーコンテスト 2012 予選 C A, B 考察 tenka1-2012-qualC A - 与えられた数より小さい素数の個数について N 未満の素数の個数を求める。エラトステネスのふるいを使って素数のリストとその要素数を求めた。 https://atcoder.jp/contests/tenk…
2020-W34 をふりかえる。 2020-W34 の目標 とその記事 目標。 ☐ bouzuya/rust-memo 0.2.0 をつくる 記事。 2020-08-22 AGC011 A, B 2020-08-21 AGC034 A, B 2020-08-20 ARC053 A, B, C 2020-08-19 ABC048 A, B, C 2020-08-18 ABC084 / かんぺぴ 2020-08-17 A…
AGC011 A, B 考察 AGC011 A - Airport Bus バスの数を最小にしたいので各バスに乗せられるだけ乗せるようにすると良さそうだ。 T_i + K まで出発を遅延させてその時点で到着している人を乗れるだけ乗せるという貪欲法で解けそう。証明はできないけどおそらく…
AGC034 A, B 考察 AGC034 A - Kenken Race 基本的には A → C と B → D の間に 2 個連続する '#' があると No になる。 C < D のときはふぬけ君 (B 側) を先に移動してからすぬけ君 (A 側) を移動すれば何も起きない。 D < C のときはどこかですぬけ君 (A 側)…
ARC053 A, B, C 考察 ARC053 A - ドミノ色塗り 横 2 マス縦 1 マスを考えると (W - 1) * H 個。縦 2 マス横 1 マスを考えると (H - 1) * W 個。合計して (W - 1) * H + (H - 1) * W を求める。 https://atcoder.jp/contests/arc053/submissions/16052774 ARC…
ABC048 A, B, C 考察 ABC048 A - AtCoder *** Contest 入力からある位置の一文字を取り出して A{}C に整形して出力する。 https://atcoder.jp/contests/abc048/submissions/16035582 ABC048 B - Between a and b ... 0 <= a <= b <= 10^18 なので a..=b を 1…
ABC084 考察 ABC084 A - New Year 12 月 31 日の 24 時間と 12 月 30 日の M 時以降の (24 - M) 時間を足した 24 + (24 - M) を求める。 https://atcoder.jp/contests/abc084/submissions/16012834 ABC084 B - Postal Code 先頭から A 文字までは数字 A + 1 …
ABC036 A, B, C 考察 ABC036 A - お茶 B / A の切り上げを求めれば良い。 / が Rust では切り捨てで動作するので (B + (A - 1)) / A として切り上げた値を求める。 切り上げは頻出テクニックなので覚えている。 https://atcoder.jp/contests/abc036/submissi…
2020-W33 をふりかえる。 2020-W33 の目標 とその記事 目標。 ☑ bouzuya/rust-memo v0.1.0 をつくる ☑ ABC174 を解く ☑ 『融けるデザイン』を読む 記事。 2020-08-15 Tenka1 Programmer Beginner Contest / 『融けるデザイン』 2020-08-14 AGC023 A / 『とな…
Tenka1 Programmer Beginner Contest A, B, C 考察 tenka1_2018 A - Measure 指示通りに判定して操作する。長さを見て 3 なら逆順にする。 https://atcoder.jp/contests/tenka1-2018-beginner/submissions/15894665 tenka1_2018 B - Exchange K <= 100 と小…
AGC023 A 考察 AGC023 A - Zero-Sum Ranges 解説 AC 。 考えたこと。先頭と末尾の位置を決めてその間の和が 0 になる個数なので O(N^2) で良いなら累積和をとって二重ループで OK 。ただし N <= 2 * 10^5 なので今回は間に合わない。ここまでで諦めた。 解説…
AGC032 A 考察 AGC032 A - Limited Insertion 解説 AC 。……なんだけど解説を見てもよく分からなかった。おおまかに言うと完成形である b から逆順にたどって構築できるかを確認する。 b を操作によって構築可能な文字列と仮定する。そのとき i 番目が i にな…
AGC005 A 考察 AGC005 A - STring ST を取り除く操作を 10^1000 回する。 X <= 2*10^5 なので全部取り除くに十分な回数という意味だ。 ST になる並びは SSSSTTTT のような並び。逆にならないのは TTTTSSSS のような並び。 S のあとに T が出てきたらそれ以前…
ABC174 A, B, C, D, E 考察 ABC174 A - Air Conditioner 30 度以上なら Yes そうでなければ No 。 https://atcoder.jp/contests/abc174/submissions/15818075 ABC174 B - Distance それぞれの点について原点からの距離が D 以下であるかを調べれば良い。N <=…
ABC109 A, B, C, D 考察 ABC109 A - ABC333 A * B * C が奇数になるかを確かめる。 1 <= C <= 3 なのですべてを試せば良い。 https://atcoder.jp/contests/abc109/submissions/15797289 ABC109 B - Shiritori ひとつ前の末尾の文字と先頭の文字が一致するこ…
2020-W32 をふりかえる。 2020-W32 の目標 とその記事 目標。 ☑ 『プログラミングコンテストチャレンジブック』(初級編) を読む ☐ ABC174 を解く 記事。 2020-08-08 AGC043 A / bouzuya/rust-memo / 『 FACTFULNESS 』 2020-08-07 AGC016 A 2020-08-06 CADDi…
AGC043 A 考察 AGC043 A - Range Flip Find Route 解説 AC 。もうすこし考えれば解けそうだったけど考えるのが面倒になってしまったよ……。 縦か横に連続している場合は反転が 1 回で済むので連続する # は 1 回の反転になることは分かった。適当に書いたら間…
AGC016 A 考察 AGC016 A - Shrinking 入力例 1 の serval の各文字の数値から挙動を考える。 s: serval → serva → serv → ser → se → s e: serval → eerva → eerv → eer → ee r: serval → srrva → rrrv → rrr v: serval → sevva → svvv → vvv a: serval → se…
CADDi 2018 C, D 考察 CADDi 2018 C - Product and GCD 解説 AC 。 考えたこと。 N, P <= 10^12 なので前から順に求めるのは難しそうだ。かけて P になる数だし 10^12 という制約からおそらく素因数分解する (O(√P)) 。 gcd(a_i, a_{i+1}) を最大化するには……
ABC024 A, B, C 考察 ABC024 A - 動物園 合計人数 (S + T) が K 以上なら S * (A - C) + T * (B - C) を K 未満なら S * A + T * B の入場料になる。 https://atcoder.jp/contests/abc024/submissions/15708840 ABC024 B - 自動ドア ある人が来てから最長で …
ARC004 A, B 考察 ARC004 A - 2 点間距離の最大値 ( The longest distance ) N <= 100 なので O(N^2) ですべての線分を列挙できるので全探索する。 https://atcoder.jp/contests/arc004/submissions/15679723 ARC004 B - 2 点間距離の最大と最小 ( Maximum a…
diverta 2019 Programming Contest 2 A, B 考察 diverta2019-2 A - Ball Distribution K = 1 のときは 0 。 K > 1 のときはそれぞれに 1 個ずつ配って残りを誰かひとりに配れば良い。多い人: N - (K - 1) 個 少ない人: 1 個になる。差は N - (K - 1) - 1 = N…
2020-W31 をふりかえる。 2020-W31 の目標 とその記事 目標。 ☑ 『 RDRA2.0 ハンドブック』を読む ☐ 『プログラミングコンテストチャレンジブック』(初級編) を読む ☑ 2020-07 をふりかえる 記事。 2020-08-01 ARC010 A, B 2020-07-31 2020-07 ふりかえり 20…
