そーすにっき

なんかいろいろのせておくばしょ

DDCC 2017 予選

結果:176位 3完

Dが解けなかったけど枠の都合予選通過しそう

A:2文字目と3文字目は違う必要があることを見落とし1WA

B:数字がオーバーフローし1WA

C:Dequeのおかげで5分でAC

D:解法できていたのに実装ミスから虚無

コードがうまく乗らないので準備でき次第載せます

Tenka1 Programmer Contest

http://tenka1-2017.contest.atcoder.jp/

結果:Cのみ300点

D500点が遠すぎたてかむずすぎた

C:二重ループを回すだけで解けるのを制約見逃しからかなり難しく考えてしまったので早解きに失敗

Cももう少し早く解けたしDのBit周りの精進がひどく足りない気がするので精進しなおします

でもまずはUbuntuの壊れた環境の再整備から…

#include <bits/stdc++.h>
 
#define i64 long long int
#define SPACE " "
using namespace std;
 
int main(){
  i64 N;
  cin >> N;
  i64 h=0,n,w,tmp;
  for(w=1;w<=3500;w++){
    for(n=1;n<=3500;n++){
      if(4*w*n-N*n-N*w<=0)continue;
      tmp = (N*w*n) % (4*w*n-N*n-N*w);
      if(!tmp){
        h=(N*w*n) / (4*w*n-N*n-N*w);
        break;
      }
    }
    if(h)break;
  }
  cout << h << SPACE << n << SPACE << w << endl;
}

おひさしぶり

更新が止まっているのは実家に帰っていたせいということにしておきたいんです

(全然問題解けてない)

そしてその間にAtcoderでは水色になりました

今日は競技プログラミングとは全然関係ない話にしようかと

じゃあ何かというとwindows10の0xc0000034エラーについての話

Windows Boot Managerの中身がぶっ壊れたというエラーの模様

無償アップグレード組で突然ハマるようで、ストレージの状態も悪くないのに再起動後突然ブートファイルが壊れてるとかどうなってるんだこのOSは

友人が突然これに引っ掛かり、自分もそのうちやらかしそうなのでとりあえず書いておきます

ブート

MediaCreationTool.exeをWindowsのサイトからDLして適当な外付けの何かに焼く

起動時F12を押してブートメディア選択して終わり(できないものもある)

修復

一番簡単な解決(出来ればベター)

>bootrec /fixmbr
>bootrec /fixboot
>bootrec /rebuildbcd

でもこれが通らない場合も少なくない模様

bcdbootをいじる

>diskpart
DISKPART> list disk
DISKPART> select disk 0
DISKPART> list volume
DISKPART> select volume 3
DISKPART> assign letter=S:
DISKPART> exit
>cd /d S:\EFI\Microsoft\Boot\
>ren BCD BCD.bak
>bootrec /fixboot
>bcdboot c:\Windows /l ja-JP /s S: /f ALL
>bootrec /rebuildbcd

これでエラーがなければ簡単だけども、どうやらBCD自体壊れてることがあるらしい
その時はBCDの作り直しから始まるとか

bcdeditで色々やる(あまり詳しくないので省略)

>cd S:\EFI\Microsoft\Boot
>bcdedit /createstore BCD
>bcdedit /store BCD /create {bootmgr} /d “Windows Boot Manager”
>bcdedit /store BCD /create /d “Windows 10” /application osloader

※エントリ {xxxx} は正常に作成されました と出るはず

>bcdedit /store BCD /set {bootmgr} default {xxxx}

中括弧を忘れるとエラー(1敗)

>bcdedit /store BCD /set {bootmgr} path \EFI\Microsoft\Boot\bootmgfw.efi
>bcdedit /store BCD /set {bootmgr} locale ja-jp
>bcdedit /store BCD /set {bootmgr} displayorder {default}
>bcdedit /store BCD /set {bootmgr} timeout 10
>bcdedit /store BCD /set {default} device partition=c:
>bcdedit /store BCD /set {default} osdevice partition=c:
>bcdedit /store BCD /set {default} path \windows\system32\winload.efi
>bcdedit /store BCD /set {default} systemroot \windows
>exit

後は起動出来れば勝ちなんだとか

出典

http://tooljp.com/Windows10/doc/system-recovery/trouble-shooting/0xc0000034/0xc0000034-Windows-not-start.html
https://panyaa.herokuapp.com/blog/54
http://qiita.com/Tats_U_/items/2639fab7cda852ad5143

AGC019

AtCoder Grand Contest 019 - AtCoder Grand Contest 019 | AtCoder

AGCはレート爆上げの機会になりやすくて嬉しいとか

結果:A,B2完

感想:Bの実装量をとても少なくできたので個人的には満足

A:

DPっぽく見えたけどそんなことはない

大容量ほど容量単価が安くないとそれを選択する意味がないので、それに当てはまらないサイズはカットして、上から順にとっていけばよし

0.25とか考えたくなかったので全部4倍して整数で解決(intOFに気づかず1WA)

B:

直感が輝き8分で終了

左からk文字に対しての並び替えを考えると左からk-1文字の並べ替え+αとなることが分かる

さらにαは左からk-1文字のうち左からk文字目と異なる文字の数と分かる(この辺は入力例1から試してみた)

上から1文字ずつバケットに読み込みながら異なる文字の数だけ足していけば解決

#include <bits/stdc++.h>
 
#define i64 long long
#define ui64 unsigned long long
#define ATCODER 1000000007
using namespace std;
 
////////////////////////

