問題の感想・メモ - 1日9時間寝たい

24問解きました(ググりました)。番号だけ書いてあるのはAOJの問題です。

がんばったもの
0005 0207 0281 0307 0515 0516 0545 0555 0577 0621 ABC035C
ググったもの
0030 0168 0179 0181 0285 0535 0539 0556 0557 0558 0560 0579 ABC026D

以下感想・ネタバレです。

１．AOJ0005 GCD and LCM | Aizu Online Judge
　最大公約数(GCD)と最小公倍数(LCM)を求めました。GCDを求める際にはユークリッドの互除法を使わないとTLEすると思います。a, bのLCM(a, b)を求める際にLCM(a, b) = a*b/GCD(a, b);とするとオーバー風呂?してWAになるので、(a/GCD)*bなどとしました。ちょっといじわるですね。

２．AOJ0030 整数の和 | Aizu Online Judge
　0から9までの数字を重複なしに $n$ 個選んでその和を $k$ にできる組み合わせが何通りあるかを求めました。深さ優先探索(DFS)らしいです。全く分からなかったので以下の記事を参考にしました。

初心者歓迎詐欺被害者の会: AOJ 0030 c

３．AOJ0168 Kannondou | Aizu Online Judge
　階段の上り方が何通りあるかを求めました。フィボナッチみたいな簡単なDPでしたが、分からず。参考にしたのは以下の記事です。 d.hatena.ne.jp

４．AOJ0179 Mysterious Worm | Aizu Online Judge
　ある規則に従って体節の色が時間変化する芋虫がいて、その芋虫のすべての体節が同じ色になるまでの最短時間を求めました。幅優先探索(BFS)らしいです。やはり、全く分からなかったので以下の記事を大変参考にしました。 d.hatena.ne.jp

５．AOJ0181 Persistence | Aizu Online Judge
　段数?が固定された本棚に、厚さの異なる本を順番に入れることができるような本棚の幅の最小値を求めました。二分探索(BS)らしいです。よく分からなかったので以下の記事を参考にしました。1冊で本棚の幅を超えるような厚さの本がやって来るケースの処理が甘かったです。 d.hatena.ne.jp

６．AOJ0207 Block | Aizu Online Judge
　盤面の各マスに色がついていて、スタートからゴールまで到達する経路において通過するマスの色を1種類だけですむ経路が存在するかどうかを求めました。BFSしました。DFSのほうがラクに書けるらしいですが、分かりません。スタート位置が壁（障害物）になっているケースに気をつけました。具体的には、探索をせずにNGを出力すればよいです。

７．AOJ0281 Formation | Aizu Online Judge
　3人1組のチームをできるだけたくさん作りました。No.91 赤、緑、青の石 - yukicoderを解いたことがあったのでなんとかなりました。greedyにチームを作っていきましたが、本当にこれでチーム数を最大化できるかどうかの証明は分かりません。

８．AOJ0285 Tennis | Aizu Online Judge
　試合の勝敗の数が与えられるので、そこに至るまでの勝ち負けの順番としてあり得るものを全て求めました。DFSらしいです。全く分からなかったのでAOJで他の方の提出を参考にしました。問題文に図が与えられているのでありがたかったです。たとえば、5-0→5-1に遷移しないように気をつけました。

９．AOJ0307 ニッシン館マラソン部 | Aizu Online Judge
　最低限用意しなければいけない給水の容器を求めました。 $t$ 秒目に給水所に容器を置いたら、 $t+1\leadsto T$ 秒目まで容器を取ることができるようにしました。 $O(T^2N)$ と思っていたけど、TLEしなかったので違うのかもしれません。そもそも、もっと良い方法があるのかも。

１０．AOJ0515 School Road | Aizu Online Judge
　碁盤の目状の道路で2つの地点を結ぶ経路の場合の数を求めました。ただし、通過できない交差点がいくつかあります。DPらしいです。通行止めの交差点の処理も難しいものではありませんでした。しかし、問題での座標の取り方がいじわるでした。

１１．AOJ0516 Maximum Sum | Aizu Online Judge 　数列の連続した $k$ 個の数字の和の最大値を求めました。累積和です。こわいので、配列はちょっと多めに取っておきます。累積和でなくても、1個足して1個引いていく方法でも良いらしいです。

１２．AOJ0535 Crossing Black Ice | Aizu Online Judge
　できるだけたくさん氷を割りました。BFSらしいです。全く分からなかったので以下の記事を大変参考にしました。一旦氷を割っておいて探索が終わったら元に戻すテクが使われていました。 lepton.hatenablog.jp

１３．AOJ0539 Pizza | Aizu Online Judge
　できるだけはやくピザを届けました。にぶたんらしいです。やはり、全く分からなかったので以下の記事を大変参考にしました。ただし、lower_boundは使わず普通ににぶたんしました。両端に番兵を置きました。 d.hatena.ne.jp

