競プロをしながら、節約と株式投資でセミリタイアを目指す東大卒のブログ

東大卒でメーカー勤務の私がセミリタイアするために投資や競プロを頑張っていこうという趣旨で始めたブログです。独身男性です。お金の大切さや今後の生き方も併せて伝えられたらと思います。

エイシングプログラミングコンテストで書いたコード

using System;
using System.Numerics;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace debug
{
    class main
    {
        static void Main(string args)
        {
            //問題クラスを展開
            ProgramD a = new ProgramD();
            a.main();//実行する

        }

    }
    //エイシング
    class ProgramA
    {
        public void main()
        {
            //入力
            string s = Console.ReadLine().Split(' ');
            int h = int.Parse(s[0]);
            int w = int.Parse(s[1]);
            int k = int.Parse(s[2]);

            int count = 0;
            //hからwでkで割れるか調べる
            for(int i = h;i <= w;i++)
            {
                if (i % k == 0)
                    count++;
            }

            //答え出力
            Console.WriteLine(count);

        }
    }

    class ProgramB
    {
        public void main()
        {
            //入力
            int n = int.Parse(Console.ReadLine());
            string s = Console.ReadLine().Split(' ');

            int count = 0;
            //奇数番目のみ検索して、奇数かどうか見る
            for(int i = 0i < n;i = i + 2)
            {
                if (int.Parse(s[i]) % 2 == 1)
                    count++;
            }

            //答え出力
            Console.WriteLine(count);

        }
    }

    class ProgramC
    {
        public void main()
        {

            //入力
            int n = int.Parse(Console.ReadLine());

            int ans = new int[n];

            //(x,y,z)組み合わせを全探索最大でも1-100までの間しかないことに注目
            for(int x = 1;x <= 100;x++)
                for (int y = 1y <= 100y++)
                    for (int z = 1z <= 100z++)
                    {
                        long temp = x * x + y * y + z * z + x * y + x * z + y * z;
                        if (temp <= n)
                            ans[temp - 1]++;
                    }

            //答え出力
            for(int i = 0;i < n;i++)
                Console.WriteLine(ans[i]);



        }
    }

    class ProgramD
    {
        public void main()
        {

            //入力
            long n = long.Parse(Console.ReadLine());
            string s = Console.ReadLine();

            int count = 0;
            long num = 0;
            long num2 = 0;
            //あらかじめ1の数は数える
            for (int i = 0i < ni++)
            {
                if (s[i] == '1')
                    count++;
            }

            //popcount=0のとき
            if (count == 0)
            {
                for (int i = 0i < ni++)
                    Console.WriteLine("1");
                return;
            }
            //popcount=1のとき
            if (count == 1)
            {
                if (s[(int)n - 1] == '1')
                {
                    for (int i = 0i < ni++)
                    {
                        if (i == n - 1)
                            Console.WriteLine("0");
                        else
                            Console.WriteLine("2");
                    }
                }
                else
                {
                    for (int i = 0i < ni++)
                    {
                        if (s[i] == '1')
                            Console.WriteLine("0");
                        else if(i == n -1)
                            Console.WriteLine("2");
                        else
                            Console.WriteLine("1");
                    }
                }
                return;
            }

            //popcount±1野ときをそれぞれ求めておく
            for (int i = 0i < ni++)
            {
                if (s[i] == '1')
                {
                    num += modpow(2n - 1 - icount -1);
                    num2 += modpow(2n - 1 - icount + 1);
                }
            }

            for (int i = 0i < ni++)
            {
                long temp = 0;

                //ビット反転後の数を求める
                if (s[i] == '1')
                {
                    temp = num;
                    temp -= modpow(2n - 1 - icount - 1);
                    temp %= count - 1;
                }
                else
                {
                    temp = num2;
                    temp += modpow(2n - 1 - icount + 1);
                    temp %= count + 1;
                }

                //1以下目の操作終了
                long ans = 1;

                //0になるまで操作
                while(temp != 0)
                {
                    long t = 0;
                    long t2 = temp;
                    //2進数で1の数を出す
                    while (temp != 0)
                    {
                        t += temp % 2;
                        temp /= 2;
                    }

                    temp = t2 % t;
                    ans++;//一回の操作はここで終わり

                }

                //操作回数を出力
                Console.WriteLine(ans);
            }

        }



        
        //繰り返し二乗法
        static long modpow(long along nlong MOD)
        {
            if (n == 0)
                return 1;
            if (n % 2 == 0)
            {
                long temp = modpow(an / 2MOD);
                return temp * temp % MOD;
            }

            return a * modpow(an - 1MOD) % MOD;
        }
    }

    

}