CODE THANKS FESTIVAL 2014B日程オープンコンテスト感想

今日は研究をお休みにして、CODE THANKS FESTIVAL 2014B日程の問題を解いてました。

 

問題はこちら

Welcome to code thanks festival 2014 B日程(オープンコンテスト) - code thanks festival 2014 B日程(オープンコンテスト) | AtCoder

 

A問題 朝食

2つの数字の入力を受け取って大きい方の数を出力する問題。

 

 

B問題 電卓ゲーム

3つの数を様々な計算をして、一番大きかったものを出力する問題。

配列に入れて計算をした後、ソートして出力。

4通りしか計算手法がなかったので、そのまま書いてしまいましたがあんまりよくないとは思います()

 

 

C問題 人気投票ゲーム

数を2つ受け取って、過半数とれてればOKなもの。

2で割ったものよりも大きければいいのでそのまま割って比較、小数点は無視できる。

 

D問題 足ゲーム

一番無駄に頭使った問題かもしれません()

最初、最小公倍数でどうこうすればいいんじゃないかとか考えたんですがわけがわからなくなって、途中で時間を1ずつ増やして、与えられたボタンの時間で割ってあまりが0なら数えるって手法をとりました。

 

 

E問題 マスゲーム

座標を受け取って、指定されたとおりに色を塗って後は幅優先探索

スタートが黒じゃない時を設定するのを忘れて最初WAを出しましたが、直したら全部通りました。

 

F問題 太鼓ゲーム

高校の時の数学を思い出すような問題。

愚直に全部足し合わせようかとも思いましたがさすがに厳しいと判断

再帰的に求められないか(部分文字列から部分文字列を生み出すのは何通りか)

→DPで解けないか。

でなんとか解けました。

こちらも中途半端にWA出しててバグ取りが大変でしたが、

計算途中でオーバーフローしてしまうため、計算するたびに指定された数のあまりを計算するようにしたらいけました。

 

 

G問題 石取りゲーム

こちらもDPで解けそうな気はしましたが、そもそも慣れていないため実装にかなりの時間がかかりました。

特に座標のやりとりでx座標、y座標がごっちゃごっちゃになってしまって意味不明な座標の状態になってしまってました。

xをこれから取れる石の数

yをのこりの石の数として

考え方としては

1.取れる石の数が残りの石を超えている場合は確実に勝てるのでその座標には1を代入

2.残り数、取れる数が少ない座標から考える。

2-1そこからどこの座標、状態に移ることができるかを考える。

2-2その移れる座標では次の人が負けが確定するかどうかを見る。

2-3次の人の負けが確定する場合、その状態に動けるように石を取ればいいので、

  その場所では勝ちが確定する。座標のデータに1を代入する。

2-4 次の人の負けが確定しなかった場合、自分は勝てないため、-1を代入する。

といったものを考えていって、最終的に指定された座標のデータからどっちが勝つかを出力すれば解けました。

 

 

H問題はまだやってませんがそのうちやってみたいと思います。