金魚亭日常

読書,ガジェット,競技プログラミング

AtCoder

AtCoder ABC #089 D. Practical Skill Test

400点埋め Q が大きいので,前計算しておく. D が同じなので累積和を使う. AtCoder ABC #089 D. Practical Skill Test

AtCoder ABC #087 D. People on a Line

400点埋め 解説読んでもいまいちピンとこなかったので写経. AtCoder ABC #087 D. People on a Line

AtCoder AGC #028 A

x を Array にしたら RE になったので Hash で. AtCoder AGC 028 A

AtCoder ABC #085 D

400点埋め AtCoder ABC #085 D

AtCoder ABC #080 D Recording

400点埋め 最初問題を読み違えていたが,普通にループを回して間に合う. AtCoder ABC #080 D Recording

AtCoder ABC #079 D Wall

400点埋め この前書いた ダイクストラで AtCoder ABC #079 D

AtCoder ABC #071 D Coloring Dominoes

400点埋め AtCoder ABC #071 D

AtCoder ABC #110 D

AtCoder ABC #110 D

AtCoder ABC #110

C が解けなかった D は素因数分解やって組合せだろうな,というとこまでは考えたが… B のテストケースに問題があって Unrated になる可能性があるらしい. AtCoder ABC #110 C AtCoder ABC #110 B AtCoder ABC #110 A

AtCoder ABC #109

1054 -> 1011 C で詰まって終了 久しぶりに解説放送見て C D 解いたけど,やっぱりわかりやすい. A A * B が偶数なら "No" で 奇数なら "Yes" AtCoder ABC #109 A B Hash に突っ込んでやったけど,2重ループ回すのでも余裕で間に合うみたい. AtCoder ABC #…

AtCoder ABC #108

1015 -> 1054 A 偶数の個数と奇数の個数を数える. AtCoder ABC #108 A B 回転行列で. 45度回転させて √2 倍する. AtCoder ABC #108 B C a + b, b + c, c + a が kの倍数になるのは, a, b, c がkの倍数 a + b, b + c, c + a がkの倍数,つまり,a, b, c …

AtCoder ABC #090 D. Remainder Reminder

AtCoder ABC #090 D. Remainder Reminder

AtCoder ABC #090

順調に Rating が下がっているので,やはりD問題を解かないといけないな,と思った. AtCoder ABC #090

AtCoder AGC #021 A. Digit Sum 2

端以外は9で埋めてよさそうだったので,間に合う範囲で全探索した. AtCoder AGC #021 A. Digit Sum 2

ABC #088 解いた

C は直感で解いたので,間違っている可能性がある. D は 蟻本の幅有線探索を見た. AtCoder ABC #080 A. Infinite Coins AtCoder ABC #088 B. Card Game for Two AtCoder ABC #088 C. Takahashi's Information AtCoder ABC 088 D. Grid Repainting

Hack to the Future 2018 予選

最初 1 0 0 1 を出力するやつで,4,625,945,309 点 その後,例を眺めていて思いついたのが,最大値を見ていくやつで, Hack to the Future 2018 Qual で,963,334,4494 点 だった.

AtCoder ABC # 080 C. Shopping Street

要素数10の配列 各要素は 0 or 1 全部で 210 = 1024 通り この組み合わせを列挙して,各要素が0か1か知るには, # 1 << 10 は 1024 (左シフト) (1 << 10).times do |b| x = [] 10.times do |i| # 任意の桁数右シフトして 1 と AND をとる x << ((b >> i) &…

Weathernews Programming Competition (その 3)

次はハフマン符号してみた. かなり書くのが厳しかったが,とりあえず AC で,得点は 1692167.64 . 最下位脱出して 38 位. ハフマン符号 ver.(Rust)

Weathernews Programming Competition (その 2)

とりあえず Python でハフマン符号してみたら,速度的に無理そうだったので,Rust に移植することに. とりあえず,自明解を提出. 実行するときは --release を付けないと結構厳しい. 書き出すときは,数値は u8 にする必要があるので,自前で頑張っている…

AtCoder ABC #077

1185 -> 1172 C 二分探索するところまでは思いついたが,その後難しく考えすぎて解けなかった. B より大きいCの個数は毎回求めてたらTLEしたので,前計算する. AtCoder ABC #077

AtCoder ABC #076 D - AtCoder Express

AtCoder ABC #076 D - AtCoder Express

AtCoder ARC #049 B - 高橋ノルム君

B: 高橋ノルム君 - AtCoder Regular Contest 049 | AtCoder コストを固定して,二分探索. 何回するかがパッと思いつかないが, ぐらいなら 回ぐらいで十分らしい. AtCoder ARC #049 B - 高橋ノルム君

AtCoder ARC #047 B - 同一円周上

B: 同一円周上 - AtCoder Regular Contest 047 | AtCoder マンハッタン距離 => 45度回す AtCoder ARC #047 B - 同一円周上

AtCoder ARC 046 B - 石取り大作戦

B: 石取り大作戦 - AtCoder Regular Contest 046 | AtCoder AtCoder ARC 046 B - 石取り大作戦

AtCoder ARC #043 B - 最短路問題

B: 最短路問題 - AtCoder Regular Contest 044 | AtCoder 距離が同じもの同士は,ペアの選び方が なので, 通り 距離 から は ,距離 のそれぞれから 距離 のそれぞれについてつなぐ・つながない 二通りあって,全部つながないというのを除くので, 距離 が …

AtCoder ARC #043 B - 難易度

累積和 1回 にしたつもりが になっていて,TLEになった. AtCoder ARC #043 B - 難易度

AtCoder ARC #042 B - アリの高橋くん

頂点の座標が の三角形の面積 は (サラスの公式) なので,点を原点まで平行移動した後,面積を求めて, を底辺の長さで割ると辺までの距離が出る. AtCoder ARC #042 B - アリの高橋くん

AtCoder ARC #041 B - アメーバ

端の列を除いて,4近傍の最小値を取っていく. 値が決まったら,元の4近傍から値を引いておく. 解説は,上から順番に決めていく方式だった. AtCoder ARC #041 B - アメーバ

AtCoder ABC #075 D - Axis-Parallel Rectangle

最初,ユークリッド距離で近い順にK点選んで長方形を作る,ってやっていたけど,だめだった. x座標とy座標それぞれソートしてから長方形を全部作り,K点以上含まれるかどうか判定する. で,Ruby で書くとTLEだったので Rust. AtCoder ABC #075 D - Axis-P…

AtCoder ARC #040 B - 直線塗り

B: 直線塗り - AtCoder Regular Contest 040 | AtCoder 再帰でやると思ったが違っていた. AtCoder ARC #040 B - 直線塗り