天下一プログラマーコンテスト2017

天下一プログラマーコンテスト2017を解きました

入力された文字列Sの中にある'1'の数を求める。

・文字列Sを受け取ってs[i]=='1'ならans++してansを出力

・入力を数字として受け取ってSが0になるまで10の余りをansに加算してSを10で割ることを繰り返して最終的に求まったansを出力

ゲームの参加人数の最大値を求める。

・ $A_i$ が最大となるiを求めて $A_i+B_i$ を出力

4/N=1/h+1/n+1/wが成り立つh,n,wを求める。

hとnで全探索して $w=\frac{Nhn}{4nh-nN-hN}$ で自然数wが求まったらh,n,wを出力する。自分は、wを整数に代入してそれをdoubleにした時の値がwと等しい時wを整数と判定しました。

選んだ整数 $A_i$ の全てのbitwise orがK以下になるように選んだ時の $B_i$ の総和の最大値を求める。

・整数Xとbit単位でor演算を行ってXのままの整数のみを選ぶと選んだ整数全てでor演算を行っても必ずX以下の値となる

・2進数10111のような下位ビットが連続して1を示す値は10101のような値を包含する

この2つを利用する。

まず、Xの候補を求める。最初にKを2進数に変換して次の処理を行う。1を示す桁を選びそのビットの値を0にして、選択した桁より上位のビットの値はそのままで下位のビットを全て1にした値を候補値とする。

例えば、K=14の場合、2進数にすると1110となるため、候補値は7(0111),11(1011),13(1101)となる。

次に、それぞれの候補値で $XorA_i=X$ となるiの $B_i$ の総和を求め、その中の最大値を出力する。

C問題とD問題を解くときに実装が大変だった。