Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-06-29

[][] Project Euler Problem 119 08:49 はてなブックマーク -  Project Euler Problem 119 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=119

要約

 正数で,各桁の数を足し合わせて出来た数を何乗かするともとの正数にもどるようなもののうち,30番目に小さいもののを求めよ.例えば,81は 8 + 1 = 9で,9**2 == 81なので,81は条件を満たす(実は81はこのような条件を満たす最小の数).

続きを読む

2011-06-28

[][] Project Euler Problem 114 08:25 はてなブックマーク -  Project Euler Problem 114 - 練習帳

1週間はさすがにさぼりすぎました,反省します.

問題文

 http://projecteuler.net/index.php?section=problems&id=114

要約

 1 * 50の長方形のマスに様々な長さのタイルを敷いて行く.タイルの大きさは1 * n (n = 3, 4, 5・・・)で,タイル同士は1以上の整数分だけ離れてなければならない.また,タイルを1枚も敷かない場合も1通りと数える.タイルの並べ方の場合の数を求めよ.

 例えば,長さが50ではなく7ならば,次の17通り

■■■□□□□ ■■■□■■■ □■■■□□□ □□■■■□□ □□□■■■□ □□□□■■■ 
■■■■□□□ □■■■■□□ □□■■■■□ □□□■■■■ ■■■■■□□ □■■■■■□ 
□□■■■■■ ■■■■■■□ □■■■■■■ □■■■■■■ □□□□□□□ 
方針

 一番左にあるタイルの位置(左端,右端)で場合分けする.長さNのでの場合の数をf(N)とすると,大雑把には

f(N) = Σ_{0 <= i < j <= 50} f(50 - j - 1)

というような形になる.これを修正して,正しい答えを求めていく.

Σを取る範囲は最も左端にあるタイルが[i, j]の範囲にある事を想定している.タイルの長さは3以上なので,jの取る範囲は i + 3<= j <= 50なければならない.また,j = 49, 50の時はf(0)やf(-1)などの値が式の中に現れる.これの値はいくつとすべきか.これらの場合はタイルが右端から1個ずれてるか(49) or 右端にぴったり重なっているかである.これらも1通りに数えないとならないので,f(0) = f(-1) = 1とする.最後に,今までの話はタイルが1つ以上敷かれている事を前提としている(fの定義がそもそもそうなっている)ので,タイルを1枚も敷き詰めていない場合も含める.結局,

f(N) = Σ_{(i, j) 0 <= i <= 50, i + 3 <= j <= 50} f(50 - j - 1) + 1

が得られる.

