C - タイル (Tile)

Quiz

https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_c

AC Code

https://atcoder.jp/contests/joi2011yo/submissions/10218261

Code (抜粋)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    // input
    ll N; 
    cin >> N;
 
    ll Q;cin>>Q;
    while(Q--){
      ll x,y;cin>>x>>y;
      x--;y--;
      
      if(x>N/2){
        x = N-1-x;
      }
      if(y>N/2){
        y = N-1-y;
      }
 
      if(x>y) swap(x,y);
 
      if(x%3==0){
        p(1);
      }else if(x%3==1){
        p(2);
      }else{
        p(3);
      }
    }   
    return 0;
}

解法

• 対称性を利用すると、全ての点は左上の領域に移動しても色が変わらない
• x, yを入れ替えても色は変わらないので、x<=yとなるように移動してよい
• このように移動した後は考えるパターン数が減るのでコードがシンプルになる

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

No.982 Add

Quiz

https://yukicoder.me/problems/no/982

公式解法

https://yukicoder.me/problems/no/982/editorial

考えたこと

• gcd=1じゃなければ-1
• lcmの部分まで考えれば良さそう
• 実際にそれで求まるのだが、公式解説や他の人の解説では分からなかった
• それは私の数学力による

具体例を表で眺める

• A=21, B=16で表を描く。ここで肌色の箇所の数字は作ることができる（いい整数）
• lcm = 21x16 = 336
• lcmより大きい値は全て作れそう。ということで337を検索してみると存在する。(列64+行273)
• gcd=1なので、乗数が負を許せば1刻みで作れる気はする
  • -1 = 21x3 + 16x(-4)
  • 1 = 21x(-3) + 16x4
• lcmを超えた領域では、乗数が負にならないことを保ちながら1刻みで作れるのだろう
• ふわっとした理解だが、ここまでとする

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

C. Cow and Message

Quiz

https://codeforces.com/contest/1307/problem/C

解法

https://codeforces.com/blog/entry/73953

補足

• indexの関係は「arithmetic progression（等差数列）」になっていなければいけない
• なので、s=aaabbcccの場合の答えは9が正しい
  • 3x2x3=18ではない
• indexのセットを選ぶたびに等差は変わってもよい

例題

abcabcbopqrsc

ans = 6

わかりやすく分割すると

abc abc b opqrs c

• abcを3つ取れるようにsを設定した
• しかし答えは6
• bcの組が6個取れる
• abの組は5個
• もしsの後端にcが大量にあったとしても、abcの組はabの組以上にはならない

abcabcbopqrsccccccccccccccccccccccccc

• この場合の答えは351
• ccが大量に作れるため

振り返り

• 「長さ3以上は考える必要がない」と気づけるか
• 英語をちゃんと読まないと制約を見逃す

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

精進してても周りの同色より成長しないとレートは上がらないことに気がついた

レートが停滞する時ってありますよね。精進していれば解ける問題が増えていき、レートも上がっていくと何故か思っていた。しかしレートは相対評価。１つ上の色に行きたいなら、同色の人以上の精進をしないと抜きん出ることはできない。

頑張っている人のレート停滞は、少なくとも同等の色の方々と同じぐらいの努力はできているということなので、「維持できてる」ぐらいに思ったほうがいいと思うけどなぁ。

— nico_shindannin (@nico_shindannin) February 17, 2020

精進の成果を見せたいところだが、当然周りも精進しているため、

— beet (@beet_aizu) February 17, 2020

自分の精進 < 平均精進の場合

— beet (@beet_aizu) February 17, 2020

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

重複組み合わせには「数学的なもの」「蟻本的なもの」の2種類がある

数学的なもの

• nHrと表記されるもの
• https://mathtrain.jp/tyohukuc
• 例：{R, G, B}の玉が「無限に」あって、r個選ぶときの場合の数
• これはnCrが求められればいいのでn=10⁶程度まで求められる

蟻本的なもの

• n種類の物体がある
• i番目の物体は「Ai個」ある
• r個選ぶときの場合の数
• 蟻本v2 p67
• 計算量 O(nm)なのでn=10⁴までが限界

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～