１４．AOJ0545 Party | Aizu Online Judge
　自分からの距離が1または2の節点の個数を求めました。ワーシャルフロイドしました。ワーシャルフロイド禁止されると、解けません。

１５．AOJ0555 Ring | Aizu Online Judge 　環状の文字列に部分文字列が含まれるかどうかを求めました。文字列の後ろから同じ文字列をくっつけて、環状を実現しました。

１６．AOJ0556 Tile | Aizu Online Judge
　規則に従って3色に塗られている盤面で座標が与えられるので、その座標に対応する色を求めました。規則性を式で表せませんでした。参考にしたのは以下の記事です。t=min(x,y) の部分は、タイルを更に2分の1にしているのだと思います。 d.hatena.ne.jp

１７．AOJ0557 A First Grader | Aizu Online Judge
　数字の間に+または-を入れていき等式を成り立たせるとき、+、-の入れ方の場合の数を求めました。ただし、計算途中で0を下回ったり20を上回ったりするものは除きます。DPらしいです。全く分からなかったので以下の記事を大変参考にしました。 d.hatena.ne.jp

１８．AOJ0558 Cheese | Aizu Online Judge
　スタートからゴールまで、指定された地点を経由しながら到達する最短経路を求めました。BFSらしいです。よく分からなかったので以下の記事を大変参考にしました。問題の読み替えができていませんでした。 taku-k.hatenablog.com

１９．AOJ0560 Planetary Exploration | Aizu Online Judge
　長方形領域に含まれる各文字の個数を求めました。2次元の累積和?らしいです。参考にしたのは以下の記事です。 be-a-prgrmr.hatenablog.com

２０．AOJ0577 Unique number | Aizu Online Judge
　他の人が言っていない数字を言っている人にその数字の分だけ得点が入るゲームで、それぞれの人の獲得する得点を求めました。ちょっと険しかったです。配列の縦と横入れ替えてごにょごにょしましたが、上手いやり方があるのかもしれません。https://ideone.com/gJpTTn

２１．AOJ0579 Hot days | Aizu Online Judge
　数列の階差の絶対値の和の最大値を求めました。ただし、各項に使える数字には制限があります。DPらしいです。よく分からなかったので以下の記事を大変参考にしました。 mmxsrup.hatenablog.com

２２．AOJ0621 Russian Flag | Aizu Online Judge
　盤面が与えられるので規則に従って各マスの色を塗っていくとき、元の色と違う色を塗らなければならないようなマスの個数を求めました。全探索しました。具体的には、塗り分けの境目を1つずつずらしていきました。

２３．ABC026D D: 高橋君ボール1号 - AtCoder Beginner Contest 026 | AtCoder
　関数 $f(t)=A\times t+ B\times \sin(C\times t\times \pi)$ において $A, B, C$ が与えられるので $f(t)=100$ となる $t$ を一つ求めました。にぶたんらしいです。ちょっと分からなかったので公式の解説スライドを見ました。coutで出力するとダメみたいなのでおとなしくprintfを使いました。

AtCoder Beginner Contest 026 解説 from AtCoder Inc.

www.slideshare.net

２４．ABC035C C: オセロ - AtCoder Beginner Contest 035 | AtCoder
　オセロの駒が一列に並べられていて、区間を指定してその区間に含まれる駒を全てひっくり返す操作を何度かするので、すべての操作が終了した後の盤面の状態を求めました。ただし、はじめすべての駒は黒を上にしておいてあります。これは既に解いたことがあったのでなんとかなりました。いもす法には感動しました。やはり、こわいので配列はちょっと多めにとっておきました。

おまけ

開催されたコンテストの問題も少し解きました。

A: 天下一プログラマーゲーム - 天下一プログラマーコンテスト2016予選A | AtCoder

#include<iostream>
 
using namespace std;
 
int ans=0;
int TenPro(int n){
    if(n==101) return ans;
    if(n%3!=0&&n%5!=0) ans+=n;
    TenPro(++n);
}
 
int main(){
 
    cout<< TenPro(1)<< endl;
 
    return 0;
}

B問題は、末端のほうからPackDropをつけていって上のほうにずらしていけばいいと思いました。解説見たら、だいたい合ってそうですが実装はできません。

AtCoder Grand Contest 002
- A: Range Product - AtCoder Grand Contest 002 | AtCoder
  $a\leq b$ の条件に注意するとif(ここ)がちょっと簡単になります。条件がないときは、適当にswapすればいいと思います。
- B: Box and Ball - AtCoder Grand Contest 002 | AtCoder
  ちょっとややこしかったですが、なんとかAC。mapとかを使いました。赤色のボールが入った箱からボールを移動させるとき、移動先の箱に赤色のボールを入れて、かつ、元の箱にも赤色のボールが残るとみなしていいと思います(!?!?)。ただし、元の箱にボールが1つだけ(赤が1つだけ)のときは、もちろん元の箱に赤色のボールが残るとはみなせません。