Hatena::Grouptopcoder

どせいふんとうき。 RSSフィード

2013/05/30

Round #186

| 05:47 | はてなブックマーク - Round #186 - どせいふんとうき。

ふらっと参加しました.結果は ooo-- でレーティングは 1621 -> 1698 へと上昇しました.前半 3 問を素早く解けたことがよかったようで初めてのルーム 1 位,全体では 103 位につくことができました.


A. Ilya and Bank Account: 492

3 パターンの残高をすべて計算して最大値を出力しました.下 2 桁目を落とすのには以下の式を使いました.

int chomped_num = (num/100)*10 + num%10

B. Ilya and Queries: 952

l から r までループを回すことは避けたいところです.そこで cumulative な配列を作って cum[l-1]-cum[r-1] を出力しました.

C. Ilya and Matrix: 1302

大きい順に整列したあと cumulative な配列を作って

for (int i=1; i<=n; i=(i<<2)) score += cum[i-1];

こんな感じでスコアを計算しました.

D. Ilya and Roads: ---

DP でやるのだろうなということは分かったのですがうまい設計が思いつかず…….

E. Ilya and Two Numbers: ---

うまい方法が見つからず結局 TLE のコードしか書けませんでした.むーん.


A, B, C は解けましたがワンランク上に進むためには D, E を解けるようになりたいところです.次回もレーティングを上げて色を変えられるといいなぁー.

2013/05/12

Round #183

| 01:02 | はてなブックマーク - Round #183 - どせいふんとうき。

久しぶりに参加しました.結果は ooo-- でレーティングは 1607 -> 1621 に微増しました.もう一問くらいは解けそうでした.


A. Pythagorean Theorem II: 464

下から順当にループを回して解きました.無駄な計算を省けば時間内に収まります.

B. Calendar: 410

せいぜい数万回ループすれば終わるので1日ずつコマを進めていきました.それぞれの月が何日含んでいるのかがわからなくなって調べたのは許してください.

C. Lucky Permutation Triple: 708

0 1 2 3 4
1 2 3 4 0
1 3 0 2 4

常にこんなのを生成するプログラムを提出したら解けてしまいました.n が 2 の倍数のときは解がなく,それ以外のときはこの方法で常に解けるようなんですが確認はしていません.

D. Rectangle Puzzle II: ---

最初に最大となる長方形の幅と高さを求めて収まるようにシフトする……という方針で解けました.しかし計算の符合が一箇所間違っており,デバッグを時間内に終えることができませんでした.ちょっと悔しいです.

E. Minimum Modular: ---

終了後にチラッと見ただけで全然手をつけていません.

2013/04/12

Round #179

| 14:02 | はてなブックマーク - Round #179 - どせいふんとうき。

参加しました.結果は o-o-- で Div2 での順位は 164 位でした.おかげさまでレーティングも 1449 -> 1607 にアップして Expert に戻ってきました.


A. Yaroslav and Permutations: 486

数の多いものから順に 1 つ飛ばしにして入れていけばいいですね.数の 1 番多い要素だけに注目すればいいようです.

B. Yaroslav and Two Strings: ---

余事象を考えればそれほど難しくない問題でした.残念.

C. Greg and Array: 1266

問題を見た瞬間ピキーンときました.これでやった内容がまるごと応用できます.進研ゼミでやった内容がそのままテストに出たときの生徒の気分が理解できたような気がします.

D. Greg and Graph: ---

行列のサイズも小さいですし,ダイクストラ法で都度最短距離を作成してコストの合計を出力していけばいけるような気がします.ダイクストラ法の練習として後日チャレンジすることにします.

E. Greg and Friends: ---

人の数をインデックスにした DP で解けるでしょうか.時間オーバーになりそうな気もします.要検討.


成績としてはそれほど悪くなかったですが B を解けなかったのがちょっと悔しいです.余事象に注目して条件が簡単な方で計算するなんてすごい基礎的な内容なのに…….肝に銘じておきます.

2013/04/02

Round #177

| 04:19 | はてなブックマーク - Round #177 - どせいふんとうき。

成績は o-o-- で 807 位でした.レーティングは 1511 -> 1449 に変動しました.前回せっかくランクアップしたのですが早々に Specialist へと逆戻りです.


A. Polo the Penguin and Segments: 484

しばらく問題の意味がわからずぽけーっとしていました.計算するだけでした.

B. Polo the Penguin and Matrix: ---

3分探索で解ける!とひらめいたところまでは良かったのですが時間内にきちんと実装できず……くやしいです.

C. Polo the Penguin and Strings: 1092

最初は abab... を繰り返しておいて最後に cdef... と登っていけば解けるかな?と思ったら本当に解けました.キッタナイ場合分けをしました.

D. Polo the Penguin and Houses: ---

終了後に「1..k の部分は 1 を根とする全域木に一本足せば良いのでは?」とひらめきました.頂点の数が k の最小全域木の数は k^(k-2) だそうなので,その通りに実装したら Accepted をもらいました.

E. Polo the Penguin and XOR operation: ---

まだ読んでないです.


成績は悪かったですがコンテスト終了後わりと早い段階で解けなかった B, D 問題が解けたのはよかったです.次回以降のコンテストに活かしていきたいです.

April Fools Day Contest 2013

| 04:07 | はてなブックマーク - April Fools Day Contest 2013  - どせいふんとうき。

せっかくなので参加しました.ちゃっかり 411 位をゲットしました.


A. Mysterious strings: Accepted

Google 先生に相談→あとはタイピング.

B. QR code: Accepted

あー. QR コード読み込んだら目的のデータファイルダウンロードできるとか気づかなかったわー.気づかなかったわー.(´;ω;`)

C. WTF?: Accepted

ネットスラングなんでしょうか.

D. Orange: Accepted

イラストを見ながらコードに落とすだけ.

E. HQ: ---

アライグマさんがきらいになる問題.

F. Greedy Petya: ---

問題を読んで速攻であきらめました.まさかコンテスト中に解けた人がいたなんて…….

2013/03/14

Round #173

| 10:37 | はてなブックマーク - Round #173 - どせいふんとうき。

今回で 4 回目の参加です.結果は o-o-- の 2 完で 1712 点でした.C 問題を解いたおかげかレーティングは 1422 -> 1511 と上昇して Specialist から Expert にクラスチェンジしました.


A. Bit++: 494

"++X", "X++", "--X", "X--" の 4 パターンしか入力がないので場合分けしました.

B. Painting Eggs: ---

問題文をよく理解できないまま終わってしまいました.

Practice で解いてみました.まず何も考えずに A, G のうち数が少ない方だけを選択します.A, G のつけた値段の合計値は常に 1000 なので A->G または G->A に変更した場合,値段の差 (Sa-Sg) は常に 1000 だけ動きます.ということで差の絶対値が 500 以下になるまで選択を変更していけばいつか答えに辿り着きます.

C. XOR and OR: 1218

手を動かして色々と試してみたところ bit の立っている数が 0 か 1 以上かに注目するだけで解けそうだと予想できました.実際テストもパスしたので間違ってはいないと思います.

D. Yet Another Number Game: ---

数字が 2 つの場合は後者が勝つことのできる組み合わせはかなり限られることがわかりました.では数字が 3 つの場合は……と手を動かしているうちにタイムオーバーでした.

E. Sausage Maximization: ---

読んでないっす:(;゙゚'ω゚'):


3 問完答を目指したいところです!