/* a */ 
int main(){
  #define INF -1
  i64 q,h,s,d,n;
  cin >> q >> h >> s >> d;
  if(q*2<h) {
    h=INF;
    // cout << 1 << endl;
  }
  if(q*4<s){ s=INF;}
  if(q*8<d){ d=INF;}
  if(h!=INF&&h*2<s){ s=INF;}
  if(h!=INF&&h*4<d){ d=INF;}
  if(s!=INF&&s*2<d){ d=INF;}
  cin >> n;
  n*=4;
  i64 res=0;
  if(d!=INF){
    res+=(i64)n/8*d;
    n%=8;
  }
  if(s!=INF){
    res+=(i64)n/4*s;
    n%=4;
  }
  if(h!=INF){
    res+=(i64)n/2*h;
    n%=2;
  }
  res+=(i64)n*q;
  // cout << q << " " << h << " " << s << " " << d << endl;
  cout << res << endl;
}

/* b */

char s[200005];
 
int main(){
  cin >> s;
  int alpha[26] = {0,};
  int t;
  i64 res = 1;
  for(int i=0;s[i]!='\0';i++){
    t = (int)s[i]-'a';
    alpha[t]+=1;
    res+=i-alpha[t]+1;
  }
  cout << res << endl;
}

ARC081

お盆前に帰省+諸々で精進出来なかった結果がこれだよ!

結果:Cのみ

C:
入力:要素数N 値A_i(i[0,N))
出力:Aから相異なる4つを選んで最大の長方形の面積を出力
解法:
ソートして2つ等しい要素があれば大きい順にそれを選んでいく
3, 5,5,5, 7,...などの場合に5,5,5,5と選択しないように注意する

#include <bits/stdc++.h>
 
#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define MDIST(a,b) abs(a-b)
#define DIST(a,b) sqrt((a)*(a)+(b)*(b))
#define ATCODER 1000000007
using namespace std;
 
////////////////////////
 
int main(){
  vector<int> a;
  int n;
  cin >> n;
  a.resize(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  sort(a.begin(),a.end(),greater<int>());
  int m1,m2;
  m1 = m2 = -1;
  for(int i=0;i<n-1;i++){
    if(a[i]==a[i+1]){
      if(m1==-1){
        m1 = a[i];
        i++;
      }else{
        m2 = a[i];
        break;
      }
    }else continue;
  }
  if(m1>0&&m2>0)cout << (i64)m1*m2 << endl;
  else cout << 0 << endl;
}

Dを1時間かけて解けなかった(400点)
400点問題で詰まってしまうのは重症なので精進しなおします

8000 - FizzBuzz

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=753&page=show_problem&problem=6022

海外の問題、解いてみたくなって、キャッチーなあの言葉に釣られて選択

結果:まんまFizzBuzzだった

えぇ…(困惑)

#include <bits/stdc++.h>

using namespace std;

int main(){
  int c;
  cin >> c;
  int x,y,n;
  while(c--){
    cin >> x >> y >> n;
    for(int i=1;i<=n;i++){
      if(!(i%x)&&!(i%y))cout << "FizzBuzz" << endl;
      else if(!(i%x))cout << "Fizz" << endl;
      else if(!(i%y))cout << "Buzz" << endl;
      else cout << i << endl;
    }
  }
}

POJ3413 - RPG

http://poj.org/problem?id=3413

POJから。某所で解けなかった問題を今更実装。

問題内容:
入力
RPGのクエストのクリアに必要な経験値A、十分な経験値Bと経験値S、初期状態の経験値D

制約
エストは各1回選択できる。
エスト1つが終わると成功失敗にかかわらず経験値を得る。
エストの成功確率はクエスト選択時の経験値をEXPとして以下の通りに定められる。
・0 (EXP<=A)
・1 (EXP>=B)
・(EXP-A)/(B-A) (それ以外)
エストの数は10以下、入力の経験値は全て1000以下

出力
全クエストを終了時最も成功確率が高くなる場合の成功確率とクエストの順番

解法
全探索
next_permutationして全通り試してみただけ
if(tmpprob>=maxprob)をif(tmpprob>maxprob)
にするとmaxprob=0の時に順番の出力が不正になりWA

およそ800~900ms要しておりやはりO(n*n!)は辛いと感じる一品

(にしても遅いような気がする)

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define MDIST(a,b) abs(a-b)
#define DIST(a,b) sqrt((a)*(a)+(b)*(b))
using namespace std;
 
////////////////////////

double calc(int a,int b,int d){
  if(d<=a)return 0.0;
  else if(d>=b)return 1.0;
  else return (double)(d-a)/(b-a);
}

int main(){
  int n,d;
  int a[10],b[10],s[10];
  cin >> n >> d;
  for(int i=0;i<n;i++){
    cin >> a[i] >> b[i] >> s[i];
  }
  vector<int> res(n),tmp(n);
  double maxprob=0.0;
  double tmpprob;
  int tmpexp;
  REP(i,n)tmp[i]=i;
  do{
    tmpprob = 1.0;
    tmpexp = d;
    for(int i=0;i<n;i++){
      tmpprob *= calc(a[tmp[i]],b[tmp[i]],tmpexp);
      tmpexp += s[tmp[i]];
    }
    if(tmpprob>=maxprob){
      maxprob = tmpprob;
      res = tmp;
    }
  }while(next_permutation(tmp.begin(),tmp.end()));
  cout << fixed << setprecision(3);
  cout << maxprob << endl;
  for(int i=0;i<n;i++){
    cout << res[i]+1 << " ";
  }cout << endl;
  return 0;
}