Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-05-30

SRM441 Div1 Easy: PerfectPermutation

| 19:14 | SRM441 Div1 Easy: PerfectPermutation - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM441 Div1 Easy: PerfectPermutation - naoya_t@topcoder SRM441 Div1 Easy: PerfectPermutation - naoya_t@topcoder のブックマークコメント

Mediumを先に解いてたら分かったのかも・・・いや分からなかったかな

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090530

2009-05-28

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090528

2009-05-23

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090523

2009-05-22

SRM148 Div1 Medium: MNS

| 23:07 | SRM148 Div1 Medium: MNS - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM148 Div1 Medium: MNS - naoya_t@topcoder SRM148 Div1 Medium: MNS - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より。

Backtrackingで解く例(その2)。450点問題。

続きを読む

SRM232 Div1 Easy: WordFind

| 05:11 | SRM232 Div1 Easy: WordFind - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM232 Div1 Easy: WordFind - naoya_t@topcoder SRM232 Div1 Easy: WordFind - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Brute Forceで解く例(その4)。

続きを読む

SRM229 Div1 Easy: Cafeteria

| 04:51 | SRM229 Div1 Easy: Cafeteria - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM229 Div1 Easy: Cafeteria - naoya_t@topcoder SRM229 Div1 Easy: Cafeteria - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Brute Forceで解く例(その3)。

続きを読む

SRM212 Div2 Hard: LargestCircle

| 04:27 | SRM212 Div2 Hard: LargestCircle - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM212 Div2 Hard: LargestCircle - naoya_t@topcoder SRM212 Div2 Hard: LargestCircle - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Brute Forceで解く例(その2)。

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090522

2009-05-20

vectorで多次元配列を作る場合の初期化

| 02:19 | vectorで多次元配列を作る場合の初期化 - naoya_t@topcoder を含むブックマーク はてなブックマーク - vectorで多次元配列を作る場合の初期化 - naoya_t@topcoder vectorで多次元配列を作る場合の初期化 - naoya_t@topcoder のブックマークコメント

Multidimensional arrays are very important. The simplest way to create the two-dimensional array via vector is to create a vector of vectors.

vector< vector<int> > Matrix; 

It should be clear to you now how to create the two-dimensional vector of given size:

int N, M; 
// ... 
vector< vector<int> > Matrix(N, vector<int>(M, -1)); 

Here we create a matrix of size N*M and fill it with -1.

Power up C++ with the Standard Template Library: Part I - Algorithm Tutorials

知らなかった...

Abusing C++ Extensions for Fun and Profit

| 02:41 | Abusing C++ Extensions for Fun and Profit - naoya_t@topcoder を含むブックマーク はてなブックマーク - Abusing C++ Extensions for Fun and Profit - naoya_t@topcoder Abusing C++ Extensions for Fun and Profit - naoya_t@topcoder のブックマークコメント

http://www.topcoder.com/tc?module=Static&d1=features&d2=022006

Compound literals

I often define a small struct that will hold two or three items, such as the end-points and weight of an edge in a graph. For two-item structs there is already the utility pair template, but it has unfriendly field names (first and second compared to, say, target and cost), and it doesn't generalise well to more than two elements (although you can create a pair<pair<R, S>, T> if you really insist).


One advantage of pair that you lose when you do this is the make_pair function that creates pairs on the fly. You could of course define such a function for your class, or give it a constructor, but this can take vital coding time. GCC provides another alternative, which comes from C99: the compound literal. A compound literal is a mix between a cast and an initialiser. To understand what I mean, consider a struct defined as

struct edge
{
    int target;
    int cost;
};

An example of a compound literal is (edge) { t, c } where t and c are expressions. The values in the braces are used to initialise the values of the struct, in the order in which they are declared. This is useful for instantiating structs on-the-fly to pass to STL methods.

Comparisons

Although the header <algorithm> provides min and max functions, these have some limitations. They have only one template parameter, which specifies the type for both arguments; this sometimes leads to errors when the given arguments are of different types. GCC provides the highly non-standard operators ? (max), which will coerce the arguments to a suitable type.


These operators are most commonly seen in their assignment forms ?=. For example, the following loop computes the minimum value of a function over a range:

int m = INT_MAX;
for (int i = 0; i < N; i++)
    m <?= func(i);

これは見たことある

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090520

2009-05-18

SRM353 Div1 Easy: Glossary

| 14:19 | SRM353 Div1 Easy: Glossary - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM353 Div1 Easy: Glossary - naoya_t@topcoder SRM353 Div1 Easy: Glossary - naoya_t@topcoder のブックマークコメント

以前に見たことがある気がする(おそらくSRM前の準備運動がてら開いてみた)

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090518

2009-05-17

ログインしたらレーティングが+1して1501になってた

SRM222 Div1 Easy: GroceryBagger

| 17:49 | SRM222 Div1 Easy: GroceryBagger - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM222 Div1 Easy: GroceryBagger - naoya_t@topcoder SRM222 Div1 Easy: GroceryBagger - naoya_t@topcoder のブックマークコメント

Algorithm Tutorialsで同SRMのMedium問題が例に挙げられていたのだけれど、準備運動代わりにEasyを解いた。

  • unused codeの削除が足りず, save/compile/submit直前までを3回ループ。時間もったいない!
  • 243.89pt (4'30'')
  • 続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090517

2009-05-12

SRM440

22:39 | SRM440 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM440 - naoya_t@topcoder SRM440 - naoya_t@topcoder のブックマークコメント

05.12.2009

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090512

2009-05-05

SRM207 Div2 Hard: CaptureThemAll

| 21:05 | SRM207 Div2 Hard: CaptureThemAll - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM207 Div2 Hard: CaptureThemAll - naoya_t@topcoder SRM207 Div2 Hard: CaptureThemAll - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より

Problem hints: At first sight this may seem like dynamic programming or backtracking. But as always, take a look into the text of the statement. After a while you should observe the following things:

  • A table is given.
  • The knight can jump from one cell to some of its neighbors.
  • The cost of passing from a cell to another is always 1 (just one jump).
  • You need to find the minimum number of steps (jumps).

Given this information we can see that the problem can be easily solved by the help of BFS. Don't get confused by the fact that connected points are represented by unconnected cells. Think of cells as points in a graph, or states (whatever you want) - and in order to pass from one point to another, the knight should be able to jump from the first to the second point.

Notice again that the most revealing hint about the BFS solution is the cost of 1 for any jump.

「ジャンプのコストが全て1」→BFSで解けるよというあからさまなヒント

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090505

2009-05-01

SRM439

11:58 | SRM439 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM439 - naoya_t@topcoder SRM439 - naoya_t@topcoder のブックマークコメント

04.30+.2009

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090501