7K12 blog

猫でも分かるアルゴリズム解説

IQテスト💩

f:id:tkr987:20200304151337p:plain

https://not-522.appspot.com/contest/5683583224119296

虚無と言いつつ苦労したわけだが…(^^;

なんだこれIQテストか?糞ゲー いや自分の地頭力が💩なんだよな 萎える


A - Infinite Coins

f:id:tkr987:20200304151515p:plain

https://atcoder.jp/contests/abc088/submissions/10496614

う


 B - Card Game for Two

f:id:tkr987:20200304151721p:plain

https://atcoder.jp/contests/abc088/submissions/10496721s

^o^


 C - Takahashi's Information

f:id:tkr987:20200304151848p:plain

https://atcoder.jp/contests/abc088/submissions/10521964

IQテストか?

連立方程式に見えるが、C問題でガウスの消去法を使うとは思えないので、式変形が答えかと思って  a_{1} + b_{1} = c_{11} とか  a_{1} + b_{2} = c_{12} を永遠に眺めていたが、何も分からなかった。

何も分からなかったので、 3 * (a_{1} + a_{2} + a_{3} + b_{1} + b_{2} + b_{3}) = \sum c から少なくとも3の剰余が0なのは確定なので、3の剰余が0でなければNoというコードを書いて提出してみた。未証明だったので当然WAで詰んだ。

f:id:tkr987:20200304153714p:plain

とりあえず、 a_{1}を c_{11}未満の数にしてみると、 b_{1} = c_{11} - a_{1}で求まる。赤マス以外のマスに対して同様にしていくと a_{1}から b_{3}まで全て決まる。最後に赤マスが正しいかどうかチェックすると答えが得られる。

ちなみに、aやbは全ての整数を取れるので、 a_{1}=0として他のaやbを決めていってしまって良い。


D - Grid Repainting

f:id:tkr987:20200304155051p:plain

https://atcoder.jp/contests/abc088/submissions/10506996

C問題で萎えたのでD問題は寝てから解いた。

答え = H * W - グリッド上の最短経路 - 壁 - スタート地点

うしさんのライブラリをコピペしたら秒殺だった ^o^