ICPCオフ会3日目

USAGI Codeによるセット．なんとなくhosさんらしい問題が並ぶ．

開始(10:00)

問題文を読む．問題文は短いのですぐに読める… けど，やっぱり難しそうなものが多い．cosさんらがAが重いけどできると言っているのでAを進める．
僕はEが貪欲で解けそうな気がしたのでEを考える．交互にいろいろ進める．Aが通る．

A Accepted(10:37)

Eを適当に実装する．貪欲にする基準は(倒すのにかかるターン数)×(敵から受ける攻撃)でいい? (間違ってる)
投げる．WA．ギョ．

cosさんがFができそうと言っているので交代する．Eをまじめに考える．隣り合う項同士を比較すると… あれ，比でいいんでは．でもなんかちょっと自信ない．
cosさんがFを投げるがTLEを喰らう．Eをソートする基準だけ書き直してsubmit．WA．あれー? うーむ，わからない．放置．

しょうがないのでBでDPを組む．大体こんなんでいいんじゃない? 送る，WA．
N=1のときputs("1");とかしてる… 直す，WA．
1回もジャンプできないときに1を吐いてる… 直す，AC．

B Accepted(12:10 +2)

cosさんがFを進める．Jが解かれているのでJを見てみる．ふむふむ，なんか簡単そう．
適当にアルゴリズムを考える．cosさんがFを通す．

F Accepted(12:39 +1)

Jを進める．途中，斜めの判定でx%(N-1)のような式が出てくる．あれ，N=1の場合ってそういえばどうなるんだろう．もしかしてコーナーケース? これは危ない…．
できたので送る．WA．あれ? 考える．N==1の場合弾いてなかった，送る．AC．

J Accepted(13:02 +1)

なんか解けそうなのがなくなってきた!!
3人でHについて考える．チケットの数字でかいから貪欲でいいんじゃね? a==1とかの場合が怖いけどそこは場合わけすればなんとかなるんでは，とか．

cosさんにコードを任せてCを考える．なんか思いつけば数式一発っぽいんだけども…．1次元でベクトルが2本の場合は適当にgcdとればいいだけなので簡単．2次元でベクトルが1本しかない場合も簡単．じゃあ両方マージした場合は?
…なんとなーく群っぽい構造が浮かんできそうな気もするけど分からない．うーむ．

Hが書きあがったとのことなのでsubmit．WA．ウボァ．
よく考える．cosさんが，片方が1でもう片方が1でない場合は貪欲にできないといっている? うーん，そうなのだろうか…
オーバーフローの検出とかがだめっぽかったので直す．WA．

cosさんが全探索にしても貪欲っぽくなるからよいのでは，と言っている．なぜそれでいいのか分からなかったけどそれでもいいかなぁと思ったのでそうする．書けた．WA．
デバッグを一緒にやる．適当なケースを作って実行すると明らかにおかしい結果が出る．なんだってー!!
あれ，REPマクロでlong longがintにキャストされてるけどこれはまずいのでは…? 直す．AC．

H Accepted(14:25 +3)

解ける問題が無い… やべぇ．Eはなんか怖いので放置している．Cをずっと考えていたけど，最後まで分からなかった．終了．

結果

5ACで3位．Eはほとんど合っていたけど，勝負が終わらない場合で-1を返していたのがまずかったらしい…．うーむ，なんか惜しい．
問題文に違和感を感じたら「たぶん設問者のミスだろう」とか思わないでクラを投げるようにしたほうがいいのかな．

Cは群論のLagrangeの定理を使うとスムーズに解けるらしい．難しい．
Dはクエリを平方分割すると良いそうです．cosさんとnojimaさんがFree Solving Sessionで通していました．
Iは誰も解いていなかったけど，勝利できる領域が凸六角形になるので上手い具合にやればできるのだとか．
Gは手をつけないほうがいいそうです．