CODE FESTIVAL 2015 予選A
結果：A,B,Cの3完．DはずっとN<100のケースを通す方法もお思いつかず1時間が経過し，直前で答えありきで順繰りにできるか確かめる方法と2分探索を思いつき，悔しい思いをしました・・予選Bは後悔のないようにしたい．
下はACした解答．
intにするとオーバーフローする計算があるので注意が必要．
yukicoder No.96
今回は初めて★4の問題に挑戦してみました．無論解法を確認しながらですが・・・
ほとんど丸1日かけてACまでこぎつけました．本当は★2~3で基本テクニックに慣れてから解く方が効率はいいのでしょうが，一回★4がどのくらいの難易度かみてみたかったので．これをプロ界隈は息を吐くように解くんですか!?!?
今回手に入れたテクニック
- mapのデータ構造．C#でdictionary使ったことあったのですがそれみたいな物ですかね．イテレータの扱いなどに慣れていなかったのもあって苦労しました(そして最終的には使うのをやめた)
- 凸包を求めるアルゴリズム．無論初見だったので凸包の例題をyukicoderで解いて下準備せざるをえなかった．アンドリューのアルゴリズムはこの本見ながら実装しました．
- Union-Findのデータ構造．これはAtCoderのATCで取り上げられていたのでそれで予習しました．ランクという概念は，意外なところで計算量の削減になっていてこれはまたどこかで出会いそうな予感．
テクニックを複合的に使う難しさを体感できてよかったです．また基本が定着するまでしばらくは★3埋めに集中します．
ABC029, TTPC2015
今回のABCは4完63分．D問題で時間がかかりかつ1WA出したのがもったいない．実装は時間がかかってしまったがyukicoderでこれより難しい問題をやっていたので安心して取り組めました．次回も全問正答，かつランキング1ページ目を目指したい．
昨日は東工大プログラミングコンテストがAtCoderで開かれるということで少し参加．盛大に寝坊してA,Bだけ解いて後はE見ながらボケーっとしてました．
事後参加でF,Gを解きました．4問解いた中ではGが印象的でしたね．
貪欲法はyukicoderで少し経験していましたが今回は同一の文字を含む文字列を部分列としてうまく抽出する問題．考え方がわかれば難しくないはずなんですが，色々な実装の穴をWAごとに見つける作業がすごく辛かった．最後テストケース1個だけWA残ったときはどうしようかと思った(103行目のbreakが抜けていました)．
それにしてもランキング上位を見ているとなんでそんなスピードで問題が解けるんだという驚きしか出てこない．
残りの問題(特にH以降)も時間を見つけて解こうと思います．オンサイト行ってみたい(初心者の感想)
yukicoder No.281
今回は初めてyukicoder主催のリアルタイムでコンテストに参加しました．
No.281が本当に問題児だった．始めは★2でしたがコンテスト中に難易度が★3に修正．
問題は門松列に似たような条件を満たすように3本並んだ竹を長さdづつ切っていって，条件が満たすように竹を切る回数の最小値を求める問題．
見かけ上場合分けの問題というのはすぐにわかるのですが様々なコーナーケース(というわけでもないけれど)に対応した実装をしなければならず，かといって時間中はテストケースの中身も見ることができないのでWA原因の特定が非常に大変．
全然通らなくて順位表みてましたがやっぱりこういう問題みんな苦労するものなんですね・・何かエレガントな解き方があるに違いない，と思いながらやってたらいつの間にか風呂入ってました．
結局時間オーバーで解けず，12WA出しながらなんとかAC．実装泥臭い．こういう類の問題はTopCoderとかCodeforcesでは本当に出ないでほしい・・
やはりテストケースが見れるyukicoderは実装初級者にはありがたいと感じた一問．
Codeforces #320 div2
Codeforces 2回目の参加．
まず結果
A,Bの2完．1581 -> 1533 (-48)
やはりCで間違いの原因がわからずWA*7を出してしまい，終了2分前に考えのミスに気づいてしまったのが響いてしまった・・・
A: 倍々ゲーム(ただし途中で何度でも1を足すことができる)．指定の数字を実現するのに必要な1は幾つかという問題．やり方は単純で1のbitが立っている数を数える．
B: 2n人が任意にペアを組んだ時の攻撃力が与えられ，最強の最強のn組の組み合わせを求める問題．単純に大きい攻撃力の組から順々に決めるのだが，priority_queueを使った(学びたてだから使いたくなった)からか実装はだいぶかかってしまった．たぶんこんなの使わなくても解けるんだろうなあ
C: (0, 0) – (x, x) – (2x, 0) – (3x, x) – (4x, 0) – ... - (2kx, 0) – (2kx + x, x) – ....を通るギザギザのグラフがあって，与えられた座標をそのグラフが通過するxの最小値を求める問題．間違いの原因はわかったものの具体的なアルゴリズムに関してはまだわからず・・正解者数的にあまり難易度は高くないと信じて時間がある時に通したい．おそらく2分探索を使うのだろうと思うけれど・・(勘)
実装の穴や発想の穴を見つけられないとどうしても時間がかかってしまう．大会に限らずyukicoderでも．うーんどうすればいいものか．いろいな人のソースコードを参考にさせて頂くときもあるのですが，なかなか意図を読み解くのも時間かかってしまいますね・・練習量と思考の深さ次第というところでしょうか
SRMもCFも不甲斐ない結果だったので，次はせめて上り坂にしたい．
yukicoder No.124
幅優先探索★3．かなり時間かかったけれど自力でACまで持っていけてかなり嬉しかった．
考え方：基本的には前いた場所と今の場所をセットで持っておいて，次行ける座標とキューの座標2つが門松列になっていればqueueにpushする．確認が終わったqueueの中身は確認ごとにpopする．ゴールについたか，行けるマスがなくなったらおしまい．かなり煩雑な実装になってしまった・・・
Codeforces事後報告は次の記事で．
SRM 668 Div2
いつも昼頃に起きる自分がSRMのために早起きしました
結果：1097 -> 1078 (-19)
結果は2完．前回より易しいセットなために前回の1完のときより相対的な出来は悪いという結果．
Easy: 文字列を入れ替える問題．特に問題なくできましたが時間がかかってしまった．
Medium: 整数座標が4つ与えられ，それが正方形をなすか答える問題．自分の解法はまず任意の3つの点(A,B,C)を選び，90度の角を見つける(ベクトルの内積で計算)．AB・AC=0かつAB=ACのとき，OA+AB+ACが残りの点の座標になるかどうかをチェック．これもなんだかんだで時間をかけてしまった．
Hard: int型の配列vが与えられ，そこから3つの整数a,b,cを適当にとったとき，与えられた整数Kで割り切れる組は何通りあるかという問題．next_combinationみたいなのがあればできたかも・・方針としてはgcd(v[i], K) for all iを計算したものに配列をアップデートし，そのあと3つの数字をかければ10^18以下なのでlong longでオーバーフローしない，というものを思いついたが，時間と実力が足りず実装まではできず・・
今回はコーディングの速さが課題となったラウンドでした．次はレート上げていきたい．
