Hatena::Grouptopcoder

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

2013/08/03

天下一プログラマーコンテスト2013予選A

| 22:37 | はてなブックマーク - 天下一プログラマーコンテスト2013予選A - どせいふんとうき。

たまたま予定が合ったので参加しました.合計 110pt で 107 位でした.


A. 天下一株式会社採用情報: 20

計算するだけ問題でした.


B. 天下一難易度設定: 30

ループを回して集計するだけ問題でした.


C. 天下一二三パズル: 60

MxN マスを数字で埋めていく問題ですが 1 < M,N < 1e6 ということでループを回していたらまず解けません.しかしサイズの小さい問題だけでも解ければ部分点になるということで greedy にループを回して解きました.100x100 マスまでクリアしたので部分点をゲット.

どうやらパターンを見つけてどうにかする問題だったようです.


D. 天下一展開: 0

あと 10 秒早く submit していれば部分点 50 点もらえたのに q( ゚д゚)pブーブーブー

地道に内側から文字列を展開して行きましたが medium な入力に対してちょこちょこ TLE を出していたのでもう少し効率的にやる必要がありそうです.『構文解析してうごうごする』とできるらしいですがよくわかりません.


E. 天下一ジグソーパズル: 0

時間が足りなかったので問題分もほとんど読んでないです(;´Д`)


予選 B も予定が合えば参加しようかなーと思っています.

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

SRM 576

| 14:16 | はてなブックマーク - SRM 576 - どせいふんとうき。

日本時間だとお昼前の時間に開催でした.ちょっと危なかったのですがなんとか 2 問正当しました. Challenge は早とちりして失敗したため -25.00pt です…….レーティングは微増して 1005 -> 1061 になりました.

TheExperimentDiv2: 239.96

冷静にループを回せば難しくない問題でした.

ArcadeManao: 172.00

領域のサイズが小さかったので,配列を作って X にたどり着くために必要な最低のはしごの長さをどんどん更新していくことにしました.とりあえずテストケースを突破した所で投稿したのですが,コンテスト終了間際に自分のコードを撃墜する入力を思いついてしまったので急遽訂正.かなり汚いコードになりましたがなんとかシステムテストは突破しました.

CharacterBoard2: Opened

単純にループを回したら大変なことになるのかなぁ……とか思いつつ手を付けられずにいます.


Challenge: -25.00

誤爆しました(´;ω;`)


ArcadeManao の再提出に伴う減点が痛かったですが,まるごと 0 点になるよりはマシです.書きなおしがコンテスト終了までに間に合ってよかったです.設計をミスして無駄の多いコードになってしまったので反省しなければ…….

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/07

SRM 575

| 07:04 | はてなブックマーク - SRM 575 - どせいふんとうき。

500 点問題がシステムテスト弾かれたので解けたのは 1 問のみ.レーティングは前回からさらに下がって 1025 -> 1005 になりました.かろうじて 3 桁をキープ.ギリギリです.


TheSwapsDivTwo: 191.52

数列の任意の位置をひっくり返して異なる数列をいくつ作れるかという問題でした.場合分けに自信がなかったのでじっくり考えてしまいました.点数低めです.

TheNumberGameDivTwo: Failed System Test

数取りゲームです.ある数 n からその約数を引いていき,引けなくなった時点でその人の負になります.DP を使って解けばさほど難しくない問題だったのですが,問題をちょっと勘違いして解いてしまったので Failed System Test をいただきました.

確認はしていませんが,僕のコードは入力に 30 を与えれば落ちたはずです.

TheTilesDivTwo: Opened

与えられたチェッカーボードに L 字型のボードを最大でいくつ載せられるかという問題でした.深さ優先探索で解けると思ったのですが,時間オーバーでシステムテストを突破できていません.探索に無駄があるようです.


前回がひどい結果だったのでリベンジのつもりだったのですが,前回とはさほど変わらない結果になってしまいました.他の人のコードを参考にしつつ,勉強を続けていきます(´;ω;`)