SRM563 - 不定期プログラミング覚え書き

250-500-850とか

結果報告

Level	ProblemName	Status	Point
Easy	KnightCircuit2	PassedSystem Test	229.48
Medium	AlternateColors2	PassedSystemTest	231.23
Hard	DefectiveAddition	Opened	0.0

2問答えて1問チャレンジ成功した大勝利回。
初の2桁順位じゃなかろうか？

1545->1486->1500->1497->1518->1457-> 1595とかそんな感じのレート遷移をしてる。
ちなみに、毎回色が変わる記録はここで途絶えた。

Easy KnightCircuit2

問題

入力で与えられる盤面を、チェスのナイトが動きまわるとする。場所は好きな所からはじめて良く、同じ所に戻ってきても良い。
最大で何種類の枡に到達出来るか答えよ

考えたこと

ガリガリ紙に書く。

短い辺が１だったら移動不可だから答えは１
短い辺が２だったら、長い辺の方向にひたすら移動出来るだけ。(長い辺+1)/2が超えた。
短い辺が３の時、全部移動可能…じゃなかった。3*3の時は真ん中に到達不可能。でも他は全部移動可能(3*4が移動可能と示せたらそれ以上のサイズは帰納法で示せる感じ)

コード

  int maxSize(int w, int h) {
    if( h < w ) return  maxSize( h, w );
    // must w <= h
    if( w == 1 ) return 1;
    if( w == 2 ) return (h+1)/2;
    if( h == 3 ) return 8;
    return w*h;
  }

計算量は勿論定数。

Medium AlternateColors2

問題

赤・緑・青のボールがn個あるとする。
プレイヤーは赤のボールを１つ取って捨てる・緑のボールを１つ取って捨てる・青のボールを１つ取って捨てる
という操作を延々と続ける。（ボールがない色に対する操作はスキップされる）
k回目に赤のボールを取るようなボールの個数のパターンを答えよ

考えたこと

ガリガリ場合分けした。
まず、k-1回目までに捨てられた赤玉の個数をpとする
(1) 緑のボールも青のボールもp個捨てられている場合
最低１つは赤玉があるとして、残ったn-k個は赤・緑・青のどれでも良い。
これは ${}_{n-k+2} C_2$ として計算出来る。
(2)それ以外の場合、捨てられた個数の総数はk-1個なのだから
緑・青それぞれ、最大でmin(k-1-p,p)個、最小でmax(0, k-1-2p)個捨てられる事となる。
（そして捨てられた緑玉・青玉の数の和はk-1-pである)
(2)' k-1-p < p の場合 (この時、max(0,k-1-2p) = 0 であることに注意する)
緑・青の捨てられた玉の個数は(0,k-1-p),(1,k-1-p-1),...,(k-1-p-1,1),(k-1-p,0)
というk-1-p個の可能性がある。
どの場合も緑・青は既に枯渇しているはずだから、残った玉はすべて赤色である。
よって、k-p-1通りである。
(2)'' k-1-p>=pの場合
緑・青の捨てられた玉の個数は(p,k-1-2p),(p-1,k-1-2p-1),...,(k-1-2p-1,p-1),(k-1-2p,p)
のパターンが有る。
最初の場合と最後の場合は、k-1回玉を捨てた後、最低１つは赤玉があるとして、
残りは赤＆緑or 赤＆青で適当に割り振れば良い。つまりn-k+1通り。
＊k-1-2pはpでないことが保証されている(その場合は(1)で計算した）事に注意
残りは(2)'と一緒で、それぞれ１通りである。

コード

  long long countWays(int n, int k) {
    long long result=0;
    ll key = k-1;
    ll rest = n-key;
    for( ll T_r = (key+2)/3; T_r <= key ; T_r++ ){
      //cout << "now: "<< T_r  << endl;
      if( T_r * 3 == key ){
        //cout << rest << endl;
        if( rest == 1 ) result += 1;
        else result += (rest+1)*(rest)/2;
      }
      else{
        ll mi = max( 0LL, key-2*T_r);
        ll ma = min( T_r , key-T_r );
        //cout << mi << "-" << ma << endl;
        if( ma == T_r ){
          //cout << "rest..." << rest << endl;
          result += 2*(rest);
          ma--;
          if( mi == key-2*T_r ) mi++;
        }
        //cout << mi << "-" << ma << endl;
        ll range = ma-mi+1;
        result += range;
      }
      //cout << "result: "<< result << endl;
    }
    return result;
  }

計算量は $O(k)$ 。kは最大100000なので余裕で間に合う。

Hard DefectiveAddiction

問題

int 配列 cards と整数nが与えられる
int配列と同じ長さの配列arrayで
array[i]

考えたこと

何か計算のところはごちゃごちゃ書いてあったけど結局xorでしょ、とまでは思った。
何か凄い賢い方法有りそうなんだけど、思いつかず。