コード例(python
N = 50
memo = [-1] * (N + 1)

def dp(n):
    if memo[n] >= 0 :  return memo[n]
    if n <= 0 : return 1
    memo[n] =  sum([dp(n - j - 1) for i in xrange(0, n)  for j in xrange(i + 3, n + 1)]) + 1
    return memo[n]

print dp(N) 

2011-06-22

[][] Codeforces Beta Round #75 Div. 2 D. Queue 09:32 はてなブックマーク -  Codeforces Beta Round #75 Div. 2 D. Queue - 練習帳

問題文:http://codeforces.ru/problemset/problem/92/D

要約

 n人の人が縦一列に並んでいる.i番目の人はa[i]歳で,自分のよりも真に若い人が前(この場合は番号が大きい方が前)に並んでいると不満を言う.その不満の大きさは数値化すると,「自分より前にいる中で最も若い人」と「自分」の間にいる人の数に等しい.ただし,自分より前の人がすべて自分と同年齢or年上の時は不満の大きさは-1とする.それぞれの人の不満の大きさを答えよ.nは2以上10**5以下.それぞれの人の年齢a[i]は1歳以上10**9歳(!)以下.

方針

 ナイーブに全探索を行ったらもちろんO(n**2)で計算量的に間に合わない.そこで,過去に使った情報を再利用できないかを考える,今回で言えば i < j < kについて,j番目の人とk番目の人の大小関係はj番目の人より前での最小年齢の計算だけでなくi番目より前での計算にも使える.ここでは,それを[i, n]の最小値を求める事で利用している(完全にeditorial読んだのでこんな天下り的な事を言っています).

 mns[i]を[i, n]での最小値とすれば,mns[i]はiについて単調増加なので,2分探索でa[i]の入る位置を求められる.その入る位置とiとの距離-2(i番目の人と最小年齢の人を除いている)が求める答え.

分析

 前にこれに似た問題(特定の区間の最小値を求める)にstd::setを使った記憶があって,これもそうに違いないと思い込んでいたのが失敗でした.editorialにある,[i, n]の最小値はiについて単調減少に気づければ,二分探索でプラスマイナス1の差に悶絶しながらも解けはしたような気がします.

コード例
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <climits>

using namespace std;

typedef long long ll;

int inf = INT_MAX;

int main(){
  int n;
  while(cin >> n){
    vector<int> a(n);
    for(int i = 0;i < n;i++){
      cin >> a[i];
    }
    vector<int> ans(n);
    vector<int> mns(n);
    vector<int> pos(n);
    int mn = inf;
    for(int i = n-1;i >= 0;i--){
      if(mn > a[i]){
	pos[i] = i;
	mn = a[i];
      }else{
	pos[i] = pos[i+1];
      }
      mns[i] = mn;
      if(i == n-1){
	ans[i] = -1;
      }else{
	int p = lower_bound(mns.begin() + i, mns.end(), a[i]) - mns.begin();
	int dist = p - i - 2; 
	ans[i] = dist >= 0 ? dist : -1; 
      }
    }
    for(int i = 0;i < n;i++){
      cout << ans[i] << " " ;
    }
    cout << endl;

  }
}

2011-06-21

Codeforces Beta Round #75 Div. 2 00:46 はてなブックマーク - Codeforces Beta Round #75 Div. 2 - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #75 (Div. 2 Only) - Codeforces

結果:Standings - Codeforces Beta Round #75 (Div. 2 Only) - Codeforces

=.ABCDE
--0:091:07---
1164+0/-0482682---

部屋内20位(Room 20),全体387位

Rating: 1557→ 1510 (-47)

 TLEに泣いた回でした.ナイーブに書いたら間に合わないのは分かっていても,じゃあどうすれば計算量を減らすかが思いつけませんでした.Editorialがあるのが救いです.

続きを読む

2011-06-20

[][] Codeforces Beta Round #74 Div.2 08:50 はてなブックマーク -  Codeforces Beta Round #74 Div.2 - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #74 (Div. 2 Only) - Codeforces

結果:Standings - Codeforces Beta Round #74 (Div. 2 Only) - Codeforces

=.ABCDE
--0:070:19-3--
1410+0/-0486924---

部屋内4位(Room 12),全体150位

Rating:1541 → 1557 (+16)

 YandexやICPCなどのイベントが続きご無沙汰だったCodeforces.張り切って臨んだのですが気づいたら朝でした.レート下がらなくてよかったです.

続きを読む

2011-06-19

[][] TopCoder Open 2011 Round1 19:39 はてなブックマーク -  TopCoder Open 2011 Round1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:12:15.506Passed System Test213.11
5001:02:27.079Opened0.00
10000:43:25.259Opened0.00
Challenge..0.00

部屋(Room 1) 16位,全体 1000位

Rating : 1548 → 1505 (-43)

上位800人がRound2に進出.easyを半分の時間で解くか,1回チャレンジを成功させると進出できたようです.

続きを読む

2011-06-15

[][] Project Euler Problem 123 21:56 はてなブックマーク -  Project Euler Problem 123 - 練習帳

問題文

 Problem 123 - Project Euler

要約

 p[n] を n 番目に小さい素数とする( n は 1-indexed)。(p[n] + 1)^{n}+(p[n] - 1)^{n}を p[n]^{2} で割った余りが 10^{10} を始めて越える n はいくつか。

続きを読む

2011-06-13

[][] Codeforces Beta Round #73 07:29 はてなブックマーク -  Codeforces Beta Round #73 - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #73 (Div. 1 Only) - Codeforces

Yandex OpenやICPCなどのイベントが続きご無沙汰だったCodeforces.参加はしませんでしたが,解いた問題について記録をします.

続きを読む

2011-06-11

[][] SRM 509 Div1 500 PalindromizationDiv1 01:34 はてなブックマーク -  SRM 509 Div1 500 PalindromizationDiv1 - 練習帳

分析(前回*1の続き)

続きを読む

2011-06-09

[][] TopCoder Single Round Match 509 Div1 09:21 はてなブックマーク -  TopCoder Single Round Match 509 Div1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:04:58.971Passed System Test242.60
5001:09:53.079Opened0.00
10001:06:36.095Opened0.00
Challenge..0.00

部屋(Room 26) 7位,全体 223位

Rating : 1448 → 1548 (+100)

 黄色くなりました.あまり満足のいかない結果がしばらく続いたのでうれしいです.次回の目標は青色に戻らないようにする事だと思います.

続きを読む

2011-06-05

[][] Google Code Jam Round 2 18:14 はてなブックマーク -  Google Code Jam Round 2 - 練習帳

 問題一覧:http://code.google.com/codejam/contest/dashboard?c=1150486

=A.B.C.D.
-SLSLSLSL
47.3443:0143:34------
.1 Wrong Try---1 Wrong Try---

全体 1703位.

普段の成績から考えれば妥当な線とはいえ,やっぱり悔しいです.

続きを読む

2011-06-04

[][] Project Euler Problem 60 19:29 はてなブックマーク -  Project Euler Problem 60 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=60

要約

 2 つの素数 a, b の組に対し, 10 進数で書き2 通りに連結したもの( ab と ba )が共に素数になるという条件を考える(条件Pと書く)。

 素数の5つ組で,どの 2 つを取っても条件Pを満たすようなものの中で,5 個の数の和が最小となるものを答えよ。

続きを読む

2011-06-03

[][] Project Euler Problem 105 09:40 はてなブックマーク -  Project Euler Problem 105 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=105

要約

 整数の有限集合Aに対し,その和をS(A)と書く,Aがspecial sum setであるとは次の条件を満たすものを言う.

  • 任意の集合B ⊂ A, C ⊂ A,B ∩ C = Φに対し,
    • S(B) ≠ S(C)
    • さらに#(B) > #(C)を満たすなら,S(B) > S(C)

整数の集合のリストが与えられている.リストにある集合の数は1000個で,各々の集合は整数8個から12個からなる.その中からspecial sum setを見つけ,それらのすべての和を求めよ.

続きを読む

2011-06-02

[][] Project Euler Problem 61 07:29 はてなブックマーク -  Project Euler Problem 61 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=61

要約

 次の条件を満たす数列 a[i] (0 <= i < 6) を求め,その数列の和を求めよ.条件を満たす数列は一つしかない事が保証されている.

  • a[i] は 10 進数で 4 桁の数( 1000 以上 9999 以下)
  • a[j] の下 2 桁と a[(j+1)%6]の上 2 桁は等しい(0 <= j < 6)
    • 例えば 1234, 3456, 5678, 7891, 9123, 2312など.最初と最後の数にも関係がある事に注意
  • a[i] は三角数,四角数・・・,八角数のいずれかで,それぞれの角数が1回ずつ表れる.

続きを読む